[알고리즘] 그래프
그래프
- 노드(vertex)와 간선(edge)의 집합
- 간선 $e = (u, v)$ 에서 u는 소스(source)노드, v는 싱크(singk)노드 라고 한다.
- 비순환 방향 그래프에서는 유입 간선이 없는 노드를 소스라 하고,
- 유출 간선이 없는 노드를 싱크라 한다.
- 간선에 길이를 추가하거나, 노드에 가중치를 추가할 수 있다.
- 그래프는 인접 리스트 혹은 인접 행렬로 표현할 수 있다.
알아야 할 내용
- 공간상에서 객체가 연결되어 있는 문제는 그래프를 이용한다.
- 객체 간의 이진 관계를 분석할 때 유용
- DFS, BFS를 이용해 탐색하는 경우 복잡도는 O(V + E)이다.
- BFS는 시작 지점에서 거리 계산에 사용하고, DFS는 사이클이 존재하는 지 확인할 때 유용하다
고급 그래프 알고리즘
- 다항 시간(polynomial time)에 복잡한 그래프 문제를 효율적으로 풀 수 있는 네 가지 방법이 있다.
- 다항 시간 : n^2 같은..
- 지수 시간 : 2^n 같은..
- 대부분의 그래프 문제는 이들의 변형이거나, 다항 시간 알고리즘으로 풀지 못하는 문제이다.
최단 경로
- 간선에 비용이 포함된 방향 혹은 무방향 그래프가 주어졌을 때, 주어진 노드에서 모든 노드로의 경로 중 최소 비용의 경로를 구하라.
- 비용이 음이 아닌 정수인 경우에 모든 노드 쌍에 대한 최단 비용 경로를 찾는 문제도 있다.
최소 신장 트리(MST)
- 간선에 가중치가 실려 있는 연결된 무방향 그래프가 주어졌을 때 가중치가 최소가 되는 간선의 부분 집합으로 이뤄진 부분 그래프를 구하라.
매칭
- 무방향 그래프가 주어졌을 때, 각 노드의 연결된 간선이 최대 한 개인 조건에서 최대한 많은 간선의 컬렉션을 찾아라.
- 응용 문제로 최대 가중치 매칭 문제가 있다.
최대 흐름
- 간선에 용량이 표시된 방향 그래프가 주어졌을 때, 소스 노드에서 싱크 노드로 흐를 수 있는 최대 흘름을 구하라.
그래프의 표현
에지 리스트
- edge list는 에지를 중심으로 그래프를 표현한다. 배열에 출발 노드를, 도착 노드를 저장하여 에지를 표현한다.
- 또는 출발노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현한다.
- 에지 리스트는 구현하기 쉽지만 특정 노드와 관련된 에지를 탐색하기는 쉽지 않다.
- 노드 사이의 최단 거리를 구하는 벨만-포드나 최소 신장 트리를 찾는 크루스칼 알고리즘에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않는다.
인접 행렬
adjacency matrix는 2차원 배열을 자료구조로 이용하여 그래프를 표현한다. 에지 리스트와 다르게 노드 중심으로 그래프를 표현한다. 인접 행렬을 이용한 그래프 구현은 쉽다. 두 노드를 연결하는 에지의 여부와 가중치값은 배열에 직접 접근하면 바로 확인할 수 있는 장점이 있다. 하지만 노드와 관련되어 있는 에지를 탐색하려면 N번 접근해야 하므로 시간 복잡도가 인접 리스트에 비해 느리고 노드의 개수에 비해 에지가 적을 때는 공간 효율성이 떨어진다.
가중치 없는 그래프
노드의 개수가 N일 때, N * N 배열을 생성한다. 1에서 2를 향하는 에지는 A[1][2]에 1을 저장하는 식으로 표현한다.
가중치 있는 그래프
2에서 5를 향하는 에지는 A[2][5]에 3을 저장하는 식으로 한다.
인접 리스트
- C++의 인접 리스트는 이차원 벡터로 그래프를 표현한다.
- 하지만 노드와 연결된 에지를 탐색하는 시간은 매우 뛰어나며, 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러도 발생하지 않는다.
- 실제 코테에서는 인접 리스트를 이용한 그래프 구현을 선호한다.
가중치 없는 그래프
vector<vector
가중치 있는 그래프
가중치가 있을 경우 pair클래스를 이용하여 표현한다.
typedef pair<int, int> Node;
vector<vector<Node>> A;
노드 1과 2가 가중치 8 에지로, 노드 1과 3이 가중치 3에지로 연결되어 있다면, A[1]에 [(2,8), (3,3)]으로 표현한다.
1. 미로 찾기
풀이 방법
- BFS 나 DFS로 해결하기
2. 불 행렬 색칠하기
풀이 방법
- 시작 노드가 여러개인 경우 BFS가 좀 더 낫다.
3. 닫힌 지역 찾기
풀이 방법
- 모서리에 닿은 지점을 모두 없애고 BFS
4. 데드락 찾기
- 방향 그래프가 주어졌을 때 해당 그래프에 사이클이 포함되어 있는 지 확인하는 프로그램을 작성하라
풀이 방법
- ‘뒷’ 간선에 집중한다.
- DFS를 통해 사이클이 존재하는지 확인한다.
- 이미 방문한 노드를 다시 방문하는 경우에 사이클이 있다고 리턴해도 되고,
- 스택이 노드의 개수를 넘어서면 사이클이 있다고 볼 수도 있다.
5. 그래프 복제하기
6. 와이어로 회로 연결하기
- ??
7. 문자열을 다른 문자열로 바꾸기
- 문자열 s가 주어졌을 때 s에서 시작해 인접한 문자열의 길이는 같고 오직 하나의 문자만 다른 경우 s에서 다른 문자열을 생성했다고 한다.
- 사전 D와 문자열 s,t가 주어졌을 때 s에서 t를 생성할 수 있는 지 확인하는 프로그램을 작성하라.
풀이 방법
- 문자열을 무방향 그래프의 노드라 생각하고, 문자열 u와 v의 문자 차이가 하나일 때 간선을 연결한다.
특정 거리의 도시 찾기
단방향, n개의 도시, m개의 단방향 도로, 모든 도로의 거리는 1이다. 도시 x로 부터 출발해 도달할 수 있는 모든 도시 중 최단 거리가 k인 모든 도시들의 번호 출력하기.
이분 그래프 판별하기
각 집합에 속한 노드끼리 서로 인접하지 않는 두 집합으로 그래프의 노드를 나눌 수 있을 때 이 그래프를 bipartite graph(이분 그래프)라고 한다.
트리는 항상 이분 그래프가 된다. 즉, 사이클이 발생하지 않아야 함. 기존 탐색 매커니즘에서 탐색한 노드에 다시 접근하게 됐을 때 현재 노드의 집합과 같으면 이분 그래프가 불가능하다는 것을 판별할 수 있다.
물의 양 구하기
각각 부피가 A, B, C(1≤A, B, C ≤200)리터인 3개의 물통이 있다. C만 가득 차있고 나머지 두 물통은 비어 있다. 어떤 물통에 들어 있는 물을 다른 물통으로 쏟아부을 수 있는데 이 때는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 부을 수 있다. 1번째 물통이 비어 있을 때, 3번째 물통에 담겨 있을 수 있는 물의 양을 모두 구하는 프로그램을 작성하라
ex) 8, 9, 10 일 때 답은 1, 2, 8, 9, 10
문제 분석하기
그래프 원리를 적용해 그래프를 역으로 그리는 방식으로 접근해야 한다. A, B, C의 특정 용량 상태를 1개의 노드로 가정하고, 조건에 따라 이 상태에서 변경할 수 있는 이후 용량 상태가 에지로 이어진 인접한 노드라고 생각하고 문제에 접근해 보자.
풀어보기
유니온 파인드
union-find는 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union연산 과 두 노드가 같은 집합에 속해 있는 지를 확인하는 find연산으로 구성된 알고리즘이다.
핵심 이론
- union 연산: 각 노드가 속한 집합을 1개로 합치는 연산이다. union(a, b)는 A U B를 말한다.
- find 연산: 특정 노드 a가 속한 집합의 대표 노드를 반환하는 연산이다. find(a)는 A 집합의 대표 노드를 반환한다.
원리
- 일반적인 방법은 1차원 배열을 이용하는 방법이다. 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 된다. 각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스 값으로 초기화한다. A[1] =1, .. A[N] = N.
- 이후 1, 4 와 5, 6을 union 연산하고 4와 6을 union 연산하면, 유니온 파인드 배열은 {1, 2, 3, 1, 1, 5}가 된다.
- find 연산은 대표노드를 찾는 역할만 하는 것이 아니라 그래프를 정돈하고 시간 복잡도를 줄여준다.
- 작동 원리
- 대상 노드 배열에 index값과 value값이 동일한지 확인한다.
- 동일하지 않으면 value값이 가리키는 index 위치로 이동한다
- 이동위치의 index값과 value 값이 같을 때까지 반복한다.
- 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 대표 노드값으로 변경한다.
- 작동 원리
최종적으로 {1, 2, 3, 1, 1, 1} 이 된다. 이러면 추후 노드와 관련된 find 연산 속도가 O(1)로 변경된다.
집합 표현하기
초기에 {0}, {1}, … {n}이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과 두 원소가 같은 집합에 포함돼 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작성하라
합집합은 0 a b 의 형태, 두 원소가 같은 집합에 포함돼 있는지를 확인하는 연산은 1 a b 형태로 입력이 주어진다.
자주 실수하는 부분!!
find 연산 수행 시 재귀 함수에서 나오면서 탐색한 모든 노드의 대표 노드값을 이번 연산에서 발견한 대표 노드로 변경하는 부분과 union 연산에서 선택된 노드끼리 연결하는 것이 아닌 선택된 노드의 대표 노드끼리 연결하는 부분이 유니온 파인드에서 가장 많이 실수하는 부분이다.
여행 계획짜기
- 도시의 개수와 도시 간의 연결 여부가 주어져 있다. 여행 계획이 주어졌을 때 이 계획대로 도시들을 순차적으로 방문할 수 있는가
거짓말쟁이가 되긴 싫어
- 사람의 수, 파티의 수, 이야기의 진실을 아는 사람의 수와 번호가 주어진다.
- 모든 파티에 참가할 때 거짓말쟁이로 알려지지 않으면서 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하라
위상 정렬
topology sort(위상 정렬)는 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 노드 간의 순서를 결정하며, 시간 복잡도는 O(v + e) 이다. 위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다. 또한 사이클이 존재하면 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없다.
핵심 이론
원리 이해하기
- in-degree(진입 차수)는 자기 자신을 가리키는 에지의 개수이다.
- 진입 차수 배열을 생성한다. 만약 vector<vector
> A {2, 3},{4,5},{4},{5},{}} 라면, 진입차수 배열 D[N] 은 {0, 1, 1, 2, 2} 이다. - 진입 차수 배열에서 진입 차수(배열의 value)가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다. 이 과정을 반복하여 모든 노드가 정렬되게 한다. 두 번째 진입 차수가 0인 노드를 고를 때 2 또는 3 노드를 고를 수 있으므로 유일한 값으로 정렬되지 않는 다고 볼 수 있다.
줄 세우기
- 일부 학생들을 둘씩만 키를 비교한 결과가 주어졌을 때 키 순서대로 줄을 세운 결과를 출력하라.
게임 개발하기
어떤 건물을 짓기 위해서는 다른 건물을 먼저 지어야 할 수도 있다. 여러 개의 건물을 동시에 지을 수 있다. N개의 건물을 지을 때 각 건물을 짓기 위해 필요한 최소 시간을 출력하라.
건물의 종류 수 N, 그 다음 N개의 줄에 각 건물을 짓는 데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어야 하는 건물들의 번호가 주어진다.
임계 경로 구하기(나중에 추가)
- 플레티넘 문제니까 나중에 꼭 보자
다익스트라
- dijkstra 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.
- 출발 노드와 모든 노드 간의 최단 거리를 탐색하며 에지는 모두 양수여야 하고, 시간 복잡도는 O(ElogV) 이다.
- 특정 노드에서 다른 노드들의 최단 거리를 구하는 문제에서 사용하면 된다.
핵심 이론
- 인접 리스트로 그래프 구현한다. 인접행렬로 해도 좋지만 시간 복잡도 측면과, N의 크기가 클 것을 대비해 인접 리스트로 연습해 두자.
- 최단 거리 배열을 초기화하는데, 출발 노드는 0 이외의 노드는 무한으로 초기화한다.(적당히 큰 수)
- 최단 거리 배열에서 현재 값이 가장 작은 노드를 고른다. 처음은 0인 출발 노드겠죠
- 선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값을 업데이트하여 최단 거리 배열을 업데이트 한다.
- 출발노드와 도착 노드간의 최단거리만을 구하는 알고리즘이 아닌, 출발 노드에서 다른 모든 노드 간의 최단 거리를 표현한다는 점에 유의하자!
- 활용할 수도 있다.
- 최단 경로를 계속 뽑기 위해 priority_queue를 사용해 준다.
priority_queue<edge, vector<edge>, greater<edge>>
최단 경로 구하기
에지의 가중치가 10 이하의 자연수인 방향 그래프가 있다. 이 그래프의 시작점에서 다른 모든 노드로의 최단 경로를 구하라.
최소 비용 구하기
- N개의 도시와 한 도시에서 출발해 다른 도시에 도착하는 M개의 버스가 있다.
- A 도시에서 B 도시까지 가는 데 드는 최소 비용 구하라.
K번째 최단 경로 찾기
1번째 줄에 n,m,k가 주어진다. n과 m은 여행을 고려하고 있는 도시들의 개수와 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에는 각각 도로의 정보를 제공하는 3개의 정수 a, b, c가 포함돼 있다. a번 도시에서 b번 도시로 갈 때 c의 시간이 걸린다는 의미다.
풀이 방법
- 최단 경로를 표현하는 배열을 우선순위 큐 배열(크기는 K)로 변경하면, 최단 경로뿐 아니라 최단 경로 ~ K번째 최단 경로까지 표현이 가능하다.
- 이 경우 K번째 경로를 찾기 위해서는 노드를 여러 번 쓰는 경우가 생기기 때문에 방문은 체크하지 않는다.
- 현재 노드에 저장된 경로가 K개 미만일 때 신규 경로를 추가한다
- 경로가 K개일 때 현재 경로 중 최대 경로와 신규 경로를 비교해 신규 경로가 더 작을 때 업데이트 한다.
벨만-포드
- bellman-ford-moore 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다. 특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 탐색한다.
- 음수 가중치 에지가 있어도 수행이 가능하며, 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다.
- 시간 복잡도는 O(VE)이다.
핵심 이론
- 에지 리스트로 그래프를 구현하고 최단 경로 배열 초기화한다. 벨만-포드 알고리즘은 에지를 중심으로 동작하므로 그래프를 에지 리스트로 구현한다. 최단 경로배열을 출발 노드는 0, 나머지 노드는 무한대로 초기화 한다. 에지는 일반적으로 노드 변수 2개와 가중치 변수로 구성돼 있다.
- 모든 에지를 확인하며 정답 배열을 업데이트 한다. 최단 거리 배열에서 업데이트 반복 횟수는 노드 개수 -1 이다. 노드 개수가 N이고, 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수는 N-1이기 때문이다. 모든 에지 E = (s, e, w)에서 다음 조건을 만족하면 업데이트를 실행한다. 업데이트 반복 횟수가 K번이라면 해당 시점에 정답 배열의 값은 시작점에서 K개의 에지를 사용했을 때 각 노드에 대한 최단 거리이다.
업데이트 조건과 방법
D[s] ≠ 무한대 이며, D[e] > D[s] + w 일 때 D[e] = D[s] + w 로 배열의 값을 업데이트 한다.
음수 사이클이 없을 때 N -1번 에지 사용 횟수를 반복하면 출발 노드와 모든 노드 간의 최단 거리를 알려 주는 정답 배열이 완성된다.
- 음수 사이클 유무를 확인하기 위해 모든 에지를 한 번씩 다시 사용해 업데이트되는 노드가 발생하는지 확인한다. 만약 업데이트 되는 노드가 있다면 음수 사이클이 있다는 뜻이 되고, 2단계에서 도출한 정답 배열이 무의미하고 최단 거리를 찾을 수 없는 그래프라는 뜻이 된다. 음수 사이클을 돌면 최단거리가 점점 줄어들어 정답이 무의미 해진다.
타임머신으로 빨리 가기
N개의 도시, M개의 버스 노선의 개수, 버스 노선의 정보 A, B, C(C는 음수 가능). A에서 B로 가는 데 C 시간이 소요된다. 1번 도시에서 출발해 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하라
먼저, 에지가 음수가 가능하므로 벨만-포드 알고리즘을 사용하면 된다. 에지 리스트에 에지 데이터를 저장한 후 거리 배열을 초기화 한다. 이후,
- 모든 에지와 관련된 정보를 가져온 후 다음 조건에 따라 거리 배열의 값을 업데이트 한다.
- 출발 노드가 방문한 적이 없는 노드 (출발 노드 거리 == INF)일 때 값을 업데이트 하지 않는다.
- 출발 노드의 거리 배열값 + 에지 가중치 < 종료 노드의 거리 배열값 일 때 종료 노드의 거리 배열값을 업데이트 한다.
- 노드 개수 -1 번만큼 위를 반복한다.
- 음수 사이클 유무를 알기 위해 모든 에지에 관해 1을 다시 수행한다. 이 때 한번이라도 값이 업데이트 되면 음수 사이클이 존재한다고 판단한다.
- 음수 사이클이 존재하면 -1, 존재하지 않으면 거리 배열의 값을 출력한다. 단, 거리 배열의 값이 INF일 경우 -1을 출력한다
세일즈맨의 고민
- A 도시에서 시작해 B 도시에서 끝나는 출장으로 최대한 많은 돈을 구하려 한다.
- 교통수단의 출발 도시와 도착 도시, 비용, 그리고 각 도시에서 벌 수 있는 돈이 주어진다.
- 같은 도시를 여러 번 방문해도 된다. 교통수단 또한 여러 번 이용할 수 있다.
- 돈의 액수는 음수가 될 수도 있다.
해결 방법
- 이때는 양수 사이클의 존재 유무를 검사해야 한다.
플로이드-워셜
- floyd-warshall(플로이드-워셜) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.
- 모든 노드 간에 최단 경로를 탐색하며,
- 음수 가중치 에지가 있어도 수행이 가능하며,
- 동적 계획법 원리를 이용해 알고리즘에 접근한다.
- 시간 복잡도는 O(V^3)이다.
핵심 이론
A노드에서 b노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것이다. 이 원리로 다음과 같은 점화식을 도출할 수 있다. D[S][E] = min(D[S][E], D[S][K] + D[K][E])
- 배열을 선언하고, s와 e의 값이 같은 칸은 0, 나머지 칸은 무한대로 하여 D[S][E]로 최단거리 배열을 초기화 한다.
- 최단 거리 배열에 그래프 데이터를 저장한다.
- 점화식으로 3중문의 형태로 배열을 업데이트 한다.
시간 복잡도가 느린 편이므로 이 알고리즘을 사용해야 하는 문제는 일반적으로 노드 개수의 범위가 적다.
가장 빠른 버스 노선 구하기
n개의 도시, m 개의 버스, a 도시에서 b 도시로 가는데 비용 c가 주어 질때, 모든 도시의 쌍 (A, B)에 관해 필요한 비용의 최솟값을 구하는 프로그램을 작성하라
경로 찾기
- 가중치 없는 방향 그래프가 주어졌을 때 모든 노드(i, j)에 관해 i에서 j로 가는 경로가 있는 지 여부를 구하라
풀이 방법
- 최단 거리 업데이트 해줄 필요 없고,
- 방문 가능하면 가능하다고만 업데이트 해주게 변경해주면 된다.
케빈 베이컨의 6단계 법칙
최소 신장 트리
- minimum spanning tree란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다.
- 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클은 포함하지 않는다.
- N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1이다.
핵심 이론
- 에지 리스트로 그래프를 구현하고, 사이클 처리를 위한 유니온 파인드 배열도 초기화 한다.
- 그래프 데이터를 가중치 기준으로 오름차순 정렬한다. 이 때 객체를 구조체로 표현하면 operator() 함수를 사용해 높은 자유도로 정렬을 수행할 수 있다.
- 가중치가 낮은 에지부터 연결을 시도한다. 에지 연결 시 사이클 형성 여부를 find 연산을 통해 확인한 후 사이클 형성이 되지 않을 때만 union 연산을 이용해 두 노드를 연결한다.
- 가중치가 낮은 에지는 우선순위 큐로 뽑으면 편하다.
- 과정 3을 반복하다 연결한 에지의 개수가 N-1이 되면 멈춘다.
- 완성된 최소 신장 트리의 총 에지 비용을 출력한다.
struct Edge {
int s, e, v;
bool operator > (const Edge& temp) const {
return v > temp.v;
}
};
최소 신장 트리 구하기
- 노드와 에지, 가중치가 주어질 때 그래프의 최소 신장 트리의 가중치를 출력하라
다리 만들기
- 2차원 배열에 섬으로 나눠진 나라가 있다.
- 각 섬을 다리로 연결해 모든 섬을 잇는 다고 할 때, 다리 길이의 최솟값을 구하라.
- 다리가 겹칠수도 있지만 이 경우 겹치는 길이를 빼지는 않는다.
- 다리의 길이는 2 이상이여야 하고, 다리의 방향이 중간에 바뀌면 안된다.
풀이 방법
- BFS를 통해 섬을 구분한다.
- 모든 섬에서 상하좌우 다리를 지어 다른 섬으로 연결할 수 있는 지 확인한다.
- 현재 섬이면 탐색 중단, 바다면 계속 수행
- 2에서 구한 에지들을 오름차순으로 정렬해 최소 신장 트리 알고리즘을 수행한다.
불우 이웃 돕기
- 컴퓨터는 서로 연결되어 있거나, 다른 컴퓨터를 통해 연결돼 있으면 서로 통신이 가능하다.
- N개의 컴퓨터가 서로 연결돼 있는 랜선의 길이가 주어졌을 때, 제외할 수 있는 랜선의 길이의 최댓값을 구해라
풀이 팁들 모음
가장자리에 닿지 않는 섬들 면적 모음
- 가장자리를 먼저 훑으면서 만나는 섬은 다 빼고 난뒤,
- 섬 개수 혹은 면적 구하면 됨
방향있는 간선 그래프에서
‘266가지 문제로 정복하는 코딩 인터뷰 - 아다드 아지즈, 쭝시엔 리, 아트 프라카시 지음 - 이창현, 김현욱 옮김’,
‘알고리즘 코딩테스트-c++편, 김종관 지음’ 책을 참고하여 작성한 포스트입니다.
Leave a comment