C++
그리디 알고리즘
그리디 알고리즘 그리디 알고리즘이란 지금 주어진 단계에서 가장 최선의 선택을 하는 기법이다. 이렇게 각 단계에서 최선의 결과를 선택한 결과 값이 전체적으로도 최선이기를 바라는 알고리즘이다. 일반적인 그리디 알고리즘 풀이 방법을 적어보자면 아래와 같은 흐름을 따른다. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다. 탐색 범위를 줄여도 올바른 답을 낸다는 것을 수학적으로 증명한다. 알고리즘을 구현한다. 그리디 알고리즘은 모든 경우에서 통하는 알고리즘은 아니다. 현재에 약간 손해보더라도 전체적으로 봤을 때는 이득인 경우에 통하지 않는데, 예를 들자면 유명한 마시멜로 이야기와 같이 지금 당장은 마시멜로를 1개를 받을 수 있지만 조금 기다리는 경우 2개를 받을 수 있는 경우 그리디 알고리즘으로 풀면 틀린 경우가..
BOJ 11052 카드 구매하기
boj 11052 카드 구매하기 - 문제 링크 https://www.acmicpc.net/problem/11052 - 문제 해설 DP가 작은 문제부터 쌓아나가서 구하고자 하는 값을 구하는 알고리즘임을 생각하면 쉽게 접근 방법을 찾을 수 있다. 나는 보통 DP로 문제를 풀 때 D[i]를 어떻게 나눌지를 생각하는 편이다. D[i]를 i개의 카드를 사는 금액의 최댓값이라고 지정하자. 그러면 아래와 같이 쪼갤 수 있다. D[i-1] + P[1] : 카드 1개가 들어있는 팩의 구매 값 + i-1개의 카드를 구매한 최댓값 D[i-2] + P[2] : 카드 2개가 들어있는 팩의 구매 값 + i-2개의 카드를 구매한 최댓값 . . . D[0] + P[i] : 카드 i개가 들어있는 팩의 구매 값 + 0개의 카드를 구매한..
BOJ 2011 암호코드
boj 2011 암호코드 - 문제 링크 https://www.acmicpc.net/problem/2011 - 문제 해설 DP를 이용하여 간단히 풀 수 있는 문제이다. D[i]가 주어진 암호의 i번째까지에서 해석할 수 있는 가짓수라고 하자. 끝 두자리의 숫자가 10 ~ 26 범위이면 한자리 숫자 2개가 될 수도 있고 두자리 숫자 1개가 될 수도 있다는 점을 생각하면 문제를 쉽게 해결할 수 있다. 생각해볼 사항들이 무엇이 있는지 살펴보자. 암호의 처음 숫자가 0일 시에는 0을 출력한다. 맨 끝 한 자리가 0인 경우는 맨 끝 두 자리가 10, 20인 경우를 제외하고는 암호가 성립할 수 없다. 예를 들면 맨 끝 두 자리가 00, 30, 40 ... 90 같은 경우는 대응되는 알파벳이 없기에 암호가 성립되지 못한..
이분탐색(Binary search)
- 이분탐색이란? 이분탐색이란 정렬이 되어있는 배열에서 원하는 데이터를 찾기 위해 순서대로 찾아보는 방법 대신에 탐색 범위를 절반으로 줄여나가며 찾는 탐색 방법이다. boj 문제 중에 이분탐색을 요구하는 문제가 있어서 문제를 보면서 이분탐색의 개념을 정리했다. - boj 1920 수 찾기 https://www.acmicpc.net/problem/1920 예시로 A 배열에 '3 5 6 9 10 12 14 26 35 41' 이 주어졌다고 하고, 14가 있는지 알아본다고 하자. 입력 받은 후에 sort 함수를 이용해서 정렬하면 앞과 같이 정렬된 상태일 것이다. 원래 문제는 A 안에 14가 있는지만 확인하면 되지만, 14가 A 안에서 위치하는 인덱스를 반환하는 함수를 구현해보려고 한다. st와 e..
BOJ 2225 합분해
boj 2225 합분해 - 문제 링크 https://www.acmicpc.net/problem/2225 - 문제 해설 테이블 D[i][j]를 n이 i이고 k가 j일 때의 경우의 수라고 정의한다. 경우의 수를 어떻게 나눌지 잘 떠오르지 않아서 일단 n과 k에 따른 경우의 수를 작은 수부터 나열해보았다. 표로 나열해보면서 점화식을 유추해보자. 예를 들어 D[3][3]을 구한다고 해보자. 3을 3가지 수의 합으로 나타내는 경우는 0부터 3까지의 수를 2가지 수의 합으로 나타낸 것에다가 3이 되기위해 필요한 수를 더하면 된다. 0을 2가지 수의 합으로 나타낸 경우 : (0 + 0) 1을 2가지 수의 합으로 나타낸 경우 : (0 + 1), (1 + 0) 2를 2가지 수의 합으로 나타낸 경우 : (0 + 2), (..