[백준] 2250 트리의 높이와 너비
https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 각 트리 노드의 열 번호를 구하고, 레벨에 따라 저장한다. 그 후 레벨에 따라 열 번호의 최소, 최대 값을 구해 연산하면 전체 트리의 최대 너비를 구할 수 있다. 레벨에 따라 트리 노드의 열 번호를 저장 해야하기 때문에 Map 자료 구조를 사용해야한다. 그리고 아래 제시된 그림을 보면, 각 노드의 열 번호가 중위 순회에 따라 부여된다는 것을 알 수 있다. 따라서 트리를 중위 순회..
[백준] 1436 영화감독 숌
영화 제목에 '6'이 적어도 3개 이상 연속된 경우를 숫자의 크기대로 찾아 N번째인 경우를 반환해야한다. 가장 간단한 해결방법은 666에서 시작해서 1씩 증가시킨다. 만약 6이 연속해서 3회 이상 등장한 수인 경우 카운트를 1씩 늘리고, 카운트가 N이 된경우 그 수를 반환한다. 하지만 수를 문자로 변환시키고 파이썬 내장 함수인 count()를 사용하게 된다면 상당히 비효율적이다. 따라서 더 효율적인 코드를 위해서 숫자를 문자열로 변환하지 않고 6이 3회 이상 연속되는 경우를 찾아야한다. 숫자 i를 가지고 666이 들어가는 수를 만든다고 생각해보자. i = 0 : 0 * 1000 + 666 = 666 i = 1 : 1 * 1000 + 666 = 1666 ... i = 6 : 6 * 1000 + 666 = ..
[백준] 1450 냅색문제
DP에서 유명한 냅색 문제이지만, 이 문제는 최대 경우의 수가 2^30이기 때문에 DP를 통해서 해결할 수는 없다. 이전에 해결했던 부분수열의 합2와 같이 배열을 반으로 나누어 시간복잡도를 줄여야 한다. 주어진 하나의 배열을 Left, Right 2개의 배열로 나눈 후 부분수열을 구하는 알고리즘을 활용하여 원소들의 합을 구한다. 두 부분수열의 합 배열 중 하나만 선택하여 정렬하고, 나머지 하나의 배열의 원소를 주어진 C에서 빼 정렬한 배열을 Upper Bound 알고리즘을 통하여 문제를 해결한다. Upper Bound 알고리즘은 주어진 값 보다 큰 원소가 나타나는 첫번째 위치를 반환하는 알고리즘이다. 반면 Lower Bound 알고리즘은 주어진 값 보다 크거나 같은 값이 나타나는 첫 번째 위치를 반환하는..
[백준] 14225 부분수열의 합2
크기가 양수인 부분수열의 모든 원소의 합이 S가 되는 경우를 구하는 문제이다. 부분수열의 합1 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 위 문제와 유사한 풀이로 해결이 가능하다. 하지만 부분 수열의합1의 최대 크기가 2^20인데 반해 부분수열의 합2은 최대 크기가 2^40이다. 따라서 시간복잡도를 줄일 방법이 필요하다. 시간복잡도를 줄이기위해 배열을 반으로 나눌 수 있다. 반으로 나눈다면 각 배열의 최대 크기는 2^20이 되고 최종적으로..
[백준] 2632 피자 판매
피자는 A 종류 이거나 B 종류이거나 A와 B 혼합하여 판매할 수 있다. 그리고 한 종류의 피자 조각 을 2개 이상 판매할 때 그 조각들은 반드시 연속해야한다. '조각들이 연속해야한다'는 부분에서 A와 B 각각 누적합을 구해야함을 알 수 있다. 그리고 구해진 누적합을 이분탐색을 통해 고객이 원하는 피자의 크기를 구할 수 있다. 누적합 구하기 피자는 원형이기 때문에 순환 배열(Circular Array) 누적합을 구해야한다. start(front), end(rear) 포인터를 사용해야한다. start와 end 포인터를 한 칸씩 이동하면서 누적합을 구한다. 단 start 포인터가 다시 0이 되면 종료한다. start에서 end까지 모든 수의 누적합이 구매자가 원하는 크기 보다 작거나 같을 경우 조각의 개수 ..
[백준] 17825 주사위 윷놀이
이동할 수 있는 말에 대한 경우의 수를 백트래킹 알고리즘으로 구해 해결할 수 있다. 유의 해야 할 부분은 윷판에 지름길이 존재한다는 것이다. 나는 지름길을 처리하기 위해서 루트를 0 - 4로 나누었다. route0에서 처리 route0에서 고려해야할 것은 5, 10, 15 번에서 출발할 경우 지름길을 통하는 것이다. 5는 1번루트, 10은 2번루트 마지막으로 15는 3번 루트로 변경한다. 그리고 이동 해야 할 거리는 주사위의 숫자 크기를 따른다. 그리고 route0에서 말이 이동할 때 19 번을 넘을 겅우 route4로 루트를 변경 해야 한다. 이떄 route0의 길이를 오프셋으로 하고 이동 해야할 위치에서 오프셋을 빼준 후 다시 route4의 길이 - 1을 더해 위치를 변경한다. 예를 들어 route0..
