넘치게 채우기

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제 유형 : DFS / 트리 solved.ac 난이도 : Gold V 문제 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 입력 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나..

BFS BFS(Breadth First Search)는 너비 우선 탐색으로, 가까운 노드부터 탐색하는 알고리즘이다. BFS에서는 큐 자료구조를 이용하여 구현한다. 인접한 노드들 중 방문하지 않은 노드를 큐에 추가하면 가까운 노드부터 탐색하는 것이다. 동작 방식은 다음과 같다: 1. 탐색 시작 노드를 큐에 넣고, 방문처리한다. 2. 큐에서 노드를 꺼내 큐의 인접 노드들 중 방문하지 않은 모든 노드들을 큐에 삽입하고, 순서대로 방문처리한다. 3. 2번의 과정을 계속해서 반복한다. 노드 '1'부터 시작해서 '1'을 큐에 넣고 방문처리한다. 노드 '1'을 큐에서 꺼내고, '1'의 인접 노드들 중 방문하지 않은 노드들을 모두 큐에 넣고 방문처리한다. 노드 '2'를 큐에서 꺼내고, 2에 인접한 노드들 중 방문하지 ..

DFS DFS는 Depth-Fisrst Search. 깊이 우선 탐색이다. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 스택 자료구조를 사용하고, 최대한 깊숙히 노드를 방문하고, 끝에 도달하면 다시 돌아가서 다른 경로를 탐색한다. DFS 는 다음의 동작과정이 있다: 1. 탐색 시작 노드를 스택에 삽입하고, 노드를 방문처리한다. 2. 스택 맨 위에 있는 노드에서 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고, 방문처리한다. 방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼낸다. 3. 2번을 계속 방문한다.(스택이 빌 때까지) DFS의 과정 1부터 탐색을 시작한다. 1을 스택에 넣고, 방문처리를 한다. '1'에서 방문하지 않은 인접 노드 '2', '3', '4'가 ..

재귀 함수란 자기 자신을 다시 호출하는 함수를 의미한다. 자기 자신을 계속해서 호출하다가, 일정한 조건이 만족되면 함수를 반환하여 결과를 도출한다. 컴퓨터 내에서 재귀 함수는 스택 자료구조와 동일하다. 함수를 계속 호출했을 때, 마지막으로 호출된 함수가 먼저 종료되어야 첫 함수가 종료된다. 아래는 재귀 함수의 대표적인 예시인 팩토리얼이다. def factorial(n): if n == 0 or n == 1: return 1 else: return n * factorial(n-1) 재귀 함수의 장점은 수학의 점화식을 표현한 코드여서 매우 간결한 표현이 가능하단 것이다. 단, 끝없이 재귀 함수가 반복되지 않도록 함수를 끝낼 수 있도록 조건을 만들어놓아야 한다.

그래프 그래프는 객체로 나타내는 정점(vertex)와 객체를 연결하는 간선(edge)의 집합으로 구성된다. G = (V, E) (V = 정점의 집합, E = 간선의 집합) 그래프의 종류 무방향 그래프 두 정점을 연결하는 간선에 방향이 없는 그래프이다. 정점 V1에서 정점 V2로 잇는 것을 표현하는 간선으로 (V1, V2)로 표현한다. (V2, V1)로 표현해도 같은 간선이다. 방향 그래프 두 정점을 연결하는 간선에 방향이 있는 그래프이다. 정점 V1에서 정점 V2로 잇는 것을 표현하는 간선으로 로 표현한다. 이랑은 다른 간선이다. 완전 그래프 각 정점에서 다른 모든 정점을 연결한 그래프이다. 최대로 많은 간선 수를 가지고 있다. 무방향 완전 그래프에서는 정점이 n개일 때, n(n+1)/2개의 간선을 가진..

힙 힙(Heap)은 다음과 같은 특성을 가지고 있다: 1. 완전 이진 트리이다. 2. (부모 노드의 index) = (자식 노드의 index) // 2 3. (왼쪽 자식의 index) = (부모 노드의 index) * 2 4. (오른쪽 자식의 index) = (부모 노드의 index) *2 +1 5. 루트의 index는 1이다. (구현의 편의상 1부터 시작한다.) 힙은 이러한 특성때문에 보통 배열로 많이 구현한다. 힙의 삽입과 삭제는 O(log N)이 걸리고, 탐색에는 O(N)이 걸린다. 힙은 두 가지의 종류가 있다. 최대 힙과 최소 힙이다. 최대 힙(max heap)은 부모 노드의 key값이 자식 노드의 key 값보다 큰 힙이고, 최소 힙(min heap)은 부모 노드의 key값이 자식 노드의 key ..

트라이란? 트라이는 문자열의 저장과 탐색을 효율적으로 하기 위한 k진 탐색 트리이다. 단어들이 공동으로 가지는 접두사들을 이용해서 문자열을 저장하고 탐색한다. 트라이의 특징 1. 트라이의 루트에는 빈 문자열을 나타내는 노드부터 시작한다. 루트 노드부서 시작해서 문자열의 접두사부터 따라가기 시작한다. 2. 각 노드는 문자와 자식 노드에 대한 포인터를 가지고 있다. 3. 종료 노드는 해당 문자열이 Trie에 존재함을 나타낸다. 4. 문자열 검색은 루트에서 시작하여 해당 문자열의 모든 문자를 따라 이동한다.(문자열의 접두사를 얻을 수 있다) 트라이의 시간복잡도는 O(n)(문자열의 길이만큼) 이다.트라이는 검색이나 사전 등에서 사용된다. 각 노드는 다음 자손의 포인터와 nil을 모두 포함하는 배열을 가지고 있다..

레드블랙트리의 삭제의 순서는 다음과 같다: 1. 삭제할 노드를 찾는다 2. 삭제할 노드의 자식이 a. 둘인 경우 - 없앨 노드의 오른쪽 서브트리의 가장 왼쪽 노드(또는 왼쪽 서브트리의 가장 오른쪽 노드)로 노드를 바꾸고, 그 잎 노드를 없애준다. b. 하나인 경우 - 삭제되는 노드의 부모노드와 자식노드를 연결시킨다. c. 없는 경우 - 노드를 없애주면 된다. 여기까지는 이진탐색트리의 노드제거와 같다. 3. 삭제되는 노드의 색깔이 빨간색인 경우, 여전히 레드블랙트리의 규칙을 만족하므로 삭제가 완료된다. 그러나, 삭제되는 노드의 색이 검은색인 경우, 그 자리를 대체하는 노드를 검은색으로 칠한다. 여기서, 대체하는 노드 역시 검은색인 경우, 이중 흑색노드가 생긴다. 그럼, 이중 흑색노드를 어떻게 해결하냐? C..

레드블랙트리의 삽입 레드-블랙트리의 삽입에서, 다음과 같은 과정을 거친다: 1.이진 탐색 트리와 같이 노드를 삽입하고, 삽입한 노드의 색은 빨간색으로 한다. 2.트리에 문제가 생기진 않는지 확인해주고, 문제가 있으면 고쳐준다. 레드블랙트리의 삽입에서의 문제 해결은 다음과 같은 경우들이 있다: 삽입되는 노드를 편의상 z라고 가정해보자. 1. z가 루트인 경우 z가 루트인 경우는 쉽다. 루트 노드의 색은 검정색이여야 하므로 빨간색을 검은색으로 칠해주면 된다. 이 경우를 제외한 나머지 경우는 모두 부모 노드가 빨간색이라 Double Red가 생긴 경우이다. 2. z의 삼촌이 빨간색인 경우 z의 삼촌이 빨간색일 땐, 조부모 노드(부모노드의 부모노드)의 색을 빨간색으로 칠해주고, 부모노드와 삼촌노드를 검은색으..