코딩테스트(파이썬)

그리디(Greedy)

현재 상황에서 지금 당장 좋은 것만 고르는 방법

대부분의 그리디 알고리즘 문제는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 한다. 문제를 읽고 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고 고민해 보아야 한다.

구현(Implementaion)

머리속에 있는 알고리즘을 소스코드로 바꾸는 과정

따라서 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다.

완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 방법

파이썬은 구현 상의 복잡함은 적은 편이지만 데이터 처리량이 많을 때는 꼭 메모리 제한을 고려해야 한다.

파이썬에서 리스트의 크기

1,000개 -> 4KB, 1,000,000(백만) -> 4MB, 10,000,000(천만) -> 40MB

메모리 제한 뿐만 아니라 시간 제한도 고려해야 하는데, 1초에 2000만번의 연산을 수행한다고 가정하면 크게 무리가 없다. 따라서 만약 데이터의 개수가 100만개라면, NlogN의 시간복잡도를 가지는 알고리즘을 이용하여 풀어야 한다. Pypy3를 지원한다면 1초에 2000만 번에서 1억 번 정도의 연산을 처리할 수 있다.

DFS / BFS

◼ 스택(Stack) : 먼저 들어간 데이터가 나중에 나오는 FILO(First In Last Out)구조 파이썬 내에서는 기본 리스트에서 append()와 pop()메소드를 사용하면 된다.

◼ 큐(Queue) : 먼저 들어간 데이터가 먼저 나오는 FIFO(First In First Out)구조 collections모듈에서 제공하는 deque 자료구조를 통해 큐를 구현할 수 있다. append()와 popleft(), reverse() 함수 등이 있다.

◼ 재귀 함수(Recursive Function) : 재귀 함수란 함수 내에서 자기 자신을 호출하는 함수 재귀 함수는 반드시 종료 조건을 명시해 주어야 한다.

◼ 그래프(Graph) : 그래프는 노드(Node, 또는 정점 Vertex)와 간선(Edge)로 이루어진다. 각 노드들이 연결되어 있는 것을 인접하다(Adjacent)라고 하며 그래프를 표현하는 방식은 크게 2가지가 있다.

인접 행렬(Adjacent Matrix) : 그래프를 2차원 행렬로 표현한 방식으로 메모리가 많이 사용되지만 특정한 두 노드의 연결성을 빠르게 확인할 수 있다.
인접 리스트(Adjacent List) : 그래프를 연결된 정보만을 저장하기 때문에 효율적이지만 특정한 두 노드의 연결성을 확인하는데 인접 행렬보다 느리지만 특정 노드부터 인접한 모든 노드를 방문해야 하는 경우에는 효율적이다.

DFS(깊이 우선 탐색)

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘으로 모든 데이터를 탐색하는데 O(N)의 시간이 소요된다.

탐색 시작 노드를 스택에 넣고 방문처리 한다.
스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 인접 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼낸다.
1,2의 과정을 반복한다.

재귀함수를 이용할 경우 스택을 사용하지 않고 구현 가능하며 더 간결해진다. 그렇지만 컴퓨터 시스템의 동작 특성상 실제 프로그램의 수행 시간은 느려질 수 있다. 따라서 스택을 이용하여 수행 시간을 완화하는 방법도 필요하다.

BFS(너비 우선 탐색)

그래프에서 가까운 노드부터 탐색하는 알고리즘으로 DFS와 마찬가지로 모든 데이터를 탐색하는데 O(N)의 시간이 소요된다. 하지만 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편이다.

탐색 노드를 큐에 넣고 방문처리 한다.
큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 넣고 방문처리 한다.
2의 과정을 수행할 수 없을 때까지 반복한다.

정렬(Sorting)

◼ 선택 정렬(Selection Sort) : 가장 작은 것을 선택해 정렬하는 방법. 속도가 느려 알고리즘 문제에 사용하기 적합하지 않다

시간복잡도 O(N^2)

가장 작은 데이터 선택
맨 앞에 있는 데이터와 교환
나머지 중 가장 작은 데이터 선택
두번째 데이터와 교환
반복...

◼ 삽입 정렬(Insertion Sort) : 특정한 데이터를 적절한 위치에 삽입한다는 의미로 해당 데이터 이전 까지는 이미 정렬되어 있다고 가정한다. 보통 비효율적이지만, 거의 정렬이 되어 있는 상황에서는 퀵 정렬 알고리즘보다 강력하다.

시간복잡도 O(N^2)

첫번째 데이터는 정렬되었다고 판단하고 두번째 데이터부터 시작
두번째 데이터를 첫번째 데이터의 왼쪽 또는 오른쪽 중 적절한 위치에 삽입
세번째 데이터는 ^ 1 ^ 2 ^ 총 세 자리중 적절한 위치에 삽입
반복...

◼ 퀵 정렬(Quick Sort) : 기준을 설정하고 기준 데이터보다 큰 데이터와 작은 데이터의 위치를 교환한 후 리스트를 반으로 나누는 방식

평균 시간복잡도 O(NlogN)이며, 최악의 경우(이미 데이터가 정렬되어 있는 경우) O(N^2)

첫번째 데이터를 기준점 피벗(Pivot)으로 설정
Pivot을 기준으로 왼쪽에서부터 Pivot보다 큰 데이터를 선택하고 오른쪽에서부터 Pivot보다 작은 데이터를 선택
작은 데이터의 인덱스와 큰 데이터의 인덱스를 비교
작은 데이터의 인덱스가 더 작다면 Pivot과 작은 데이터를 교환 후 Pivot을 기준으로 양 쪽으로 나누어 퀵 정렬 수행
작은 데이터의 인덱스가 더 크다면 작은 데이터와 큰 데이터를 교환 후 2번부터 다시 수행

◼ 계수 정렬(Count Sort) : 특정한 조건이 부합할 때만 사용할 수 있는 빠른 정렬 알고리즘이다. 예를 들어, 모든 데이터가 양수인 경우 최악의 경우에도 O(N + K) (N : 데이터의 개수, K : 데이터의 최댓값)을 보장한다. 데이터의 크기 범위가 제한적이고 정수 형태로 표현 가능할 때만 사용가능하다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용가능하며 특히 데이터가 많이 중복되어 있을 때, 효과적이다. 예를 들어, 학생의 성적이 0 ~ 100 사이에 정수로 나타나는데, 만약 학생수가 매우 많다면 효과적이라고 할 수 있다. 그러나 만약 데이터가 0과 999,999만 있다면, 1,000,000크기의 리스트를 생성해야 함으로 비효율적이다.

시간복잡도 O(N + K), 공간 복잡도 O(N + K)

데이터 크기에 맞게 리스트 생성
데이터에 해당하는 인덱스 + 1
반복..
앞에서부터 데이터 개수에 맞게 출력

◼ 파이썬 정렬 라이브러리 : 파이썬 정렬 라이브러리인 sorted()는 병합 정렬과 삽입 정렬의 아이디어를 더한 정렬 알고리즘을 사용하며, 최악의 경우에도 시간복잡도 O(NlogN)을 보장하기 때문에 효과적이다.

문제 유형
1. 정렬 라이브러리로 풀 수 있는 문제 : sorted()의 사용법을 숙지하면 쉽게 풀 수 있다.
2. 정렬 알고리즘의 원리에 대해서 물어보는 문제 : 선택, 삽입, 퀵 정렬 등의 원리를 알아야 풀 수 있다.
3. 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법이 아닌 계수 정렬이나 다른 정렬 알고리즘을 이용하거나 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.

이진 탐색(Binary Search)

◼ 순차 탐색(Sequential Search) : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법. count() 메소드를 이용할 경우, 순차 탐색이 이루어진다.

◼ 이진 탐색(Binary Search) : 찾으려는 데이터와 중간점 위치에 있는 데이터를 비교함으로서 탐색하는 방법으로 정렬되어 있는 데이터에서만 사용 가능 하다. 단골로 나오는 문제이니 가급적이면 외우는 것이 좋다. 데이터의 탐색 범위가 2000만을 넘어갈 경우 이진 탐색을 고려해야 한다. bisect 라이브러리를 사용하는 것도 효과적이다.

다이나믹 프로그래밍(Dynamic Programing)

큰 문제를 작은 문제로 나눌 수 있다.
작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

위 두 조건을 만족하는 경우에 다이나믹 프로그래밍을 사용할 수 있다.
다이나믹 프로그래밍에는 두 가지 방식과 메모제이션 기법이 있다.

◼ 탑다운(Top-Down) 방식 : 탑다운 방식은 재귀함수를 이용해 큰 문제에서 작은 문제로 내려가는 방식을 말한다.

◼ 보텀업(Bottom-Up) 방식 : 반복문을 이용해 작은 문제부터 차근차근 답을 도출해 나가는 방식을 말한다.

◼ 메모제이션(Memoization) : 메모제이션은 한번 계산한 작은 문제의 값을 저장해두고 다른 계산에서 해당 값을 이용하는 것을 말한다. 이를 통해 같은 계산을 여러번 하는 것을 막을 수 있다. 탑다운 방식에는 메모제이션이라 표현하고 보텀업 방식에서는 DP 테이블 이라고 부른다.

예시 : 피보나치 수열

시스템 상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문에, 재귀 함수를 이용하는 탑다운 방식보다는 반복문을 이용하는 보텀업 방식으로 구현하는 것을 권장한다. resursion depth와 관련된 오류 발생시 sys라이브러리에 있는 setrecursionlimit()을 이용하여 재귀 제한을 완화할 수 있다.

최단 경로(Shortest Path)

◼ 다익스트라(Dijkstra) : 여러 개 노드가 있을 때, 특정 노드에서 다른 노드로 가는 각각의 최단경로를 구해주는 알고리즘이다. 음의 간선이 없을 때, 정상적으로 동작한다. 어떻게 구현하느냐의 차이가 있지만 잘 구현하는 경우 O(ElogV) (E : 간선의 개수, V : 노드의 개수)의 시간이 소요된다. 또 가장 가까운 노드를 계속해서 탐색해 나가기 때문에 그리디 알고리즘의 한 종류라고 볼 수 있다.

출발 노드 설정
최단 거리 테이블 초기화(일반적으로 출발 노드는 0 나머지는 INF, INF는 int(1e9)로 보통 사용)
방문하지 않은 노드 중 가장 가까운 노드 선택(heapq를 사용)
해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
3, 4번 반복

heapq와 리스트의 차이 : 리스트의 경우 삽입하는데 O(1), 삭제하는데 O(N)의 시간이 소요된다. 그러나 heapq의 경우 삽입과 삭제 모두 O(logN)의 시간이 소요된다.

◼ 플로이드 워셜(Floyd-Warshall) : 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용하는 알고리즘이다. 총 시간 복잡도는 O(N^3)으로 현재 노드를 거쳐가는 모든 경로를 고려한다. N번 만큼의 단계를 반복하며 점화식에 맞게 2차원 리스트를 갱신하기 때문에 다이나믹 프로그래밍이라고 볼 수 있다.

현재 노드에서 다음 노드까지 이미 계산되어 있는 값과 현재 노드에서 새로운 노드를 거쳐 다음노드로 가는 경우 중 작은 값을 계속해서 골라가며 진행.

username1103/python_coding_test