김덕우

개발자로 취업하기 위해 거쳐야 할 필수 관문은 '코딩 테스트'다. 

개발자로 취업하고 싶은 비전공자로서 코딩 테스트를 어떻게 준비해야 할지 막막했다.

여러 후기를 검색한 결과, 

방법론 적으로는 의외로 단순했다. 

'시험에 자주 출제되는 문제'를 '스스로 고민'하여 '반복'적으로 푸는 것이었다. 

다시 키워드로 요약하자면,

1. 빈출 유형

2. 스스로 고민

3. 반복

이 세 가지다.

첫 번째로 맞닥드린 문제는, 어떤 유형의 문제가 자주 출제되는지 구별하는 안목이 없다는 점이다. 

그래서 이 책을 샀다.

굳이 책을 사지 않아도 코딩을 공부할 수 있는 환경이 인터넷에 잘 갖춰져 있긴 하다.

'백준'이나 '프로그래머스'와 같은 사이트에서 다양한 문제를 무료로 풀어볼 수 있기 때문이다.

하지만 나는 책으로 공부하는 것이 익숙하거니와,

이러한 사이트에 전적으로 의존하자니, 공부의 시작과 끝이 모호했다.

반면 책으로 공부하면 풀어야 할 문제가 딱 정해지므로 목표가 손에 잡히는 느낌이 든다.

대형 서점에 가보니 선택지가 두 개로 좁혀졌다.

하나는 '이것이 코딩 테스트다(나동빈/한빛미디어)'였고,

다른 하나는 '파이썬 알고리즘 인터뷰(박상길, 정진호 / 책만)'였다

후자를 선택했다. 그 이유 중 하나는 저자가 카카오 코딩 테스트 출제자였다는 점이다.

그만큼 책에 담긴 문제가 시험에 자주 나오는 유형이라고 추정할 수 있었다.

두 번째 문제는 '스스로 고민하기'가 어렵다는 점이다. 

파이썬에 대한 기초적인 지식만 있을  뿐,

자료구조와 알고리즘을 아예 처음 접하기 때문에 스스로 문제를 풀기가 힘들었다.

그래도 고민하는 시간에 비례하여 실력이 는다는 생각에,

도저히 모를 법한 문제도 최소한의 시간 (20~30분) 동안 고민을 해보고 해답을 읽었다. 

이 책은 해설이 비교적 쉽게 쓰인 편이라 모르는 문제를 이해하기가 수월했다.

또한 한가지 문제를 놓고 여러가지 풀이 방법을 알려주기 때문에,

문제를 다양한 방식으로 고민할 수 있었다.

다만, 완전 초보의 입장에서 이해가 안 되는 해설 내용도 많았다.

그럴 때마다 유튜브로 부족한 개념을 따로 보충했다.

'코드 없는 프로그래밍'이라는 유튜브 채널을 자주 참고했다.

그림을 그려가며 개념을 설명하기 때문에 문제에 접근하는 방식을 직관적으로 이해할 수 있었다.

마지막 문제는 '얼마나 많은 문제를 얼마나 반복해서 풀어야 할까'라는 점이다. 

솔직히 나도 정답을 모르겠다.

다만 이 책에는 총 100문제가 수록되어 있으며,

모든 문제의 풀이 방법을 응용할 수 있을 정도로 숙지한다면,

카카오 코딩 테스트 문제를 풀어내는데 크게 부족함이 없을 것 같다는 것이 내 추측이다.

(물론 이 책과 카카오 기출문제에 대한 짧은 분석으로 내린 결론이다.)

'몇 번을 반복해서 풀 것이냐'하는 문제는 개인마다 다를 것이다.

나의 경우 같은 문제를 최소 세 번은 풀어봐야 감이 좀 잡혔다.

문제에 대한 접근 방식이 몸에 충분히 녹아들어서, 자유롭게 응용이 가능한 수준에 이르려면

세 번도 부족하다는 생각이 든다.

이 책은 리트코드(LeetCode)의 문제를 수록했기 때문에,

책에 실린 문제를 온라인 환경에서 직접 풀어볼 수 있다.

하지만 정말 이해가 안 되는 문제는 손으로 코드를 쓰거나 그림을 그려가며 풀기도 한다.

코딩 테스트는 시험이다. 

모든 시험에는 전략적 접근이 필요하다. 

개인마다 적합한 전략이 모두 다르겠지만,

이 책을 활용해보는 방법도 고민해볼 가치가 있다고 본다.

트리는 그래프(graph)의 한 종류다.

또한 위 그림에서 보듯이 계층형 자료구조다.

그러면  트리와 그래프와 차이점은 무엇일까?

우선 트리는 순환 구조를 가지지 않는다. 트리는 위 그림과 같은 연결구조를 가질 수 없다

그래프는 위 그림과 같은 양방향(Uni-directional) 및 단방향(Bi-directional) 구조 모두 가능하지만,

트리는 단방향 구조만 가능하다.

트리는 위 그래프 처럼 루트 노드를 두개 이상 가질 수 없고,

한 노드가 두 개 이삳의 부모 노드를 가질 수 없다.

'루트 노드'나 '부모 노드'와 같은 명칭에 익숙하지 않을 수도 있다.

트리를 대표적인 명칭은 아래와 같다.

맨 윗단에 있는 노드를 '루트(Root)노드', 맨 아랫단에 있는 노드를 '리프(Leef)노드'라고 한다. 

그리고 위-아래로 연결된 노드를 각각 '부모', '자식 노드'라고  부른다. 

'차수'는 부모노드가 가지는 자식 노드의 개수를 말한다.

'크기'는 부모 노드와 자식 노드를 합한 개수이다.

'레벨'은 맨 윗층부터 0, 1, 2 순서대로 분류된다.

'깊이'는 루트 노드를 기준으로 현재 노드의 위치를 말하며,

'높이'는 리프 노드를 기준으로 현재 노드의 위치를 나타낸다.

마지막으로  이진트리(Binary Tree)의 종류에 대해서 알아보겠다.

(이진트리는 다진트리 중 자식 노드의 개수가 2개 이하인 노드를 지칭하는 말이다)

1. 정 이진 트리(Full Binary Tree)는 모든 노드가 0개 또는 2개의 자식 노드를 가지고 있는 경우를 말한다.

2. 완전 이진 트리(Complete Binary Tree)는 마지막 레벨을 제외하고 모든 레벨에 노드가 완전하게 채워졌으며,

마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있다.

3. 포화 이진 트리(Perfect Binary Tree)는 모든 노드가 2개의 자식을 가지고 있으며,

모든 리프 노드가 동일한 깊이, 레벨에 위치하는 구조를 말한다.

본 글은 '파이썬 알고리즘 인터뷰(박상길 / 책만)'의 내용을 정리한 내용입니다.

최단 경로 문제는 시간 또는 비용의 합이 최소가 되는 경로를 찾는 문제다.

회사에서 편의점을 거쳐서 오면 1시간이 걸리고,

회사에서 헬스장을 가쳐서 오면 1시간 30분이 걸린다면,

편의점을 거쳐 집으로 오는 길, 즉 제일 빠른 길 탐색하는 문제다. 

코딩 테스트에서 최단 경로 문제는 주로 다익스트라 알고리즘으로 구현한다.

다익스트라 알고리즘은 정점(vertex) 주변의 최단 경로만 택하는 알고리즘이다.

단순할 뿐만 아니라 실행 속도도 빠른 장점이 있다. 

'회사'를 정점으로 하면 주변은 헬스장과 편의점이 있고 최단 경로는 편의점으로 가는 길인 셈이다.

다익스트라 알고리즘은 너비우선탐색(BFS)를 이용하는 대표적 알고리즘이다. 

허접하게 비유하자면,

회사에서 편의점을 거쳐 집까지 쭉 판 다음, 헬스장에 간다면 깊이 우선 탐색(DFS)이고,

편의점과 헬스장을 차례로 거친 다음, 집을 탐색한다면 너비 우선 탐색(BFS)이다.

다익스트라 알고리즘의 기본 메커니즘은 동영상으로 설명하는 게 가장 이해가 잘 되었다. 

추천 영상을 링크를 아래에 붙인다.

https://www.youtube.com/watch?v=qaiuC3Q73-M

그러면 본격적으로 리트코드 743번 '네트워크 딜레이 타임' 문제를 다익스트라 알고리즘으로 풀어보자

참고로 문제 자체가 좀 어려워서 이해하는 데 한참 걸렸다.

아래 그림을 통해 보면,

2번 노드(변수 K)에서 출발하여 화살표 방향으로 신호를 보내는 데,

화살표 위에 숫자만큼 시간이 걸린다.

모든 노드가 신호를 받을 때 걸리는 최소 시간을 구하는 문제다

(계산이 불가능할 경우 -1을 리턴한다)

결론부터 말하면 정답은 '2'다

입력값과 출력값은 아래와 같다.

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

times 변수에 할당된 2차원 리스트의 요소들( [ u,  v, w ] )에서,

u는 출발 노드

v는 도착 노드

w는 걸리는 시간이다.

예를 들어, [ 2, 1, 1 ]은 2번 노드에서 1번 노드까지 '1'이라는 시간이 걸린다는 말이다.

또 다른 입력값 n은 노드의 개수(위 예제에서는 4개)를 뜻하고,

k는 출발 노드(위에서 2번)이다.

문제 풀이는 우선순위 큐를 사용한다. 구체적으로 한번 살펴보자

1. 우선 함수를 정의하고 그래프의 인접 리스트를 구성한다

변수 'items'의 자료형을 리스트에서 딕셔너리로 바꿔주기 위해서,

defualtdict 객체를 생성한다.

출발 노드(u)를 키(key)로, 

도착 노드 및 소요 시간(v, w)을 값(value)으로 하는 딕셔너리 형태로 변환한다. 

참고로 times 리스트를

딕셔너리 형태로 변환하면 출력 값은 아래와 같이 변한다.

2. 힙큐 리스트를 정의한다.

참고로 Q = [ ( 소요 시간, 정점) ] 구조이다.

앞으로 최단 경로를 채워나갈 리스트라고 보면 된다.

3. 변수 'dist'에  딕셔너리를 새로 정의한다.

'dist'는 추후 모든 경로에 대해서 최단 경로가 존재하는지 유무를 판단하고,

존재할 때 걸리는 시간을 도출하는 데 사용된다

4. 각 정점까지 최단경로를 구해서 dist에 삽입한다. min heap을 기준으로 적용한다.

우선 Q(min heap)가 빌 때까지 반복 연산을 하기 위하 while문을 이용한다.

heappop 메서드를 이용하여 최소 시간이 걸리는 노드를 우선적으로 추출한다.

추출된 노드가 dist에 없다면,

그런 다음 이동할 노드(node)와 소요시간(time)의 위치를 서로 바꾸어 'dist'에 저장한다.

그런 다음 'for 문'을  이용하여,

추출된 노드와 연결되는 다른 노드들을 heapq에 올려준다.

다시 heapq에서 최소 시간이 걸리는 노드를 추출하는 방식으로 노드가 반복된다.

위 과정을 그림으로 나타내면 다음과 같다.

모든 노드의 시간이 1이기 때문에,

heap에서 추출된 값이 heap에서 추가됐던 순서대로

dist에 옮겨진다.

만약 노드마다 시간이 다르다면,

시간이 제일 짧은 노드 먼저 추출되어 dist로 옮겨질 것이다.

5. 모든 경로가 최단 경로에 포함되는지 여부를 판단하고 최대 시간을 출력한다.

앞서 말했듯이 N은 전체 노드의 개수다.

dist의 길이가 N과 같다는 말은 모든 노드가 디스트로 다 옮겨졌다(최단 경로에 포함되었다)는 말이다.

조건이 성립할 경우, dist의 값(value) 중 최대 값을 리턴한다. 

이 값이 곧 모든 노드에 신호를 보내는 데 소요되는 시간이다.

위 조건을 충족하지 못한다면 -1을 리턴한다.

* 위 내용은 '파이썬 알고리즘 인터뷰(박상길 / 책만)의 해설을 토대로 작성했습니다.