[BAEKJOON] 2613번 숫자구슬
·
Algorithm/Binary Search
https://www.acmicpc.net/problem/2613 2613번: 숫자구슬 첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100 www.acmicpc.net 구슬 N개를 그룹 M개로 나눈다. 각 그룹은 무조건 구슬이 1개이상이다. 모든 경우의 그룹을 나눴을때, 그룹의 최대값이 나올 수 있는 경우의 수 중 최소일때를 찾는다. 접근 방법이 도저히 떠오르지 않았다. 각 경우의 수를 모두 구해야하는 완탐으로 접근해야 하나,,? N이 늘어날수록 어마무시하게 시간복잡도가 높아질게 뻔히 보이므로 알고리즘적으로 접근방법을 찾아야만 한다,,, 진짜 모르겠다 멍..
[BAEKJOON] 2250번 트리의 높이와 너비
·
Algorithm/DFS
https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 처음 문제를 보자마자 그래프가 나오길래 그래프 탐색 방법을 떠올렸다. 접근 방법은 차례대로 인덱싱하는 방향이길래 왼쪽부터 차례대로 인덱싱할수 있도록 DFS방식으로 접근해봤다. 또한 각 레벨에서의 너비를 구해야하는데, 탐색할때마다 인덱스를 1부터 시작해서 하나씩 증가시켜주며(어차피 왼쪽에서 부터 차례대로 인덱싱 할거니까), 각 레벨의 low, high 배열을 갱신시켜서 왼쪽 끝과 ..