나의 개발일지

Heap과 Priority Queue에 대해 설명하기 전에 완전 이진트리에 대해 알아보자. 완전 이진 트리 먼저, 이진 트리(binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조를 의미한다. 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다. 완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다. 마지막 레벨 h에서 1부터 2ʰ - 1 개의 노드를 가질 수 있다. 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다. (A)의 경우 완전 이진 트리이고, (B)의 경우 아니다. 힙(Heap) 힙은 완전 이진 트리의 일종이다. 여러 값들 중 최댓값 혹은 최솟값을 빠르게 찾아내기 ..

특정한 상황에 놓인 그래프에서 최단 경로를 찾을 때 O(V+E)의 시간 복잡도로 해결할 수 있는 0-1 BFS에 대해 알아보자. 0-1 BFS란 가중치가 0과 1로만 주어진 그래프에서 최단 경로를 찾고자 할 때 BFS를 응용하여 풀 수 있다. 보편적으로 사용하는 다익스트라 알고리즘의 시간 복잡도가 O(E log E)혹은 O(E log V)인데 0-1 BFS를 사용하면 단지 O(V+E)의 선형 시간 복잡도로 문제를 해결할 수 있기 때문이다. 0-1 BFS의 동작 왜 0-1 BFS가 O(V+E)에 동작할 수 있을까? 이는 BFS에서 노드를 관리하기 위해 큐를 사용하는 대신 덱(deque)을 사용하여 실현할 수 있다. 0-1 BFS는 다음 과정에 따라 최단 경로를 찾게 된다. 덱의 front에서 현재 노드를 ..

백트래킹 : 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 게임으로 비유하자면, 다음과 같은 게임에서 선택지가 나누어질 때 우리는 뭔가 하나를 정해서 가야한다. 2가지 선택지 중 첫 번째를 선택했더니 게임오버가 나왔다고 생각해보자. 그러면 되돌아와서 두 번째 선택해볼 것이고, 결론적으로 모든 경우를 다 훑어보게 된다. 즉 현재 상태에서 가능한 모든 선택지를 다 플레이해보는 방법이 바로 백트래킹이다. 백트래킹과 오목 백트래킹의 쓰임새를 하나 더 설명하자면 바둑과 오목이 있는데, 오목을 예를 살펴보자 우리는 파랑 돌이고 상대는 직전에 D5에 착수했다. 이 상황에서 어디에 둘 지 정해야 하는데 C5D5E5로 세로 3개가 완성된 것이 있으니 저걸 막아야 한다. 그러면 B5나 F5중 하나를 ..

재귀 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘 void func1(int n){ //N부터 1까지 출력하는 함수 if(n==0) return; cout

DFS(Depth First Search) : 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 DFS 과정 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김 스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입 스택이 빌 때 까지 2번을 반복 모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N) DFS도 BFS처럼 Flood Fill이 필요할 때 사용할 수 있다. 최종적인 방문 결과는 똑같더라도, 방문 순서에서 아주 큰 차이가 있다. (0,0) 에서 시작해 상하좌우로 이어진 모든 파란색 칸을 확인해보자. (0,0) 에 방문했다..

BFS(Breadth First Search) : 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 예시 (0,0)과 상하좌우로 이어진 모든 파란색 칸을 확인하는 과정. BFS 알고리즘은 좌표를 담을 큐가 필요하다. BFS 알고리즘이 시작되면 (0,0)에 방문했다는 표시를 남기고 해당 칸을 큐에 넣는다. 이 초기 세팅이 끝난 후에는 계속 큐의 front를 빼고 해당 좌표의 상하좌우를 살펴보면서 큐에 넣어주는 작업을 반복하게 된다. 지금 상황에서 큐의 front는 (0,0)이고 pop을 한다. 그리고 (0,0)의 상하좌우 칸이면서 아직 방문하지 않은 칸을 찾는다. (빨간색 테두리로 표시된 칸) (0,1) 과 (1,0)은 모두 파란 칸이면서 방문하지 않았다. 따라서 방문했다는 표시를 남기..

배열 : 메모리 상에 원소를 연속하게 배치한 자료구조 배열의 성질 1. O(1)에 k번째 원소를 확인/변경 가능 2. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음 3. Cache hit rate 가 높음 4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 배열에서 제공되는 연산 1. 임의의 위치에 있는 원소를 확인/변경, O(1) 2. 원소를 끝에 추가, O(1) 3. 마지막 원소를 제거, O(1) 4. 임의의 위치에 원소를 추가, O(N) 4번 임의의 위치에 원소를 추가할 때, 그 뒤의 원소들을 전부 한 칸씩 밀어야해서 O(N)이 필요하게 된다. 마치 책장에 책이 연속해서 꽂혀있을 때 중간에 책을 꽂기 위해 나머지 책들을 밀어야 하는 상황. 추가하는 위치가 끝에 가까울수..

수식의 괄호 쌍 32-{6-(2+4)×7} 은 올바른 괄호 쌍이다. -> {()} O 5+{6-(12+4}×7) 은 올바른 괄호 쌍이 아니다. -> {(}) X 이와 같이 수식의 괄호 쌍이란, 주어진 괄호 문자열이 올바른지 판단하는 문제이다. -> "문자열을 앞에서부터 읽어나갈 때, 닫는 괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라고 생각해도 된다." 💡예시를 들어 설명 ( { ( ) { } } ) 1. 여는 괄호를 만나면 그냥 여는 괄호를 쓴다. ( { ( 2. 이제 닫는 괄호를 만났는데, 가장 최근에 들어온 괄호를 없앤다. 둘다 파란색이니 짝이 잘 맞는다. ( { 3. 그다음 괄호는 여는 괄호이니 써준다. ( { { 4. 그 다음으로 있는 3개는 닫는 괄..

덱 덱(Double Ended Queue) 은 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조이다. 덱의 성질 1. 원소의 추가가 O(1) 2. 원소의 제거가 O(1) 3. 제일 앞/뒤의 원소 확인이 O(1) 4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 독특하게도, STL deque 에서는 인덱스로 원소에 접근이 가능 !! 덱의 구현 배열 혹은 연결 리스트를 사용해서 구현이 가능하며, 배열을 이용해 구현해 보도록 한다. 필요한 변수는 큐와 같이 원소를 담을 큰 배열 한개와 앞쪽, 뒤쪽을 가리킬 변수 두 개이다. 이 때 head와 tail을 두는 방식도 큐와 같다. head는 가장 앞에 있는 원소의 인덱스이고, tail은 가장 뒤에 있는 원소의 인덱스 +1이다. 또한 head와 ..

큐는 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. rear(한쪽 끝)에서는 삽입 연산만 이루어지며 다른 쪽 끝(front)에서는 삭제 연산만 이루어지는 유한 순서 리스트이다. 스택에서는 먼저 들어간 원소가 나중에 나왔지만, 큐에서는 먼저 들어간 원소가 먼저 나온다. 따라서 큐를 FIFO(First in First Out) 이라고 한다. 큐의 성질 1. 원소의 추가가 O(1) 2. 원소의 제거가 O(1) 3. 제일 앞/뒤의 원소 확인이 O(1) 4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 큐에서는 추가되는 쪽을 rear, 즉 뒤쪽이라고 하고 제거되는 쪽을 front, 즉 앞쪽이라고 한다. 큐의 기능과 구현 큐도 스택처럼 배열 혹은 연결리스트 둘 중 어..