앞서 배운 DFS/BFS와 최단 경로 문제에서 다룬 내용은 모두 그래프 알고리즘의 한 유형으로 볼 수 있다. 만약 알고리즘 문제를 접했을 때 서로 다른 개체가 연결되어 있다는 이야기를 들으면 가장 먼저 그래프 알고리즘을 의심해보도록 하자. 여기서는 크루스칼 알고리즘과 위상 정렬 알고리즘을 알아보도록 한다. 서로소 집합 그 전에 먼저 서로소 집합 알고리즘을 배워야 한다. 서로소 집합은 union-find 자료구조라고 불리며, 같은 집합에 포함되는지 찾고 합치는 연산을 반복한다. 소스코드는 아래와 같다. def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def unio..
벨만 포드 다익스트라 관련 알고리즘 문제를 풀다가 알게된 알고리즘이다. 다익스트라와 비슷하지만 차이점은 음수 간선이 포함되어 있을 때도 최단 경로를 구할 수 있다는 점이다. 벨만 포드에서 주목해야 할 부분은 음수 간선을 포함하고 있는 간선이 사이클을 형성한다면 최단 경로가 무한히 음수가 될 가능성이 있다는 것이다. 벨만 포드는 이러한 음의 사이클을 잡아낼 수 있는 알고리즘이다. 하지만 시간 복잡도가 O(VE)로 다익스트라 알고리즘에 비해 느리다는 단점이 있다. INF = int(1e9) v, e = map(int, input().split()) graph = [] distance = [INF] * (v + 1) # 모든 간선의 정보 입력 for _ in range(e): a, b, c = map(int,..
다익스트라 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 기본적으로 그리디 알고리즘으로 분류된다. 해당 알고리즘 코드는 꼭 숙지하고 외워두도록 하자! 참고로 해당 소스코드의 시간 복잡도는 O(ElogV)이다. import heapq INF = 1e9 n, m = map(int, input().split()) start = int(intput()) # 시작 노드 graph = [[] for i in range(n+1))] distance = [INF] * (n+1) for _ in range(m): a, b, c = map(int, input().split()) graph[a].append((b, c)) def dijkstra(start): q = [] heapq.h..
다이나믹 프로그래밍은 메모리 공간을 약간 더 사용함으로써 연산 속도를 비약적으로 증가시킬 수 있는 알고리즘이다. 다만 항상 다이나믹 프로그래밍을 사용할 수 있는 것은 아니고, 아래의 조건을 만족시킬 때 사용할 수 있다. 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 위의 조건은 대부분 점화식 형태를 가지고 있기 때문에 다이나믹 프로그래밍인 것 같다면 문제에 알맞는 점화식을 떠올리는 것이 좋은 방법이다. 메모이제이션 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나로, 한 번 구한 결과를 메모리 공간에 메모해두고, 같은 식을 호출하면 메모한 결과를 그대로 가져오는 기법이다. 탑다운과 보텀업 탑다운 방식: 재귀 함수를 이용하여 큰 문제를 ..
이진탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN)이다. def binary_search(array, target, start, end): while start target: end = mid - 1 else: start = mid + 1 이진 탐색 알고리즘은 가급적 외우고, 탐색 범위가 2000만을 넘어가면 접근해보는 것을 권한다.
선택 정렬 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다. 시간 복잡도는 O(N^2)이다. 선택 정렬을 이용하는 경우 데이터 개수가 10000개 이상이면 속도가 급격히 느려진다. for i in range(n): min_index = i for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] 삽입 정렬 정렬하려는 데이터 앞 쪽의 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다. 다시 말해 특정한 데이터..
사전 지식 인접 행렬: 2차원 행렬로 그래프의 연결 관계를 표현하는 방식 ex. [[0, 7, 5], [7, 0, INF], [5, INF, 0]] 인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식 ex. [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]] 인접 행렬은 메모리를 잡아먹지만, 그만큼 탐색 속도가 빠르고, 인접 리스트는 메모리를 효율적으로 쓸 수 있지만, 연결된 데이터를 하나 씩 확인해야 하기 때문에 속도가 느리다. DFS 그래프에서 깊은 부분을 우선적으로 탐색하는 깊이 우선 탐색 알고리즘이다. 스택과 재귀를 이용하여 구현하고 동작 과정은 다음과 같다. 아래의 동작 과정을 꼭 숙지하자!! 탐색 시작 노드를 스택에 삽입 후 방문 처리 스택의 최상단 노드에 방문하지 않..
코딩 테스트에서 구현은 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 의미한다. 구현은 언어의 문법을 잘 이해하고 경험이 있어야만 바로 떠올릴 수 있다. 구현은 크게 모든 경우의 수를 다 계산하는 완전 탐색과 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 시뮬레이션으로 나눌 수 있다. 구현 시에는 메모리나 시간에 대해 특히 조심해야 한다. 메모리는 사용량 제한보다 더 적은 크기의 메모리를 사용해야 한다는 점 정도만 기억하고, 시간은 1초에 2000만 번의 연산을 수행한다고 가정하면 안정적이게 풀 수 있다. 구현은 문제 길이가 굉장히 긴 편이지만 고차원적인 사고력을 요구하지는 않기에 파이썬 문법에 익숙해진다면 다른 문제에 비해 오히려 쉽게 풀 수 있다. 핵심: 파이썬 문법..
그리디 알고리즘 그리디라는 이름에서 알 수 있듯이 탐욕적으로 현재 상황에서 지금 당장 좋은 것만 고르는 방법. 즉 매 단계(순회)마다 그 순간에 이용할 수 있는 정보를 바탕으로 문제를 풀 수 있는 실마리가 보이는 방법(최선의 방법)을 "고르려고" 한다. 사전 지식이 없어도 풀 수 있지만, 단순히 현재 가장 좋아보이는 것만을 선택해도 문제를 풀 수 있는지에 대한 고민이 필요하다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 '가장 큰 순서대로', '가장 작은 순서대로'와 같이 기준을 제시해주거나 어느 정도 유추할 수 있다. 따라서 자주 정렬 문제와 짝을 이룬다. 그리디 알고리즘의 가장 중요한 점은 ①최소한의 아이디어를 떠올리고, ②이것이 정당한 지 검토할 수 있어야 한다. 처음에는 다양..
