본문 바로가기

Algorithm76

[알고리즘] 내려가기 (백준 2096번) 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 다이나믹 프로그래밍 문제다. 최소, 최대 값을 묻는 문제인데 이전에도 자주 풀어 본 적이 있는 유형이다. Solution 우선 max_dp와 min_dp로 나누어서 각각 최대값, 최소값을 구하는 dp 배열로 만든다. 여기서 최적화할 수 있는 방법은, 최대, 최소값을 구하기 위해서는 max_dp[i][3] 과 max_dp[i-1][3] 만 필요하면 되기 때문에 행이 2개만 있으면 된다. 그래서 max_dp, min_dp 에 필요한 원소 개수는 12개만 있으면 된다. N만큼 반복.. 2020. 10. 29.
[알고리즘] 수 묶기 (백준 1744번) 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 그리디하게 풀 수 있는 문제이다. 수를 정렬했을 때 양수 기준으로 가장 큰 수부터 곱해나간다. 단, 1과 쌍이 지어지는 경우는 그냥 더하는게 더 수가 크기 때문에 항상 list[i] * list[i+1]와 list[i] + list[i+1] 중 어떤게 더 큰지 비교해가면서 더한다. 음수는 반대로 가장 작은 수부터 곱해야지 가장 큰 값이 나온다. EX) (-5 * -1 = 5) > (-4 * -1 = 4) Solution import java.io.Buffere.. 2020. 10. 22.
[알고리즘] 단어 수학 (백준 1339번) 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 나올 수 있는 알파벳 종류가 10가지이므로 백트랙킹으로 모든 순열을 구해도 된다. 순열을 구할 때 허용되는 최대 시간복잡도가 10!인데 알파벳이 딱 10가지이기 때문이다. 하지만 수학 수식을 활용해서 그리디 하게 풀면 훨씬 쉽게 풀 수 있다. Solution 'ABC', 'BCD' 라는 문자가 있다고 가정해보겠다. 이 두가지 문자를 수학 수식으로 나타내면 'ABC' : 100A + 10B + 1C 'BCD' : 100B + 10C + 1D 로 표현된다. 그.. 2020. 10. 21.
[알고리즘] 합분해 (백준 2225번) 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 다이나믹 프로그래밍 문제고 예전에 풀어본 적은 있으나 다 까먹었다... 근래에 DP 문제를 거의 안 풀어서 그런가 비교적 쉬운 난이도인데도 어떻게 풀어야할 지 한참 헤멘다... Solution dp[N+1][K+1] 배열을 만든다. dp[i][j]는 i 수를 j개의 수로 이용해서 만들 수 있는 경우의 수다. dp[i][0] = 0, dp[i][1] = 1이다. 즉 0개의 수를 이용해서 정수를 만들 수 있는 경우는 없고 1개의 수를 이용해서 정수를 만드는 경우는 자기자신 딱 하나 밖에 없다. i = k + (i-k)라고 쳤을 때, [k][j-1] * [i-k][1] = [k][j-1]이다... 2020. 10. 20.

티스토리툴바