Simple in Complex with Simple

1. 문제

 아래 문제를 5시간 안에 푸시오. (저작권 문제로 스크린샷 없애고, 글로 유사 문제로 변형)

각, 노드의 이름이 숫자가 아닌 문자열로 주어질 때의 문제이다.

예를 들어

GRB ADD 5란 입력은 GRB란 노드와 ADD란 노드의 거리는 5를 의미한다.

입력은 시작 노드와 종료 노드를 문자열로 입력한다.

실행 후 출력 방식은

시작 노드 -> 엣지 길이 -> 경유 노드 -> 엣지 길이 -> ... -> 끝 노드

이다.

다음에 데이터가 주어질 때, 

GRB ADD 5

GRB CDA 9

ADD CDA 1

ADD DFA 4

CDA ERD 5

CDA FRA 6

EDG DFA 3

DFA GONG 8

FRA GONG 7

시작노드와 끝 노드를 입력하면 출력하는 코드를 작성하시오.

아래 코드는 연결리스트 기반 Hash와 다익스트라 알고리즘의 조합으로 풀어냈다.

2. 코드

2-1) 구조체 선언

2-2) 해쉬 선언

2-3) 메인

2-4) 해쉬 함수들

2-5) 파일 해석 알고리즘

2-6) 다익스트라 알고리즘 

2-7) 출력

3. 해설

 이번 문제는 단순히 다익스트라 알고리즘만 필요한게 아닌 해쉬 기법과 파일 입출력 기법을 적절히 조정해야하는 문제다.

해쉬 기법은 정점의 이름과 번호를 매칭시키기 위해 사용하였다. 해쉬 키값은 각 정점 이름의 알파벳 아스키코드를 합친 후 

1차 해쉬 함수인 소수 17로 나눈 나머지이다. 그리고 위의 선언부의 Define 값에 따라 전체 계산 가능한 크기를 설정할 수

있다. 굳이 2차 해쉬 함수를 사용하지 않은 이유는 현재 데이터가 크지 않기 때문이다. 데이터가 커져서 만약 똑같은 해쉬

키값이 많이 등장한다면 2차 해쉬 함수를 고려해야할 것이다. 그리고 현재 코드는 기존에 잡아둔 최대 크기만큼 계산할 수

있으므로 한계가 있다. 이 한계를 수정하기 위해서는 크기에 따라 그래프의 Adj부분을 가변 배열로서 변한게 한다면 

가능하다. 하지만 그만큼 시간 소요가 된다. 이 방법이 현재 내 수준으로 가장 깔끔하고 빠르게 풀릴 것이라 생각한 방법이다.

더 좋은 방법들이 훨씬 많겠지만 추후에 새롭게 더 빠르게 할 수 있다면 다시 작성한다.

 그 당시의 나로서는 5시간에 풀어낸다는게 정말 엄두가 안났지만 공부하다보니 이제는 알겠다. 충분히 풀어낼 수 있는

문제였다는걸. 역시 모든 문제는 내 실력이다. 실력을 쌓자. 쌓다보면 날 알아주는 기업이 나타나겠지.

다음은 출력파일과 예시 그래프 데이터, 그리고 전체 코드이다. 혹시라도 도움이 될 수 있는 사람들을 위해.

[코딩인터뷰퀘스쳔].exe

graph.txt

Source.cpp

1. 개요

 이번 글에서는 드디어 내게 수많은 시련과 아픔을 줬던 알고리즘인 다익스트라 알고리즘을 작성한다. 다익스트라 알고리즘

은 방향성이 있고 가중치가 있는 그래프에서 노드에서 노드까지 최단 거리를 찾는 알고리즘이다. 이 알고리즘은 취업 관문

에서 2번이나 만나본 알고리즘이다. 최고의 게임 회사 중 하나에서 최종 코딩테스트에서 나온 문제이기도 하고 최고의 

소셜커머스 기업에서 코딩 문제로 나온 문제이기도 하다. 그리고 나는 나올 때 마다 풀긴 풀었는데 뭔가 미흡하게 풀었고

결과는 탈락이었다. 왜냐하면 그 당시의 나는 STL을 쓰지 않고 미련하게 모든 자료구조 하나하나 다 내가 만들어서 풀려고

했기 때문에 언제나 시간이 부족했다. 다익스트라 알고리즘의 특성상 우선순위 큐 만들기도 힘든데 그 제한 시간동안 우선

순위 큐인 힙을 만드는데 주어진 시간 대부분을 써버리고 정작 알고리즘에 넣어서 최종 테스트할 시간하기도 벅찼기 때문

이다. 그래서 이번 기회에 확실하게 정리해서 다시는 틀릴 일 없도록 머릿속에 담아둔다.

 다익스트라 알고리즘은 탐욕 알고리즘(Greedy Algorithm)을 사용한다. 탐욕 알고리즘이란 현재 상황에서 여러가지 경우가

있을 경우 그 순간의 최선의 선택을 하는 알고리즘이다. 그 순간 순간 최선을 선택해 결국 최종적으로 답을 도출하지만 

이렇게 얻은 문제의 답이 전체적으로 최선이라고 보장되지는 않는다.

 필요한 재료는 다음과 같다.

 (1) 시작 노드에서 각 노드들의 최단 거리를 기록하는 거리 배열(일차원 배열)

 (2) 시작 노드에서 끝 노드까지 경유한 노드를 기록하는 경로 배열(일차원 배열)

     ( 구조: Path[CurrentNodeIndex] = BeforeNodeIndex, 각 노드 인덱스의 배열값은 이전 노드 인덱스이다. )  

 (3) 우선순위 큐 (왜 일반 큐가 아닌 우선순위 큐일까?, 왜 음의 가중치는 안될까? (답은 해설에서))

 알고리즘은 다음과 같다.

 (1) 거리 배열을 -1로 초기화한다. (단, 시작점은 0으로 만든다. 0은 시작점, -1은 아직 계산 안한 노드 의미)

 (2) 경로 배열을 -1로 초기화한다. (단, 시작점은 0으로 만든다. 0은 시작점, -1은 이전 노드가 없다는 의미)

 (3) 현재 노드에서 연결된 노드들을 우선순위 큐에 넣는다. 우선순위 큐이므로 최단거리로 정렬된다.

     (시작점 일 경우, 시작 노드를 큐에 넣는다.)

 (4) 현재 노드와 연결된 노드들 사이의 최단거리를 찾아서 거리 배열과 경로 배열을 채운다.

 (5) (3) ~ (4)을 모든 노드를 방문할 때 까지 반복한다.

2. 문제

 다음 그림에서 다익스트라 알고리즘을 작성하시오. (STL 사용시 편함)

3. 코드

3-1) 메인

3-2) 다익스트라(Dijkstra Alg) 알고리즘

3-3) 경로추적 알고리즘

3-4) 출력

4. 해설

 드디어 다익스트라 알고리즘 정리가 끝났다. STL을 안썼을때는 코드가 그렇게 커졌는데 STL을 쓰기 시작하니

코드가 기하급수적으로 줄어든다. 참 편리하다. 지금 생각하면 아쉽다. 진작 STL 썼으면 최종 코딩 테스트에서

무난히 통과했을 것 같았는데, 괜히 무리하게 모든건 다 만들어서 하려고 했던 내가 미련스럽다. 하지만 그런

과정이 있었으니 지금 더욱 발전했겠지.

 다음은 해설이다.

 (1) 왜 우선순위 큐를 쓸까?

 결론적으로 말해서 최소거리 값 갱신 횟수의 증가때문이다. 먼저 우선순위 큐를 쓰지 않고 일반 큐를 써도 결과

에는 차이가 없다. 하지만 우선순위 큐를 쓰는 이유는 속도에 이점이 있기 때문이다. 다익스트라 알고리즘에서 

속도에 영향을 주는 요소는 큐에서 노드를 꺼내오는 횟수와 우선순위 큐의 갱신 횟수이다. 이게 무슨 뜻이냐면 

예를들어 보자. 만약 위의 예제에서 일반 큐를 쓴다면 A에서 검사를 시작할 때, 연결된 두 노드 B와 C중 B부터 

검사한다. 하지만 우선순위 큐라면 C부터 검사한다. 왜냐하면 우선순위 큐로 인해 최소 거리로 정렬된 순서로 

큐에서 추출되기 때문이다. 이 상황을 정리하면

A에서 E까지 최소거리를 검사할 때

일반 큐)

A -> B -> C -> E -> B -> D -> E -> E 순으로 검사

첫 번째 E 노드를 검사할 때, 현재 B까지 최소거리는 4, C까지 최소거리는 1, E까지 최소거리는 8이 된다.

하지만 그 다음 B노드를 검사할 때 B의 최소거리가 3으로 갱신되기 때문에 이전에 계산한 작업이 

무의미한 값이 된다. 이런 경우가 일반 큐를 사용할 때 나타나는 시간상의 비효율적인 대표 예이다.

우선순위 큐)

A -> C -> B -> B -> D -> E -> E -> E 순으로 검사

이 검사는 이전에 계산해둔 값이 그 단계에서 최소값이라는 것이 보장되기 때문에 갱신 횟수가 현저히 적어진다.

 이해를 돕기위한 작은 예지만 그래프의 크기가 커지면 커질수록 이런 일반 큐와 우선순위 큐 사이의 중복갱신

횟수가 일반큐가 월등히 많아지게 된다. 그러므로 최종적으로 일반 큐에서는 O(E+V^2)에서 우선순위 큐 사용 시

O(ElogV)으로 시간상의 이점이 발생하게 된다. (V는 정점 수, E는 엣지 수)

 (2) 왜 음의 가중치는 계산을 못할까? 

결론적으로 말해서 그 이유는 이전 노드까지 계산해둔 최소거리 값이 최소라고 보장할 수 없기 때문이다.

다익스트라는 정점을 지날수록 가중치가 증가한다 라는 사실을 전제하고 쓰여진 알고리즘이다. 하지만 음의

가중치가 있다면 정점을 지날수록 가중치가 감소할 수도 있다는 의미가 되므로 앞선 전제가 무너진다. 그러므로

다익스트라 알고리즘에서는 음의 가중치를 계산할 수 없다. 하지만 이와같은 점을 음의 가중치에서도 최소거리를

계산하는 벨만-포드 알고리즘이 존재한다.  

*현재 이 코드는 정점 이름을 숫자로 표기하면 상관없지만 고유 이름으로 나타낼 수 없다. (지명 이름을 표기하고 싶으면 추가 작업 필요)

1. 개요

 그래프 문제를 풀기 위해서는 그래프 운행을 위한 메커니즘이 필요하다. (일반 운행법으로는 풀 수 없다. 중요!) 이를 

그래프 탐색 알고리즘이라고 한다. 이에 관한 두 가지 기초이자 가장 중요한 알고리즘이 있다.

● DFS (Depth First Search) 깊이 우선 탐색

● BFS (Breath First Search) 넓이 우선 탐색

이다. 두 기법의 가장 큰 차이는 이렇다.

(1) DFS는 비밀이야기다. 한 번에 한 사람에게만 전해진다. BFS는 소문이다. 자기가 아는 모든 사람에게 전한다.

(2) DFS는 모든 노드를 탐색 후 자신에게 돌아와야 끝난다. BFS는 모든 노드를 탐색 후 끝난다.

(3) 두 기법다 매트릭스 그래프일 경우 시간복잡도는 O(V^2)이고, 인접리스트 기반일 경우 O(V+E)다.

(4) 무엇이 더 좋고 나쁜지는 없다. 찾으려는 데이터가 어디에 위치해있는지에 따라 다르다.

(5) DFS는 역추적 과정이 있어 스택 또는 리커젼을 사용. BFS는 현재 연결된 모든 노드를 차례대로 찾기에 큐를 사용.

2. 문제

 매트릭스 기법으로 최대한 간단하게 BFS 운행법을 코드로 작성하시오. (큐 사용)

 그래프의 모양은 다음과 같다.

3. 코드

3-1) 메인

3-2) 생성

3-3) BFS 알고리즘

3-4) 출력

      방문 순서만 출력

        방문 순서와 큐 내부 출력(이해돕기 위해)

4. 해설

 딱 2가지만 기억하자.

 (1) 스승님은 역시는 역시, 역시다.

 (2) BFS는 큐를 사용해서 연결된 순서대로 운행하는 알고리즘이다. 

1. 개요

 그래프 문제를 풀기 위해서는 그래프 운행을 위한 메커니즘이 필요하다. (일반 운행법으로는 풀 수 없다. 중요!) 이를 

그래프 탐색 알고리즘이라고 한다. 이에 관한 두 가지 기초이자 가장 중요한 알고리즘이 있다.

● DFS (Depth First Search) 깊이 우선 탐색

● BFS (Breath First Search) 넓이 우선 탐색

이다. 두 기법의 가장 큰 차이는 이렇다.

(1) DFS는 비밀이야기다. 한 번에 한 사람에게만 전해진다. BFS는 소문이다. 자기가 아는 모든 사람에게 전한다.

(2) DFS는 모든 노드를 탐색 후 자신에게 돌아와야 끝난다. BFS는 모든 노드를 탐색 후 끝난다.

(3) 두 기법다 매트릭스 그래프일 경우 시간복잡도는 O(V^2)이고, 인접리스트 기반일 경우 O(V+E)다.

(4) 무엇이 더 좋고 나쁜지는 없다. 찾으려는 데이터가 어디에 위치해있는지에 따라 다르다.

(5) DFS는 역추적 과정이 있어 스택 또는 리커젼을 사용. BFS는 현재 연결된 모든 노드를 차례대로 찾기에 큐를 사용.

2. 문제

 매트릭스 기법으로 최대한 간단하게 BFS 운행법을 코드로 작성하시오. (리커젼 사용)

 그래프의 모양은 다음과 같다.

3. 코드

3-1) 메인

3-2) 그래프 생성

3-3) DFS 알고리즘

3-4) 출력

4. 해설

 딱 2가지만 기억하자.

 (1) 스승님은 위대하다.

 (2) DFS는 시작위치에서 다시 시작위치로 돌아와야 끝나는 알고리즘이다.