투투

전위 순회와 후위 순회의 결과가 주어질 때 트리를 구하고, 이 트리를 통해 중위 순회도 구현할 수 있다. 원리 위와 같은 트리가 주어졌을 때 전위 순회와 후위 순회의 결과는 다음과 같다. 전위 순회 : 1 2 4 8 9 5 10 11 3 6 7 후위 순회 : 8 9 4 10 11 5 2 6 7 3 1 이때 전위 순회의 첫 번째 숫자와 후위 순회의 마지막 숫자가 루트 노드라는 것을 알 수 있다. (전위 순회는 루트 노드를 먼저, 후위 순회는 루트 노드를 마지막으로 방문하기 때문이다.) 그 다음 전위 순회의 두 번째 숫자는 루트 노드의 왼쪽 자식 노드가 될 것이고, 후위 순회에서 마지막에서 두 번째 노드는 루트 노드의 오른쪽 자식 노드가 될 것이다. 이때 두 번째 숫자인 2를 후위 순회에서 찾아보면 8부터 ..

자료구조 힙에 대한 개념을 알아보고 완전 이진 트리를 통해 최소힙과 최대힙을 구현해보자. 들어가기전에 먼저 힙에 대해 알아보기 전에 완전이진트리의 개념을 상기시킬 필요가 있다. 힙은 완전이진트리의 형태이기 때문이다. 아래의 그림은 포화이진트리를 나타낸 것이다. 포화이진트리는 리프 노드를 제외한 모든 노드들이 2개의 자식 노드들을 갖고있는 트리이다. 포화이진트르의 노드 개수는 높이가 h 일 때 2^(h+1) - 1이 된다. 아래의 그림은 완전이진트리를 나타낸 것이다. 위의 포화이진트리에서 가장 오른쪽에 있는 리프노드를 제거한 모습이다. 이처럼 완전이진트리는 왼쪽부터 빈틈없이 채워나간 트리를 의미한다. 아래의 그림은 완전이진트리가 아니다. 왜냐하면 왼쪽 리프노드에 빈 칸이 존재하기 때문이다. 완전이진트리는 ..

스택과 큐의 원리를 이용하면 스택으로 큐를, 큐로 스택을 구현할 수 있다. 그 원리를 알아보고 코드로 구현해보자. 스택으로 큐 구현하기 큐는 선입선출의 구조로 데이터가 들어온 순서대로 나가게된다. 이를 스택 2개를 활용하여 구현할 수 있다. 아래의 그림을 보자. 스택 A와 B가 존재한다. 만약 큐에 PUSH하는 과정이 일어나면 스택 A에 PUSH를 한다. 이후 큐에 POP연산을 하게되면 스택 A의 모든 데이터를 스택 B로 옮긴다. 그렇게되면 스택 A의 역순으로 데이터가 저장될 것이고 스택 B를 POP하면 큐에 저장된 데이터 순서대로 출력될 것이다. 즉 스택 A는 인큐의 역할을 하게되고 스택 B는 디큐의 역할을 하게된다. PUSH를 하면 스택에는 가장 늦게 들어온 데이터가 맨 위에 쌓일 것이며 이를 다시 ..

그 동안 알고리즘 문제를 풀 때 dict를 많이 사용하였다. dict는 해시 테이블이라는 자료구조 인데 key-value 쌍으로 데이터를 저장할 수 있다. 원리는 대충 알고있었지만 정확하게 어떠한 원리를 갖고있는지 이해하고 싶어서 정리를 하게 되었다. 해싱 먼저 해싱이라는 개념을 이해할 필요가 있다. 해싱은 랜덤한 길이의 값을 해시 함수를 사용하여 고정된 크기의 값으로 변환하는 것을 의미한다. 아래의 그림과 같이 "apple", "banana", "complete"처럼 문자열의 길이가 다양한 단어가 들어왔을 때 세 자리 정수로 변환하는 작업을 해싱이라 할 수 있다. 해시 테이블과 해시 함수의 필요성 해시 테이블 해시 테이블은 해시 함수를 통해 변환된 값을 Index로 삼아 Key와 Value를 저장하는 ..

트리에서 최소 공통 조상이 무엇이며 이를 구하기 위한 기본적인 방법과 메모리를 사용하여 시간 복잡도를 개선한 알고리즘을 알아보자. 최소 공통 조상(Lowest Common Ancestor) 최소 공통 조상은 두 노드의 공통된 조상 중에서 가장 가까운 조상을 의미한다. 아래의 트리를 통해 9번 노드와 11번 노드의 LCA를 알아보자. 9번 노드의 부모 노드는 4 -> 2 -> 1이며 11번 노드의 부모 노드는 5 -> 2 -> 1이다. 이때 2와 1은 두 노드의 공통 조상이된다. 이처럼 두 개의 노드에서 공통 조상이 될 수 있는 노드는 여러 개일 수 있으며 여기서 레벨이 가장 높은(두 개의 노드에서 가장 가까운)노드가 최소 공통 조상이 된다. LCA 알고리즘 Ⅰ 기본적인 LCA 알고리즘의 개념은 다음과 같..

가중치가 있는 간선으로 연결된 트리에서 지름을 알아보자. 이를 통해 트리의 특징들을 더 깊게 이해할 수 있을 것이다. 트리의 지름을 알아보기 위해 백준 1967 트리의 지름 문제를 참고하였다. 트리의 지름이란 트리는 N개의 노드로 이루어졌을 때 N-1개의 간선으로 연결되기 때문에 순환되지 않는 구조를 갖고있다. 따라서 노드 A에서 노드 B로 이동하는 경로를 하나밖에 없다. 이때 두 개의 노드를 양쪽으로 잡아당겼을 때 가장 길게 늘어나는 경우가 생기며 특정 원 안에 트리가 들어온다. 여기서 생긴 원의 지름을 트리의 지름이라고 한다. 트리의 지름 구하기 그렇다면 트리의 간선들에 가중치가 있을 때 트리의 지름을 어떻게 구할 수 있을까? 아래의 트리를 보면 트리의 지름을 구성하는 두 개의 노드는 9번 노드와 1..

트리의 속성을 완벽히 이해하기 위해 트리와 관련된 여러가지 문제들을 풀어보자. 이번에는 백준 11725 트리의 부모 찾기 문제를 통해 트리에서 루트 노드를 제외한 다른 노드의 부모 노드를 찾아보자. 접근 트리는 순환되지 않는 구조를 갖고있다. 그렇기 때문에 N개의 노드는 N-1개의 간선을 통해 트리를 구성할 수 있다. 만약 N-1개 보다 많은 간선을 갖는다면 순환되는 구조를 갖게된다. 이때 N-1개의 간선에 대한 정보(간선에 의해 연결된 두 개의 노드)가 입력으로 주어질 때 어떻게 저장하여 트리를 구현할 수 있을까? 이번에는 2차원 리스트를 활용하였다. a, b 노드를 입력받았을 때는 어떤 노드가 부모 노드이고 어떤 노드가 자식노드인지 알 수 없다. 따라서 a행의 리스트에 b를 추가하고 b행의 리스트에도..

이진 트리는 루트 노드를 기준으로 두 개의 서브트리로 나뉘어 진다. 또한 서브트리도 최대 두 개의 서브트리로 나뉘어지는 것을 이진 트리라 한다. 이진 탐색 트리는 정해진 규칙에 의해 이진 트리의 노드에 데이터를 저장하는 기법이다. 이진 탐색 트리를 통해 데이터를 저장하면 원하는 데이터를 찾을 때 효율적으로 찾을 수 있다. 이진 탐색 트리의 원리 이진 탐색 트리는 정해진 규칙에 따라 이진 트리에 데이터를 저장한 트리이다. 아래는 이진 탐색 트리를 가장 잘 표현한 것 같아서 첨부한다. 루트 노드를 기준으로 큰 값이 들어오면 오른쪽으로, 작은 값이 들어온다면 왼쪽으로 보내진다. 이를 통해 루트 노드를 기준으로 왼쪽은 작은 값, 오른쪽은 큰 값이 저장된다. 이제 데이터를 찾아야 한다면 아래와 같은 과정을 거치게..

스택을 활용하여 후위표기법을 구현할 수 있다. 후위표기법의 개념과 스택으로 후위표기법을 구현해보자. 후위표기법이란? 우리가 일반적으로 알고있는 5+3x2와 같은 수식은 중위 표기법으로 작성된 것이다. 이를 후위표기법으로 변환하면 532x+가 된다. 먼저 중위 표기법으로 작성된 수식을 후위 표기법으로 변환하는 방법과 후위 표기법으로 표현된 수식을 계산하는 방법을 알아보자. 후위 표기법으로 변환 5+3x2라는 수식을 보자. 숫자가 나오면 바로 옮겨 적는다. "x" 또는 "÷"가 나오면 나온 순서대로 다른 곳에 기록해둔다. "+" 또는 "-"가 나오면 다른 곳에 기록해둔 "x"와 "÷"를 늦게 적은 순서대로 후위 표기식에 옮겨 적는다. 모두 옮겨 적었다면 "+" 또는 "-"를 다른 곳에 기록해둔다. 모두 적었..

중위 순회와 후위 순회의 결과를 알 때 전위 순회의 결과를 구해보려고 한다. 이는 백준 2263 트리의 순회 문제이다. 해당 문제는 트리 순회의 특징을 정확히 이해하고 있는지 판단하기 좋은 문제라고 생각한다. 이와 비슷하게 전위 순회와 중위 순회를 알 때 후위 순회를 구할 수 있지만 전위 순회와 후위 순회를 알 때 중위 순회는 구할 수 없다. 접근 아래와 같은 트리가 있다고 해보자. 이 트리를 중위 순회, 후위 순회로 탐색하면 다음과 같은 순서일 것이다. 중위 순회 : 4 -> 2 -> 5 -> 1 -> 3 -> 6 후위 순회 : 4 -> 5 -> 2 -> 6 -> 3 -> 1 후위 순회는 루트 노드를 가장 마지막에 방문하기 때문에 후위 순회 결과 중 가장 마지막 노드인 1이 루트 노드라는 것을 확인할 ..