트리 순회는 그래프 순회의 일종으로,

 

트리 자료구조에서 각 노드를 한 번 방문하는 과정을 말한다.

 

DFS 또는 BFS로 탐색 하는데,

 

이진 트리에서 DFS는 노드의 방문 순서에 따라 크게 3가지 방식으로 구분된다.

 

1. 전위(Pre-Order) 순회(NLR)

현재 노드(N) -> 왼쪽 서브트리(L) -> 오른쪽 서브트리(R) 순서대로 탐색하는 방식이다

 

재귀 구조로 구현한 코드와 그래프는 아래와 같다

 

 

Pre-Order 순회

 

빨간색 선으로 이어진 순서대로(A - B - D - F - H - I -C -G -J ) 값이 출력된다.

 

 

2. 중위(In-Order) 순회

 왼쪽 서브트리(L) -> 현재 노드(N) -> 오른쪽 서브트리(R) 순서대로 탐색하는 방식이다.

In-Order 순회

출력 순서는 D - B - G -E -H - A -C - I -F 이다

 

 

3. 후위(Post-Order) 순회

왼쪽 서브트리(L) -> 오른쪽 서브트리(R) -> 현재 노드(N) 순서대로 탐색하는 방식이다.

 

Post-Order 순회

출력 순서는 D - G - H - E - B - I - F -C -A 순서이다.

 

 

 

트리 순회의 직관적인 이해가 필요한 사람은 아래 영상을 참조해도 좋겠다.

https://www.youtube.com/watch?v=bOZhvOc5xlQ&t=223s

 

1. 저장 장치 종류

저장 장치는 크게 두 종류가 있다.

 

우리가 흔히 '메모리'라고 부르는 주기억 장치(Primary Memory)

 

'하드 디스크'라고 부르는 보조기억 장치(Secondary Memory)가 있다.

 

 

 

'메모리'는 속도가 빠른 반면, 저장할 수 있는 용량이 작다.

 

반대로 하드 디스크는 속도가 느리지만 저장 공간이 크다.

 

이처럼 저장 장치는 속도와 용량 간 상충관계를 지니며,

 

속도와 용량에 따라 계층 구조를 가진다.

 

 

 

 

2. 저장 장치의 계층구조

 

 

위 그림은 저장 장치의 계층 구조를 보여준다.

 

위로 갈수록 속도는 빠르지만 용량은 적은 저장 장치를 나타낸다. 

 

자세히 보면 '주기억장치' 내에서도 계층이 세 가지로 나뉘는 것을 볼 수있다.

 

레지스터캐시 메모리는 CPU에 위치하며, 일반적인 메모리보다 속도가 빠르며 용량이 적다.

 

 

 

 

3. 캐싱 기법

일반적으로 매우 자주 사용되는 데이터가 있는 반면, 거의 사용되지 않는 것도 있다.

 

자주 사용되는 정보를 상대적으로 느린 저장장치(ex.메모리)가 아닌, 빠른 저장장치( ex. 캐시)에 저장하면, 

 

해당 정보를 곧바로 찾을 수 있기 때문에 전체적으로 컴퓨터 성능이 향상될 수 있다.

 

이처럼 용량이 적고 빠른 저장장치를 이용해 느린 저장장치의 성능을 향상시키는 기법을 캐싱(Caching) 기법이라고 한다.

  

 

 

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

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

 

여러 후기를 검색한 결과, 

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

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

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

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을 리턴한다.

 

 

 

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

 

 

파이썬은 모든 것이 객체다. 

리스트와 딕셔너리 자료형은 가변 객체이며 숫자와 문자는 불변 객체다.

 

 

변수에 값을 할당하는 행위는 값 객체를 잠조하는 것 과 같다

아래의 예를 보자

 

 

b라는 변수에 a를 할당한 다음,

b의 메모리 주소를 출력하니 a와 동일한 값이 나왔다.

변수 b는 a의 객체를 '참조'하는 것이다

 

 

 

변수 b가 객체 a를 참조하는 것이 아니라

객체를 복사 하려면(다른 메모리 주소를 얻으려면) 어떻게 해야 할까?

 

 

 

첫 번째 방법은 '[:]'를  활용하는 것이다.

 

 

변수 b에 'a[:]'를 할당하니, 

b의 메모리 주소가 a와 달라지는 것을 확인할 수 있다.

b가 객체 a를 '참조'하는 것이 아니라 '복사'한 것이다.

 

 

 

두 번째 방법은 'copy() 메서드'를 활용하는 법이다.

 

 

마찬가지로 copy() 메서드로 a 객체를 카피한 값을 b에 할당하자

b의 메모리 주소는 a와 달라진다.

 

 

 

 

마지막으로 복잡한 리스트에는 deepcopy() 메서드를 사용할 수 있다.

 

 

위 그림과 같이 중첩 리스트의 경우도

copy 모듈을 호출한 다음

deepcopy() 메서드를 통해 a 객체의 복사본을 변수 b에 할당할 수 있다.

 

 

 

특정 객체(a)를 새로운 변수(b)에 '복사'하지 않고, '참조'하게 되면

객체의 값(a)이 변할 때마다

참조된 값(b)이 따라 변하게 된다.

'참조'와 '복사'의 개념을 반드시 구분하여 사용해야 하는 이유다.

 

 

 

 

* 위 내용은 도서 파이썬 알고리즘 인터뷰(박상길, 책만)의 책을 참고하여 정리한 내용임

 

 

 

 

 

 

나는 영영제를 믿지 않았다. 호주에서 같이 지내던 룸메이트는 하루에 한 알씩 먹는 비타민C 영양제를 세 알이나 먹곤 했다. 이해할 수 없었다. 건강에 지나치게 집착한다고 생각했다. 또 한 번은 '영양제 무용론'을 다루는 다큐멘터리를 봤다. 대부분 영양소는 음식으로 섭취할 수 있고, 인공적으로 만들어진 영양소는 체내에 흡수가 잘 안 되기 때문에 영양제는 효과가 없다는 내용이었다. 그럴듯해 보였다.

 

그런데 '사피엔스'라는 책을 읽으며 한 가지 의문이 들었다. 7만 년 전 수렵채집인은 사냥한 동물, 나무 열매, 풀, 곡류 등 다양한 음식을 먹었다. 1만 년 전 농업혁명 이후부터 사람들의 먹는 양은 수렵채집인에 비해 늘었지만, 먹는 음식의 종류는 쌀과 밀로 제한되었다. 초등 입맛을 지닌 내가 밥과 고기 외 음식은 입에 잘 대지 않는 다는 점이 그 증거다. 문제는 나의 몸이 원시인의 몸과 하드웨어 측면에서 거의 동일하다는 점이다. 내 몸은 7만 년 동안 다양한 영양분을 섭취했던 몸의 후손이다. 그런데 나는 탄수화물과 단백질만 내 몸에 밀어 넣었다. '영양 불균형으로 몸 한구석이 썩어가는 것은 아닐까?'하는 의문이 들었다.

 

한날 유명 약사 유튜버의 영상을 보았다. 이 약사는 대학병원에서 일하다가 약국을 개업했는데, 약국 근처에 한 병원 때문에 영양제에 관심을 가졌다고 한다. 이 병원은 의학적 치료와 영양 요법을 병행해서 난치병을 치료하는 것으로 유명했다. 이 약사는 부족한 영양소를 보충하는 것이 치료에 도움이 될 수 있다는 사실을 알게 되었다. 이를 계기로 영양제를 공부했고 그 내용을 유튜브를 통해 대중들과 공유했다.

 

이 약사는 '영양제를 딱 하나만 먹어야 한다면?'이라는 질문에 '오메가3'라고 답했다. 오메가3는 만성 염증을 개선하는 데 도움을 주는데, 원인을 알 수 없는 몸의 통증은 만성 염증에서 비롯되는 경우가 많다고 한다. 또 마그네슘과 비타민B 영양제를 추가로 복용하라고 추천한다. 마그네슘은 천연 신경안정제로 불릴 정도로 스트레스 해소에 효과가 있다고 한다. 비타민B는 충분한 용량을 복용할 경우 피로회복에 좋다고 알려졌다. '오메가3, 마그네슘, 비타민B' 영양제를 먹어보기로 했다.

 

영양제를 고르기 어려운 이유 중 하나는 '성분을 따지기 힘들다는 점'이다. 특히 여러 가지 영양제를 조합해야하는 경우 더욱 그러하다. 그래서 이 약사는 좋은 제품을 추천해준다. 첫 번째는 스포츠리서치사의 '트리플 스트렝스 오메가3'이다. 장점으로 오메가3 함량이 높고 가격이 적당하다. 두 번째는 쏜리서치사의 '베이직 뉴트리언트 2데이 캡슐'이다. 종합비타민으로써 비타민B군 함량이 높으며 체내에 흡수가 잘 되는 고품질 원료로 만들어졌다. 다만 가격이 좀 비싸다. 마지막으로 앞서 말한 종합비타민에는 마그네슘 함량이 부족하므로 같은 회사의 '칼슘-마그네슘 말레이트 캡슐'을 추가로 섭취할 것을 추천한다. 위 제품을 기준으로 하루에 오메가3 3알, 마그네슘 4알, 종합비타민 2알을 먹는다. 쿠팡 로켓배송으로 두 달 치를 구매하니 12만 원이 나왔다. 해외직구인데 주문한 지 이틀 만에 도착했다.

 

영양제가 만병통치약은 아니다. 건강의 기본은 건강한 식습관과 규칙적인 운동이라고 믿는다. 다만 편식하는 습관으로 부족할 수 있는 영양소를 보충하는 용도로 영양제를 활용할 뿐이다. 1년 정도 영양제를 복용하면서 그 효과를 주관적으로나마 확인해보려 한다.

+ Recent posts