2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 문제 읽기 예전에 동전 1 문제를 풀었었는데 DP 문제를 잘 못하다 보니 그때도 고생했었다. 결국 풀지 못하고 블로그 찾아봤던 기억이.. 이번에는 풀어보자! 하고 열심히 적으면서 했는데 예전 풀이가 기억나서 거기에 갇혀 좀 헤맸다. 기억이 아니라 논리에 의존해서 DP 문제를 풀고 싶구나.. 많이 풀다 보면 되겠지! 하는 생각이다. 문제 풀이 여러 차례 삽질했다. 바로 최종 문제 풀이로 넘어가도 상관 없을 듯 하다. 1차 삽질 : ..

9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제 풀기 처음에 해당 문제를 봤을 때는 뭐지 했지만, 직접 그려보니 변의 길이가 어떻게 만들어지는지 규칙이 보였다. 그래서 다음과 같은 점화식을 만들어낼 수 있었다. 점화식 P[n] = P[n-1] + P[n-5] (n ≥ 5) P[0] = 0 P[k] = 1 (k = 1, 2, 3) P[k] = 2 (k = 4) 또한 문제에서 N의 범위가 1부터 100 사이 값이기 때문에 자료구조를 다음과 같이 크기 101인 배열로 정의하고, 미리 배열의 값을 채운 다음 입력 받..

9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 읽기 프로그래밍을 많이 해보지 않은 상황에서 처음으로 해당 문제를 보게 되면 모든 경우의 수를 세어 봐야 하나? 라는 생각이 들 수 있다. 하지만 입력의 크기인 N이 최대 10만이기 때문에 모든 경우를 세기에는 숫자가 너무 크다. 이럴 때 DP를 활용할 수 있다. 해당 문제는 DP의 기본적인 문제 중 하나이다. DP 문제는 DP 문제라는 것을 아는 것이 가장 어렵다고 한다. 어쩔 수 없이 많이 그려보며 많은 문제를 푸는 방법밖에 없는 것 같다. ..

문제 읽기 해당 문제는 가장 기본적인 0-1 Knapsack 문제이다. DP에 대한 이해를 위해 직접 표를 그려보자 예제 1 4 7 0: 6 13 (무게, 가치) 1: 4 8 2: 3 6 3: 5 12 물건개수/남은부피 1 2 3 4 5 6 7 0 0 0 0 0 0 13 13 1 0 0 0 8 8 13 13 2 0 0 6 8 8 13 14 3 0 0 6 8 12 13 14 둘 다 인덱스를 0부터 시작하면 남은 부피의 경우에는 비교를 하게 되기 때문에 인덱스 + 1을 한 상태가 실제 남은 부피가 되고, 이렇게 비교해줘야 한다. 따라서 그냥 k의 경우에는 1부터 k까지 설정하는 것이 좋다. 또한 N도 이전 컬럼을 보면서 비교하기 다음 컬럼을 채워나가기 떄문에 1부터 시작하는 것이 좋다. 즉, 점화식을 보고 ..

자바에서는 Arrays.sort()와 Collections.sort() 메서드를 활용하여 정렬을 쉽게 수행할 수 있다. 그렇다면 각 메서드는 여러 자바 정렬 알고리즘 중에 어떤 메서드로 구현되어 있을까? Arrays.sort() Arrays.sort는 배열 원소가 primitive type일 경우와 object type일 경우 다른 알고리즘이 적용된다. 배열 원소 - Primitive Type - Dual Pivot Quick Sort 배열 원소가 primitive type인 경우, byte, char, short는 집합의 크기가 작기 때문에 배열의 크기가 크면 count sort를 활용한다. 그렇지 않은 경우에는 먼저 dual pivot quick sort를 활용한다. Dual Pivot Quick S..

19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 문제 읽기 문제를 읽으면서 다음과 같이 적어보았다. 기본은 시뮬레이션 문제이지만, dfs 개념도 필요한 문제이다. 0. 상어가 (0,0)에 들어옴(초기 상태 설정) 1. 물고기 작은 수부터 전부 한 칸씩 이동 (빈 칸 또는 물고기 칸만 가능. 45도 반 시계 회전.) 2. 상어 이동. 해당 방향대로 물고기가 있는 칸으로만 가능. (모든 경우의 수를 생각해서 dfs) => 상어의 이동 경로가 여러가지이기 때문에 반복문이 아닌 dfs로 수행하자. 그..