궤도

문제 풀이 동적계획법의 대표적인 문제 중 하나이다. 생각해보니 동적계획법은 대표하는 문제가 많은 것 같다...아무튼 이전까지의 문제들은 초기값을 받은 배열을 그대로 갱신하면서 값을 구했다. 하지만 이 문제는 그러면 안된다. i번째 계단을 밟는다고 생각하자. i번째 계단을 밟기 위해선 어떤 경로로 계단을 밟아야 했을까? i-3번째 계단을 밟고 i-1번째 계단을 밟은 뒤 i번째 계단을 밟거나(3번연속 계단을 밟을 수 없기 때문) i-2번째 계단을 밟고 i-1번째 계단을 건너뛰고 i번째 계단을 밟을 수 있을 것이다. 배열을 1개만 사용하면 안되는 이유가 이것이다. i번째의 계산을 할 때 i-1번째만 연속적으로 참조하던 지난 문제들과 달리 이건 불연속적으로? 지난 값들을 참고하기 때문에 초기 입력을 저장할 배열..

문제 풀이 이 문제도 동적계획법의 대표적인 문제 중 하나이다. 대표적인 풀이법에는 위에서 아래로 내려가는 방법과 아래에서 위로 올라가는 방법이 있는데, 후자가 훨씬 코드를 간단하게 짤 수 있다. i번째 줄을 계산한다고 하자. i번째 줄의 0번째(지금은 3)를 갱신하려면 i+1번째 줄의 0번째(7)와 더하거나 i+1번째 줄의 1번째(6)와 더하거나 이다. 둘 중 더 큰 값을 취하면 된다. 일반화하면 i번째 줄의 j번째 값을 갱신하려면 i+1번째 줄의 j번째 값과 i+1번째 줄의 j+1번째 값을 비교해 더 큰 값과 더하면 되는 것이다. 이를 n-1번째줄부터 1번째 줄까지 반복한 뒤 1번째 줄의 1번째 값을 리턴하면 된다. 소스코드 #include #include using namespace std; int ..

문제 풀이 이걸 이렇게 표현하는게 맞나? 싶지만 동적계획법 문제를 풀 때는 i번째가 ~라면 i-1번째는 뭐였을까? 라는 방법으로 접근하는 것이 좋다. 보통 문제를 풀 때 0번째가 이거라면 1번째는 이게 되고 2번째는...식으로 생각하기 마련인데 동적계획법은 반대 방향으로 가야한다. 이 문제도 마찬가지이다. 첫번째 두번째 집이 무슨 색인지는 궁금하지 않고, i번째 집을 빨간색으로 칠한다고 생각해보자. i번째 집이 빨간색이라면 i-1번째 집은 파란색(1번 경우)이나 초록색(2번 경우)일 것이다. 그렇다면 i번째 집을 빨간색으로 칠할 때의 최솟값은? 1번 경우와 2번 경우 중 더 작은 값을 택하면 될 것이다. 소스코드 #include #include using namespace std; int house[10..

문제 풀이 3차원 배열을 써야겠다! 라는 생각을 했다면 빨리 해결했을 것이고... 나처럼 거의 쓸 일 없는 3차원 배열을 대충 기억속에서 지우고 살았던 사람이라면 좀 걸렸을지도 모르겠다. 난 시간초과에 대한 강박이 있는데 그래서 이 문제에 재귀함수 호출을 전혀 쓰지 않았다. 조건을 보니 아무리 for문이 많이 돌아도 최대 20*20*20 = 8000번이길래 3중 for루프를 사용했다. 근데 다른 사람들의 풀이를 보니 거의 다 재귀를 사용하셨던데 뭐 이런 풀이도 있다는 걸 보는 정도로 봐주길... 소스코드 #include using namespace std; int w_func(int a, int b, int c) { //재귀를 약간 써도 시간초과가 생기지는 않는가 보다... int w[21][21][21..

문제 풀이 동적계획법의 입문(?) 문제이다. 정확히 말하자면 찐 입문은 재귀 함수로 구현된 피보나치 함수를 동적계획법으로 구현하는 것인데...거의 같은 구조이다. n>1 일 때 fib(n) = fib(n-1) + fib(n-2)이다. 그렇다면 fib(n)에서 0이 호출된 횟수는? 당연히 fib(n-1)에서 0을 호출한 횟수와 fib(n-2)에서 0을 호출한 횟수를 더한 값일 것이다. 1이 호출된 횟수 역시 마찬가지일 것이고... 소스코드 #include using namespace std; void fibo_cnt(int num) { int zero_cnt[41] = { 0, }; int one_cnt[41] = { 0, }; for (int i = 0; i

문제 풀이 팀을 나누는게 가장 중요한 문제이다. 6명이 있을 때 3명을 고르고 나면 선택받은 3명은 스타트팀 선택받지 못한 3명은 링크팀에 넣어 계산하면 될 것이다. 근데, (1,2,3)번 사람을 고르는 것과 (2,1,3)번 사람을 고르는 것은 같은 경우이다. 이런 경우를 어떻게 제외할 수 있을까? myunji.tistory.com/198?category=1154147 [백준] 15650번 : N과 M (2) 문제 풀이 myunji.tistory.com/73?category=1154147 [백준] 15649번 : N과 M (1) 문제 풀이 백트래킹의 기본 문제이다. 백트래킹은 해당 value의 방문 여부를 따지며 주로 재귀함수로 구현하는 경우가 많다. 그렇.. myunji.tistory.com 위 문제는..

문제 풀이 숫자의 순서는 고정되어 있으니 백트래킹의 대상이 되는 것은 사칙연산 기호 뿐이다. 종료 조건을 만나면 함수를 종료하던 이전 문제들과 달리 노드의 끝에 다다르면 최댓값, 최솟값을 갱신하며 모든 경우의 수를 따져야 한다. 소스코드 #include using namespace std; int min_num = 1000000000; int max_num = -1000000000; int arr[11]; int op[4]; int N; int cal(int a, int b, int op) { //계산 int result = 0; switch (op) { case 0: result = a + b; break; case 1: result = a - b; break; case 2: result = a * b..

문제 풀이 입력을 어떻게 처리하여 어떤 순서로 스도쿠의 빈공간을 채워나갈지 고민을 많이했다. 처음에는 1행->9행으로 값을 채우고 그 다음에 1열->9열로 값을 채우고 마지막으론 구역별로..?라고 생각하다가 너무 복잡해질 것 같다는 생각이 들었다. 그러다 내가 실제로 스도쿠를 볼 때 어떻게 푸는지 생각했다. 보통 사람들은 먼저 빈공간을 찾아가서 그 공간의 행, 열, 구역을 한번에 확인한 뒤 값을 채워나간다. 그럼 코드도 이런식으로 짜면되지 않을까? 싶었다. 입력을 받으면서 빈공간을 봐둔 다음에 각각의 빈공간마다 1~9를 넣어보면서 그 공간의 행, 열, 구역의 숫자와 비교하면 될 것 같았다. 이 아이디어를 떠올리니 나머지는 크게 어렵지 않았다. 소스코드 #include using namespace std;..