https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 트리 재귀 순회 문제이다. 이런 문제를 몇번 풀어보긴 했지만, 익숙하지 않아서 꽤 애를 먹었다. 알고리즘은 뭔가 답답할 땐 항상 그림을 그리며 직접 손으로 따라가보자! --설명-- 1. (0,8)을 넘겨준다 2. mid는 end+1로 설정하고, ( 아래 for문에서 mid값이 갱신되지 않는다면, end를 그대로 넘겨야 하는데 넘길 때 -1을 해주므로 ) 3. start를 pivot 삼..
https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 가장 기본적인 최장 거리 거리 수열 문제이다. O(n^2)의 시간복잡도를 가지기 때문! 해당 알고리즘은 백준에 '가장 긴 증가하는 부분 수열' 시리즈를 풀어보면 좋다 현재 위치 기준으로 이전 위치들을 탐색하며 본인보다 작은게 있다면 dp 값을 최대로 업데이트 해주는 방식이다. import sys #from collections import deque #import heapq #sys.setrecursion..
https://www.acmicpc.net/problem/24230 24230번: 트리 색칠하기 정점이 $N$개인 트리가 있다. 정점에는 1부터 $N$까지 번호가 붙어있다. 트리의 루트는 항상 1번 정점이며 맨 처음에는 모든 정점이 하얀색으로 칠해져 있는 상태이다. 하나의 정점에 색칠하면 해 www.acmicpc.net 문제가 조금 복잡하기 쓰여있지만, 하얀 색으로 칠할 수 없고 모든 입력이 칠할 수 있는 경우로만 주어지므로 그렇게 어렵게 생각하지 않아도 될 듯 하다. 기본적인 트리 탐색 알고리즘인 dfs와 bfs 중 하나 골라서 풀어도 되는데, 필자는 bfs로 골랐다. 핵심은 바로 부모와 나(자식)의 색깔 차이이다. 부모와 색이 다르다면 무조건 색을 한번 칠해야 하므로 그럴 때 마다 카운트를 해주면 된..
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분 그래프인지 아닌지를 판단하는 문제이다 정점 하나하나씩 bfs 탐색을 진행해주는데, 주의해야 할 점은 그룹을 지어야 한다는 것이다! (왜 bfs를 한번에 돌리지 않고, 정점 하나씩 해주냐면 입력이 어떻게 들어올 지 모르기 때문이다. 비연결 그래프가 존재하는 경우, 시작점과 연결되지 않은 곳은 탐색할 수 없기 때문에 모든 정점에 대해 탐색해주는 것이다) 트리를 하나 떠올려 보자. level 0 ..
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 1167번 문제와 입력만 다르지 풀이법은 동일하다. https://oh2279.tistory.com/167
https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 트리의 전위, 중위, 후위 순회를 코드로 구현하는 문제이다. c++로 코딩하던 버릇이 남아있어 그런지 아스키 코드를 이용했다 원랜 ans 변수에 답을 담는 것이 아닌, visited 배열을 이용해 답을 저장하려고 아스키 코드를 썻는데 결국 그러진 않았다. 굳이..? 라는 생각이 들어서,, 트리의 순회 방법에 대해 알고 있다면 차례대로 구현해주기만 하면 된다. 좀 더 정석적인 풀이 방법이..
