늦깍이 코린이

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net Remind Binary Tree Binary Tree란 무엇인가? 각 부모 노드가 최대 두 개의 자식 노드를 가지는 자료구조 각각의 자식 노드는 왼쪽, 오른쪽이라고 명시하기 때문에, 일반적인 트리 구조가 아님! 전위 순회, 후위 순회, 중위 순회 루트 노드부터 모든 노드를 어떻게 방문하는 순서 (부모(1) - 왼쪽 자식(2) - 오른쪽 자식(3)) 전위 순회 : (1) - (2) - ..

학교 수업 '자료구조' 복습입니다. Binary Search Trees(BST)란? 다음 조건을 따르는 이진 트리이다. 1) 모든 노드는 유일한 키를 갖는다. 2) K라는 키를 갖는 노드의 왼쪽 subtree에 있는 모든 노드는 K보다 작은 키를 갖는다. 3) K라는 키를 갖는 노드의 오른쪽 subtree에 있는 모든 노드는 K보다 큰 키를 갖는다. 4) 모든 subtree는 BST이다. BST as a Dictionary Implementation Search Insert/Remove Sorted list(array) O(log𝓃) O(𝓃) Unsorted list(array) O(𝓃) O(𝓃) Binary Search Tree O(𝑑) = O(log𝓃) (이상적인 경우) O(𝑑) = O(log𝓃) (..

학교 수업 '자료구조' 복습입니다. Binary Tree 구현(Link를 사용한 Implementation) 방법 1 : 리프 노드와 내부 노드를 똑같이 구현한다. interface BinNode { E getItem(); BinNode left(); BinNode right(); } 해당 방법으로 구현시, null 값의 개수가 node의 개수 + 1 개 이다. 방법 1의 space overhead *space overhead란? total space(사용 메모리의 총량) - data space(담고자하는 데이터를 위한 메모리 사용량) 위 그림) 데이터 A,B,C,D,E,F,G,H,I -- 9개의 data space total space -- 9 * data + 9 * 2 * pointer space o..

학교 수업 '자료구조' 복습입니다. Binary Trees란? 이진 트리의 정의 각 노드가 자식 노드를 최대 두 개까지만 가지는 트리. 두 자식 노드는 각 각 왼쪽 자식, 오른쪽 자식이라고 부름. *왼쪽, 오른쪽이라고 위치를 명시하기 때문에, 같은 두 개의 자식을 가지고 있는 트리라도 일반적인 트리와 이진 트리는 서로 다름. 정 이진 트리 full binary tree : 각 노드의 자식 노드 수가 2 또는 0인 트리 완전 이진 트리 complete binary tree : 가장 깊은 레벨을 제외한 모든 레벨이 가득 차 있음 마지막 레벨의 노드들은 가능한 왼쪽에 존재 포화 이진 트리 perfect binary tree : 모든 단말 노드의 레벨이 같음 모든 내부 노드의 자식의 수가 2임 Q1) 포화 이진..

Tree란? 자료의 계층적 성질의 도식화 조직도, 토너먼트, 카테고리, etc. acyclic, undirected, connected graph를 의미한다. graph : 노드와 노드들을 연결하는 edge로 구성된 자료. ayclic : 노드들 사이에서 서로 순환하는 고리가 없는 것. undirected : 간선에 방향이 없는 것. connected : 모든 노드들이 전부 연결되어 있는 것. 위 세 가지 조건을 모두 만족해야, 트리라고 할 수 있다. Rooted Tree - Tree Data Structure (자료구조에서의 Tree) 루트가 있는 트리 : 트리구조를 노드와 간선의 집합으로 표현한 것. 일반적인 트리는 루트가 없지만, 자료구조에서는 대체로 루트가 있는 트리를 말한다. Tree와 Root..

https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 문제 풀이 전형적인 큐 문제이다. 첫 번째 수는 버리고, 두 번째 수는 맨 뒤로 보내 순서를 바꾸는 것을 반복하면 된다. 앞과 뒤가 있으므로 큐를 활용하는 것이 가장 좋다. 푼 방법 1. 큐를 만든다(qu) 2. 1부터 N까지 순서대로 qu에 넣어준다. (front = 1 , back = N) 3. while문을 통해 qu의 size가 1이 될 때까지(size가 1이 되면 break해준다.)..

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제 문제 풀이 전형적인 큐 문제이다. 순서대로 k번째 사람에 접근해야되는데, 큐 문제가 될 수 있는 이유는 Circular queue를 생각하면 된다. 원을 이루고 있기 때문에, 1번째부터 k-1번째 사람을 순서대로 뒤로 붙여, 순서를 뒤로 미루는 방식으로 접근하면 된다. k번째 사람이 1번째 순서가 될 때까지 앞의 사람들을 다 뒤로 보내고 k번째 사람이 1번째 순서가 되면 해당 사람을 빼버리면 된다. 푼 방법 1. 큐를 두 개 만든다.(qu, qu2) 2. 1부터 N까지 순서대로 qu..

https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 문제 풀이 백준 10828번 스택과 매우 유사한 구현 문제이다. 큐(queue)와 스택(stack)의 차이를 알고 있다면 구현에 어려움은 없을 것이다. 큐와 스택의 차이는 큐는 FIFO(First In, First Out), 스택은 LIFO(Last In, First Out), 즉 선입선출, 후입선출의 차이가 있다는 걸 알아야한다. LIFO : 스택의 후입 선출은 들어온게, ..

Queues란? FIFO(First In, First Out) 선입 선출 리스트의 제한된 형태 : 한쪽 끝에서만 넣고, 다른 쪽 끝에서만 뺀다. Enqueue(넣기) Dequeue(빼기) Front(맨 앞의 값) Rear(맨 뒤의 값) Array-based Queue의 경우 다음과 같이 계속해서 사용하게 되면, 배열의 한쪽 끝으로 점점 이동하게 된다는 문제점이 있다. 따라서 아래와 같이 실행하였을 때, 영구적으로 배열을 사용할 수 있게 된다. 그림처럼 배열을 원이라고 생각하고, 한쪽 끝으로 점점 이동했을 때, 다시 맨 앞으로 돌아가서 재활용하는 방법을 사용하면 된다. 이를 코드로 생각해보면, 아래의 코드처럼 사용할 수 있다. enqueue(E item){ rearIdx = (rearIdx+1) % si..

Stack이란? LIFO(Last In, First Out) 후입, 선출 / 먼저 들어간게 먼저 나온다. 리스트의 제한된 형태 넣고 빼기가 리스트의 한쪽 끝에서만 가능하다.(뒤에서만 넣고 빼기가 가능한 리스트) PUSH(넣기) POP(빼기) TOP(맨 위의 값 리턴) Stack ADT public interface Stack { public void clear(); // 전부 다 지우기 public void push(E it); // 값을 맨 위에 넣기 public E pop(); // 맨 위의 값을 빼서 쓰기 (return타입이 있는 이유) public E topValue(); // 맨 위의 값을 가져만 오기 (return타입이 있는 이유) public int length(); // 스택에 얼마나 많은..