[백준] 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..
[백준] 17779 게리맨더링2
주어진 조건에 따라 구현하는 문제이다. 먼저 모든 구역의 인구의 합을 구하고 1-4 구역을 나눈 뒤 해당 인구를 모두 제외하면 5구역의 인구를 구할 수 있다. 경계선을 먼저 만든 후 구역을 나눌때 주의해야할 사항이 있다. 만일 경계선을 만날 경우 다음행으로 바로 넘어가도록 코드를 작성할 경우 1, 3번 구역은 정상적으로 나뉘어진다. 하지만 2, 4 번 구역은 경계선의 우측에 위치하기 때문에 경계선에서 부터 인덱스가 시작할 수 있다. 따라서 열의 역순으로 구역을 채워나가야한다. Python Java
[백준] 17140 이차원 배열과 연산
R과 C 연산에 따라 나온 각각 행과 열에 속하는 수를 1. 등장 횟수, 2. 수의 크기(오름 차순)을 기준으로 정렬하는 문제이다. 시간이 100까지 반복되기 떄문에 매 초마다 파이썬 정렬 내장 함수를 사용하고 싶지 않아 dict와 count 배열을 사용하여 정렬하였다. count 배열에는 각각의 행 혹은 열에있는 수들의 등장 횟수를 저장한 배열이다. dict에서는 등장 횟수를 key 로 하여 숫자 배열이 저장된다. 저장된 dict의 key 값을 1 ~ 100 까지 순회하여 key와 value를 가지고 새로운 배열을 만들면 된다. Python
[백준] 1941 소문난 칠공주
소문난 칠공주를 결성할 수 있는 모든 경우의 수를 구하는 문제이다. 브루트 포스, 백트래킹 알고리즘 유형에 해당한다. 단, 소문난 칠공주는 가로 또는 세로로 모두 인접해야하며, 이다솜파가 과반수(4)이상 이어야 한다. 여학생반의 크기는 5*5 크기로 고정되어 있기 떄문에 학생들을 0 ~ 24로 인덱싱한다. n번 학생의 위치는 (n / 5, n%5 )에 위치한다. DFS를 통해 0번 부터 24번 학생까지 순회한다. 현재 학생을 I라고 하면 I 학생은 이다솜파, 임도연파 중 하나이며 소문난 칠공주에 포함할 지 결정한다. 7명을 모두 소집한 경우 모두 인접한지 확인한다. 시작점을 기준으로 상, 하, 좌, 우 인접한 노드를 DFS로 방문하여 인접한 경우 카운트를 1 증가시키고 7이 되는 경우 모두 인접한 것으로..
[백준] 1600 말이 되고픈 원숭이
원숭이가 (0, 0) 지점에서 (W-1, H-1)까지 이동하는 이동 횟수의 최소값을 구하는 문제이다. 처음 문제를 접하고 DP를 사용하면 해결 할 수 있을 것 같아 시도하였지만, 해결하지 못했다. 다른 풀이를 보니 BFS로 해결할 수 있었다. 먼저 DP로 왜 해결할 수 없었는 지에 대해서 설명한다. 입력 1 6 6 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 출력(정상) 8 위 값이 입력으로 주어져 DFS & DP 를 수행하면 중간 지점에 아래와 같은 결과가 출력된다. [0, 0, 0, 0, 0, 11] [1, 0, 0, 0, 0, 10] [2, 3, 8, 9, 8, 9] [0, 4, 7, 8, 9, 10] [0, 5, ..