본문 바로가기
반응형

[백준]214

[BaekJoon/백준] 1931번 [동적계획법 VS 그리디 알고리즘 정리 2차] | 복습 1회 완료 문제를 풀기 전, 동적계획법과 그리디알고리즘에 대해 조금 알아본다. 관심없다면 건너뛰면 된다. 동적계획법은 경우의 수를 모두 검토하기 위해 점화식을 통해 구성되는 반면, 그리디 알고리즘은 순간순간의 최적의 선택지를 선택하므로 그렇지 않는다는 차이점이 있는 것 같다. 그리디 알고리즘을 선택하기 위해선 1. 탐욕스러운 선택 조건 탐욕적 선택은 항상 안전하다는 것을 보여야 한다. 즉, 탐욕적 선택으로 전체 문제의 최적해를 반드시 구할 수 있다는 것을 보여야 한다. 2. 최적 부분 구조 조건 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적의 해결 방법이다는 조건. 두 조건을 만족해야 한다. 1번에서 말하는 것은 '각각의 상황마다 최적의 조건을 선택해도 이후의 최적의 선택에 실질적으로 영향을 주지 .. 2021. 2. 4.
[BaekJoon/백준] 11047번 [ 그리디 알고리즘 ] 배수관계로 내림차순으로되어있으니 그리디알고리즘을 사용할 수 있다. 각 단계마다 해당 값보다 크지 않은 수 중 가장 큰 수를 최적값으로 선택해주면 된다. 동전으로 A1 A2 A3가 오름차순으로 차례로 주어졌다고 봤을 때 A3 = A2 x X 라고 볼 수 있다. 배수이기 때문에. 이러한 특성 덕에 각 단계에서 해당 값보다 크지 않은 최적의 수를 선택해주면 된다. 만약 배수관계가 아닌 경우, 800원의 가치값에 100 400 500원이 주어진다면, 이는 그리디알고리즘으로 풀 수 없다. 500원 x 1 + 100원 x 3 = 4개 400원 x 2 = 2개 이기 때문이다. 문제에서는 각 수가 배수관계이기 때문에, 가치값보다 A3가 작다면, A3를 사용하는게 A2를 여러번 사용하는 것 보다 최적일 수 밖에 없다. .. 2021. 2. 3.
[BaekJoon/백준] 12865번 < 냅색 문제 > | 복습 1회 완료 알고리즘과 자료구조를 못하는 내가, 코테 문제들에서 항상 풀지 못한 유형의 문제다. 내가 항상 시도했던 방식은, dp 접근법이 아닌 백트래킹 접근법이였고, 코드는 아래와 같다. #include int N; int W; int o[100][2]; int check[100]; int MAX = 0; void pick(int w, int v) { for(int i = 0; i < N; i++) { if(!check[i] && w + o[i][0] dp[0][k] 는 0번째 물건에 대한 값이므로 불필요하고, dp[k][0]은 무게가 0인 경우니까 불필요하다. - 1차원 dp 배열 위에서는 2차원 dp배열로 문제를 풀었는데, 1차원 dp배열로도 문제 풀이가 가능하며, 더 빠르기까지 하다. 1차원 dp 풀이에서도 .. 2021. 2. 2.
[BaekJoon/백준] 1912번 | 복습 1회 완료 연속합을 구하는 문제. 경우의 수를 잘 생각해내야 하는게 동적계획법 문제 풀이에 있어서 중요한 시작점인 것 같다. 말하자면 점화식을 세우는 것.. 처음에는 다소 단순하게 문제에 접근했다. 마이너스가 껴있으면 당연히 연속합이 최대가 되지 못할 것이라고 생각해서, 그냥 수를 입력받다가 마이너스를 만나면 새출발하는 느낌으로 코드를 구성했다. (동적계획법느낌의 코드는 아니였다) 그러다가 테스트케이스에서 반례를 발견했다. 10 2 1 -4 3 4 -4 6 5 -5 1 마이너스가 껴있더라도 연속합이 최대가 될 수도 있다는 것. 그래서 다시 처음부터 시작했다. 우선 경우의 수를 4가지로 나열했고, 이걸 다시 두가지로 추릴 수 있었다. 1. 이전까지의 최대합에서 지금껄 선택한다. 2. 이전까지의 최대합에서 지금껄 선택.. 2021. 2. 1.
반응형

티스토리툴바