식초의 지식보관소

※모든 사진과 자료의 출처는 나동빈 [이것이 취업을 위한 코딩 테스트다] 입니다※ 최단 경로 문제 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 다익스트라 최단 경로 알고리즘 개요 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다. 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않는다. 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다. 매 상황에..

※모든 사진과 자료의 출처는 나동빈 [이것이 취업을 위한 코딩 테스트다] 입니다※ 다이나믹 프로그래밍 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성된다. 다이나믹 프로그래밍은 동적 계획법이라고도 부른다. 일반적인 프로그래밍 분야에서의 동적(Dynamic)이란 어떤 의미일까? 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다. 반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단..

※모든 사진과 자료의 출처는 나동빈 [이것이 취업을 위한 코딩 테스트다] 입니다※ 이진 탐색 알고리즘 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 이진 탐색 동작 예시 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는 예시를 살펴본다. [Step 1] 시작점: 0, 끝점: 9, 중간점: 4 (소수점 이하 제거) 중간점 값과 찾고자하는 값 비교하여 중간점 값이 더 크다면 중간점~오른쪽 끝은 확인할 필요가 없다. 끝점을 중간점 앞으로 옮긴다. [Step 2] 시작점: 0, 끝점: 3, ..

※모든 사진과 자료의 출처는 나동빈 [이것이 취업을 위한 코딩 테스트다] 입니다※ 정렬 알고리즘 정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것이다. 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. 선택 정렬 동작 예시 정렬할 데이터를 준비한다. [Step 0] 처리되지 않은 데이터 중 가장 작은 0을 선택해 가장 앞의 7과 바꾼다. [Step 1] 처리되지 않은 데이터 중 가장 작은 1을 선택해 가장 앞의 5와 바꾼다. [Step 2] 처리되지 않은 데이터 중 가장 작은2를 선택해 가장 앞의 9와 바꾼다. [Step 3] 처리되지 않은 데이터 중 가장 작은..

※모든 사진과 자료의 출처는 나동빈 [이것이 취업을 위한 코딩 테스트다] 입니다※ 그래프 탐색 알고리즘 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적 그래프 탐색 알고리즘 : DFS, BFS DFS, BFS는 코테에서 자주 등장하는 유형 대기업 공채에서 자주 출제 스택 자료구조 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조 입구와 출구가 동일한 형태로 스택을 시각화한다. ex. 박스 쌓기 스택 동작 예시 삭제는 가장 마지막에 있던 원소가 삭제된다. 스택 구현 예제 stack = [ ] #리스트 자료형 사용한다. #삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제( ) - 삽입(1) - 삽입(4) - 삭제( ) stack .append(5)..

※모든 사진과 자료의 출처는 나동빈 [이것이 취업을 위한 코딩 테스트다] 입니다※ 실전에서 유용한 표준 라이브러리 내장 함수 : 기본 입출력 함수부터 정렬 함수까지 기본적인 함수 제공한다. 파이썬 프로그램 작성할 때 없어서는 안 되는 필수적인 기능 포함한다. itertools : 반복되는 형태의 데이터를 처리하기 위한 유용한 기능들 제공한다. 순혈과 조합 라이브러리는 코딩 테스트에서 자주 사용된다. heapq : 힙(Heap) 자료구조를 제공한다. 우선순위 큐 기능을 구현하기 위해 사용된다. bisect : 이진 탐색(Binary Search) 기능을 제공한다. collections : 덱(deque), 카운터(Counter)등의 유용한 자료구조 포함한다. math : 필수적인 수학적 기능을 제공한다. ..

※모든 사진과 자료의 출처는 나동빈 [이것이 취업을 위한 코딩 테스트다] 입니다※ 함수 함수란 특정한 작업을 하나의 단위로 묶어 놓은 것이다. 함수를 사용하면 불필요한 소스코드의 반복 줄일 수 있다. 함수의 종류 내장함수 : 파이썬이 기본적으로 제공하는 함수 사용자 정의 함수 : 개발자가 직접 정의하여 사용할 수 있는 함수 함수 정의하기 프로그램에는 똑같은 코드가 반복적으로 사용되어야 할 때가 많다. 함수를 사용하면 소스코드의 길이를 줄일 수 있다. 매개변수 : 함수 내부에서 사용할 변수 (입력할 때 사용한다.) 반환 값 : 함수에서 처리 된 결과를 반환 (return 키워드 함께 def 함수명(매개변수); 실행할 소스 코드 return 반환 값 def (define) : 정의하겠다는 의미. 매개변수와 ..

※모든 사진과 자료의 출처는 나동빈 [이것이 취업을 위한 코딩 테스트다] 입니다※ 조건문 조건문은 프로그램의 흐름을 제어하는 문법이다. 조건에 따라서 프로그램의 로직 설정한다. if 키워드를 이용한다 참일 경우 print() 안의 값 출력한다. 들여쓰기 코드의 블록을 들여쓰기로 지정한다. 블록 : 특정 기능 실행 위한 한 단위의 코드 묶음 if가 참일 경우, 같은 들여쓰기를 한 부분이 연달아 실행된다. 들여쓰기를 하지 않은 2번 부분은 무조건 실행된다. 표준은 4개의 스페이스 사용하는 것 추천한다. 조건문의 기본 형태 if ~ elif ~ else 경우에 따라서 elif 혹은 else 부분은 사용하지 않아도 된다. 비교 연산자 특정한 두 값을 비교할 때 이용할 수 있다. 비교 연산자 설명 X == Y 서..

※모든 사진과 자료의 출처는 나동빈 [이것이 취업을 위한 코딩 테스트다] 입니다※ 입출력 모든 프로그램은 적절한 입출력 양식이 있다. 프로그램 동작의 1번째 단계 = 데이터 입력 받거나 생성하는 것이다. 문제에서 요구하는 대로 입력, 출력한다. (자주 사용되는) 표준 입력 방법 input()함수 : 한 줄의 문자열 입력 받는 함수 map()함수 : 리스트의 모든 원소에 각각 특정한 함수를 적용할 때 사용 예) 공백을 기준으로 구분된 데이터를 입력 받을 때 list( map( int, input().split() ) ) 입력을 받고, 공백 기준으로 구분을 하고, 각 원소를 정수형으로 바꾸고난 다음에, 리스트로 만들어 준다 예) 공백을 기준으로 구분된 데이터의 개수가 많지 않다면 (개수가 정해져 있을 때) ..

※모든 사진과 자료의 출처는 나동빈 [이것이 취업을 위한 코딩 테스트다] 입니다※ 수 자료형 정수형 a = 777 a = a + 5 print(a) 특정한 변수의 값을 증가/감소 시키는 것이 가능하다. 실수형 a = 5. a = -.7 소수부, 정수부 0인 경우, 0인 부분 생략 가능하다. a = 0.3 + 0.6 (출력: 0.89999999) 컴퓨터 시스템은 실수 정보를 표현하는 정확도에 한계를 가진다. 2진수를 사용하기 때문이다. a = 0.3 + 0.6 print(round(a, 4)) (출력: 0.9) round()함수 : round(실수, 반올림하려는 자릿수) 지수 표현 방식 1e9 = 10의 9제곱 = 10억 e나 E 다음에 오는 수는 10의 지수부 이다. 임의의 큰 수를 표현하기 위해 자주 ..