위상 정렬의 조건 주어진 그래프에서 위상 정렬을 하려면 1. 위상 정렬을 할 그래프는 간선이 방향성을 가지는 그래프여야 한다 2. 그래프 내부에 순환이 있으면 안된다 3. 위상 정렬에서는 여러 가지 답이 존재할 수 있따. 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면 여러 가지 답이 존재한다 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다. 스택을 활용한 DFS를 이용해 위상 정렬을 수행할 수도 있다. 주요 알고리즘 로직 연결된 선에 대한 정보(connection 배열)을 만들어주고 연결선의 갯수는 보통은 작은 쪽에 설정해준다(문제에 따라 유동적) 그리고 연결선은 queue를 pop시켜 리스트를 하나씩 뺼 떄마다 연결되어 있던 선들을 제거해주고 연결된 선이..

DFS 정의 DFS는 깊이 우선 탐색의 약자로서 그래프 순회 방법이다 DFS는 한 지점(vertex)에서 간선을 타고 아래로 계속 내려가면서 끝에 도달한다. 도착 지점이 아닌 경우, 다시 돌아와 다른 지점에서 간선을 타고 탐색을 계속 하다가 도착 지점에 도달하면 종료한다. 그러다보니 DFS는 방향이 있는 그래프에서 구현한다. 구현 DFS는 주로 재귀 함수의 연속 호출로 구현을 하거나 스택으로 구현한다. 주로 재귀로 구현하는 것 같은데 백트래킹 알고리즘이 DFS를 대표적으로 구현하는 예이다. 재귀로 구현할 때와, 스택으로 구현할 때의 탐색 순서가 다를 수 있다. DFS는 방향이 있는 그래프에서 구현한다. [재귀] 1. 재귀로는 일단 지점 1부터 지점1이 연결되는 끝까지 파고 들어간 다음, 다시 하나 올라와..

다익스트라 알고리즘 최단 경로 찾기 알고리즘의 하나로, 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단경로를 알려준다 단, 음의 간선이 있을 경우는 사용할 수 없으며, 하나의 최단 거리를 구할 때, 그 이전까지 구했던 최단 경로의 정보를 그대로 사용하기 때문에 DP 문제라고 볼 수 있다. 원리 특정한 하나의 정점을 잡고, 그 정점과 이웃한 정점들의 비용을 각각 확인하여 그 후, 이웃한 정점들 중 가장 비용이 적게 드는 정점을 기준으로 다시 한 번 확인한다. (직접 이웃한 정점으로 가는 것보다, 이웃한 다른 정점을 거쳐서 가는 것이 더 적은 비용이 들수도 있기 때문에) 이걸 반복하면서, 현재까지 알고 있던 최단 경로를 계속 갱신해나가면 된다 1. 출발 노드와, 도착 노드를 설정 2. 알고 있는 모든 ..

그래프란? 정점과 간선들로 이루어진 집합으로 표현되는 자료 구조 트리도 일종의 그래프라고 할 수 있다 무방향 그래프: 간선이 방향을 가지지 않음 방향 그래프: 간선이 방향을 가지고 있음 가중치 그래프: 각 간선에 가중치 정보가 포함됨 그래프의 구현 1. 인접 행렬 기반 그래프 각 정점 간의 가중치나 간선의 유무를 행렬로 표현한다 무방향 그래프의 경우 전치행렬이 되어도 값이 같다 2. 인접 리스트 기반 그래프 인접 행렬이 행렬을 이용한 것과는 달리 인접 리스트로 구현한다 파이썬에서는 딕셔너리 자료형에 리스트를 넣어 쉽게 인접 리스트처럼 구현하여 사용할 수 있다 그래프 응용 BFS, DFS 알고리즘이 있다 BFS는 너비 우선 알고리즘이고, DFS는 깊이 우선 알고리즘이다 BFS from collections..

DP의 정의 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 보다 큰 크기의 부분 문제를 해결 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해 상위 문제를 풀어가는 방식 즉 큰 문제를 풀기 위해 작은 문제를 풀어 큰 문제를 풀어가는 방식 DP 활용법 메모이제이션(탑다운 방식, 하향식) 메모이제이션 (memoization) 은 프로그램이 동일한 계산을 반복할 때 이전에 계산한 값을 메모리에 저장하여 동일한 계산의 반복 수행을 제거하여 프로그램의 실행 속도를 빠르게 하는 기법이다. 동적 계획법의 핵심이라고 할 수도 있다. 즉 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법으로 탑다운 방식이라고 불린다 (탑다운 방식: 큰 문..