전체 글 14

트리(Tree)_1

트리 용어 노드 : 데이터 원소 간선 : 노드 사이의 부모-자식 관계를 표시 루트 : 트리 맨 위에 있는 부모가 없는 노드 내부노드(중간노드) : 적어도 한 개의 자식을 가진 노드 외부노드(잎) : 자식이 없는 노드 형제 : 같은 부모를 가진 노드들 노드의 조상 : 루트를 향해 간선을 따라 올라가면 만나게 되는 부모, 조부모, 증조부모 등의 직계 상위 노드들 노드의 자손 : 잎을 향해 간선을 따라 내려가면 만나게 되는 자식, 손주, 증손주 등의 직계 하위 노드들 부트리 : 노드와 그 노드의 자손들로 구성된 트리 경로 : 조상 또는 자손을 따라 이어진 노드 시퀀스 경로길이 : 경로 내 간선의 수 노드의 깊이 : 루트로부터 그 노드에 이르는 유일한 경로의 길이 노드의 높이 : 그 노드로부터 외부노드에 이르는..

자료구조 공부 2024.02.19

1991번: 트리 순회

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 전위순회 중위순회 후위순회를 차례로 출력하는 문제다. 재귀를 이용하는 방법이 먼저 생각이 나서 재귀함수를 만들어서 풀었다. 문제에서 예시로 준 트리이다. 각 순회마다 출력되는 순서는 다음과 같아야 한다. 전위순회 (루트-왼-오) : ABDCEFG 중위순회 (왼-루트-오) : DBAECFG 후위순회 (왼-오-루트) : DBEGFCA 어떤 부트리에서든지 각 순회의 순서가 지켜져야 한다. 그..

백준 문풀 2024.02.15

13241번: 최소공배수

https://www.acmicpc.net/problem/13241 13241번: 최소공배수 정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다. 예: 10은 5의 배수이다 (5*2 = 10) 10은 10의 배수이다(10*1 = 10) 6은 1의 배수이다(1*6 = 6) 20은 1, 2, 4,5,10,20의 배수이다. 다 www.acmicpc.net 실버 5라고 20분만에 풀겠다며 시간을 쟀지만 택도 없었다..ㅎㅎ 최소공배수를 구하는 거야 당연히 for문을 사용해서 차례대로 수를 곱해보면서 구할거라고 생각하고 바로 이중 for문을 작성해서 구했다. #pragma warning (disable : 4996) #include #include #include int main..

백준 문풀 2024.02.12

10866: 덱

https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 덱(deque)은 큐이지만 양방향으로 원소를 넣고 뺄 수 있는 자료구조이다. 이 문제는 그 덱을 구현만 하는 문제이다. 덱은 양방향이므로 양방향으로 왔다갔다 할 수 있는 이중 연결리스트를 사용하기로 했다. 문제가 문자열로 입력을 받아야했는데 문자열 문법을 다 까먹어서..ㅎㅎㅎ 구글링으로 문자열에 대해 다시 좀 공부했다. strlen(a) : a의 길이 strcat(a,b) : a뒤..

백준 문풀 2024.02.04