목록전체 글 (245)
말랑한 하루
※ 소스코드는 각 문제 설명 하단에 를 통해 확인하실 수 있습니다. [gold5, 2240 자두나무] - 다이나믹 프로그래밍(DP) T초동안, 어떤 위치에서, 몇번이나 움직이며 자두를 받아가는지를 확인해야한다 즉, "dp[T 초에][W 만큼 움직이면][1/2 번 위치에서] = 자두를 받는다"로 볼 수 있고 T초가 지나갈 때 자두는 현재 위치에서 움직일지, 움직이지 말지 선택할 수 있다 이를 통해 유도할 수 있는 점화식은 1번나무에는 1초전 움직이지 않은 1번나무와, 2번나무에서 움직였을 때를 비교하고 dp[T][W][1] = max(dp[T-1][W][1], dp[T-1][W-1][2]); 2번나무에는 1초전 움직이지 않은 2번나무와, 1번나무에서 움직였을 때를 비교할 수 있다 dp[T][W][2] = ..
※ 소스코드는 각 문제 설명 하단에 를 통해 확인하실 수 있습니다. [gold5, 11398 연속합2] - 다이나믹 프로그래밍(DP) 수를 제거하지 않은 경우와 제거한 경우를 각각 sum[i][0], sum[i][1]배열에 저장한다 할 때 수를 제거하지 않는 경우엔 연속된 구간의 합이 수열의 다음 수보다 작은 경우, 수열의 다음수 부터 새로운 구간을 시작하게 된다 이를 통해 연속합을 저장하는 sum[i][0]배열의 값은 max(sum[i - 1][0] + num[i], num[i])라는 점화식을 끌어낼 수 있다 현재를 기준으로 수를 제거한 경우를 생각해보면 1) 현재를 제거하는 경우: sum[i - 1][0] 2) 이미 제거된 경우: sum[i - 1][1] + num[i] 이와 같은 두 식이 나오게되고..
※ 소스코드는 각 문제 설명 하단에 를 통해 확인하실 수 있습니다. [sliver 1, 1309 동물원] - 다이나믹 프로그래밍(DP) N번째 줄에 사자를 배치할 수 있는 경우는 다음과 같다. (미배치(0), 왼쪽(1), 오른쪽(2)) 1) 모두 없는 경우: 왼쪽, 오른쪽, 미배치 → dp[n][0] = dp[n-1][0] + dp[n-1][1] + dp[n-1][2]; 2) 왼쪽 칸에 있는 경우: 오른쪽, 미배치 → dp[n][1] = dp[n-1][0] + dp[n-1][2]; 3) 오른쪽 칸에 있는 경우: 왼쪽, 미배치 → dp[n][2] = dp[n-1][0] + dp[n-1][1]; 이를 종합해보면 for(int i=2;i
※ 소스코드는 각 문제 설명 하단에 를 통해 확인하실 수 있습니다. [gold5, 1068 트리] - 깊이우선탐색(DFS) 간단한 DFS문제이나, 백트래킹 방식으로 접근하면 예외를 쉽게 생각할 수 있다 1) 현재 노드가 삭제된 노드인 경우, 리프 노드 개수를 구할 수 없으므로 0 반환 2) 현재 노드에게 자식이 없는 경우, 자신이 리프 노드이므로 1 반환 3) 자식이 있음에도 리프 노드값이 반한되지 않은 경우, 삭제된 노드를 자식으로 가지고 있었으므로 자신이 리프 노드가 되어 1 반환 더보기 #include #include #pragma warning(disable:4996) using namespace std; int tree[51]; int child[51]; vector parent[51]; int..
※ 소스코드는 각 문제 설명 하단에 를 통해 확인하실 수 있습니다. [gold5, 2565 전깃줄] - 최장증가부분수열(LIS) LIS의 가장 큰 특징은, 마지막 원소가 가능한 작을수록 더 긴 LIS를 생성할 수 있다 그래서 lower_bound를 활용하여, LIS의 원소를 업데이트 하면 최종 길이를 구할 수 있다 더보기 #include #include #pragma warning(disable:4996) using namespace std; int N; struct Data { int idx, conn; }; Data elec_line[101]; bool elecCompare(Data a, Data b) { return a.idx < b.idx; } int main() { scanf("%d", &N);..
※ 소스코드는 각 문제 설명 하단에 를 통해 확인하실 수 있습니다. [gold 5, 12865 평범한 배낭] - 0/1 Knapsack 흔히 배낭 문제들은 1)짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 2)짐을 쪼갤 수 없는 경우(0이상의 정수)로 나뉜다 1) 짐을 쪼갤 수 있는 경우를 분할 가능 배낭 문제(Fractional) 2) 짐을 쪼갤 수 없는 경우를 배낭 문제(0/1 Knapsack)라 부른다 0/1 Knapsack은 다음과 같이 점화식이 정해져 있다(i= 물건 번호, j= 현재 배낭무게) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]]) + V[i]; 단, 점화식에서 현재 배낭무게와(j)와 현재 물건의 무게(W[i])의값의 차가 음수가 될..
※ 소스코드는 각 문제 설명 하단에 를 통해 확인하실 수 있습니다. [bronze1, 1816 암호키] 구현 + 소수 visual studio에서 S를 1번입력 받고 출력한 뒤 종료되는 비정상적인 작동을 하였으나, 제출 시에는 문제가없었다. 소수 배열 선언 시, 크기를 MAX로 지정하고, MAX를 포함한 범위까지 루프를 돌렸기에 문제가 발생했다. visual studio에서 비정상적인 작동을 하는 이유가, prime_number[MAX]배열이 메모리에 잡힌 후, N이 메모리에 추가되었기 때문에 N의 메모리 주소가 prime_number[MAX+1]메모리 주소로 착각되어, N=ture가 대입되고 루프가 1번으로 마무리된 것이라 한다 그렇다고 N을 먼저 선언하고 prime_number[MAX]로 할때나, N..