컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 문제 해결 알고리즘 0만 없으면 참 간단한 문제인데.. 0 때문에 어려웠다. 구현이 빡셌던 문제 우선 글자 수별로 구분해줘야하는데 글자 수가 1일 때, 2일 때, 3이상일 때로 구분해준다 글자 수가 1일 때, 숫자가 0이면 0을 출력해주고, 0이 아니면 1을 배열 값에 넣어준다. 글자 수가 2일 때, if(num == 10 || num == 20) v[1] = 1; else if((11

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 알고리즘 문제 해결 동적계획법(다이나믹 프로그래밍)을 쓰는 문제 연속된 세 개의 계단을 밟을 수 없으므로 이차배열을 선언해준다. 연속으로 밟은 계단의 갯수를 배열로 알 수 있게 설정한다. 만약 2개의 계단을 밟았을 경우 두 칸을 넘게 한다. 반복문이 끝난 후, 마지막으로 N번째 행에서 최댓값을 구해서 출력한다. 소스 코드 #include using namespace std; int main(){ int N; ..

탐욕 알고리즘이란? 작은 사례로 나누지 않고 탐욕스러운 선택을 sequence로 계속하면 답에 가까워진다. 선택과정(selection procedure) : 집합에 추가할 다음 원소를 고른다. 그 당시 최적을 선택하는 탐욕 기준에 따라 선택한다. 적절성검사(feasibility check) : 새로운 집합이 해답이 되기 적절한지 검사한다. 해답점검(solution check) : 새로운 집합이 문제의 해답인지 결정한다. 이 과정이 동시다발적으로 진행된다. 거스름돈을 고르는 탐욕 알고리즘 예를 들어 돈이 50원, 25원, 10원, 5원, 1원이 있고 31원을 거슬러 주어야 할 때, (이때, 거슬러 주는 각각의 동전들은 여러개이다.) 1. 50원을 집었다가 내려놓는다. 2. 25원을 집는다. 3. 25원을 ..