본문 바로가기
728x90
반응형

전체 글77

[algorithm] 백준 - 1,2,3 더하기 5 DP문제이다. n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 것이다. 여기서 중요한 점은 같은 수를 두 번 이상 연속해서 사용하면 안된다는 것이다. 그렇기에 뒷자리수를 함께 기록해야한다. 뒷자리수가 1일 때 다음 수는 2나 3이, 2이면 다음 수는 1이나 3, 3이면 다음 수는 1이나 2 여야한다. 이것을 점화식으로 표현해보자면, dp[i][1] = dp[i - 1][2] + dp[i - 1][3]; dp[i][2] = dp[i - 2][1] + dp[i -2][3]; dp[i][3] = dp[i - 3][1] + dp[i - 3][2]; 전체 코드는 이렇다. // 1, 2, 3 더하기 5 #include using namespace std; int main(void){ long long te.. 2020. 11. 2.
[algorithm] 백준 - 카드 구매하기 이 문제는 전형적인 DP 문제이다. 포인트는 N개의 카드팩을 사는데 가장 비싼 값을 반환하는 것이다. 이 곳에는 DP 배열과 P 배열을 변수로 사용한다. DP 배열은 n개의 카드팩을 사는 방법 중 가장 큰 돈으로 살 수 있는 경우를 저장한다. P 배열은 카드 n개가 포함된 카드팩의 값을 저장한다. 예를 들어보자, 카드팩을 4개 산다고 가정했을 때 DP[4] = max( P[4] + DP[4 - 4 = 0], P[3] + DP[4 - 3 = 1], P[2] + DP[4 - 2 = 2], P[1] + DP[4 - 1 = 3] ) 가 되고, 이를 구하기 위해선 DP[0], DP[1], DP[2], DP[3]을 필요로 하게 된다. 그럼 이를 식으로 표현해보면, DP[N] = max(P[N] + DP[N - i].. 2020. 11. 2.
[algorithm] 백준 - 좋은 수열 이 문제는 두가지 해결책을 내야했다. 좋은 수열을 걸러내는 작업 dfs 좋은 수열을 걸러내는 작업 비교해야하는 크기 비교해야하는 인덱스 위치 1212 123123 12341234 와 같이 (길이 / 2) 만큼의 수열을 비교해야한다는 것을 알 수 있다. 12341233 -- 비교해야하는 수열의 크기가 1일 때 6,7을 비교한다. 12341212 -- 비교해야하는 수열의 크기가 2일 때 45 67을 비교한다. 12345345 -- 비교해야하는 수열의 크기가 3일 때 234 567을 비교한다. 12341234 -- -- 비교해야하는 수열의 크기가 4일 때 0123 4567을 비교한다. 이것을 수식으로 표현해보자면, 수열의 크기는 i, 변하는 값은 j로 했을 때 arr[len - 2*i + j] arr[len .. 2020. 10. 30.
[algorithm] 백준 - 암호만들기 조합과 동일하다. 이 곳에서 조건이 있는데 모음은 1개 이상, 자음은 2개 이상이어야 한다. 알파벳이 모음일 경우 모음변수를 하나 증가시키고, 자음일 경우 자음 변수를 하나 증가시킨다. if(isVowel(realVector[index])){ combination(vowelCount + 1, consonantCount, index + 1, alphaVector, realVector, target - 1); } else{ combination(vowelCount, consonantCount + 1, index + 1, alphaVector, realVector, target - 1); } target에 도달하고, 조건에 일치할 경우 알파벳 열을 출력하면 된다. if(vowelCount >= 1 && con.. 2020. 10. 30.
728x90
반응형

티스토리툴바