알고리즘 강좌 5회 - 그리디 #1 - 1. 그리디(Greedy)란? 이번에 우리가 공부해 볼 알고리즘은 그리디(Greedy)이다. 간단히 그리디에 대해 알아보면, 어원 그대로 상당히 탐욕적임을 느낄 수 있을 것이다. 그리디 알고리즘의 핵심은, 몇번의 선택을 하면서 답을 찾아내는데, 그 선택은 전에 결정했거나 앞으로 결정할 선택을 고려하지 않고, 그 당시의 상황에서만 가장 최적인 해를 취하는 것을 의미한다. 이런 과정을 거치기 때문에 그리디 알고리즘은 또 다른 중요한 특징을 가진다. 각 선택들은 부분적으로는 최적일지 모르나 전체적으로 보면 최적이 아닐 수도 있다는 점이다. 그래서 그리디 알고리즘을 쓸 때는 ‘전체적으로도 최적이 되는가?’ 라고 한 번 다시 생각해 봐야한다. ...이렇게 말해놓으면 무슨 소린지 잘 모르는 사람.. 더보기 알고리즘 강좌 4회 - 다이나믹 #3 - 7. 연습문제 풀이 자, 지난번 강좌에 나왔던 연습문제는 푸셨는가? 그럼 풀이법에 대해 설명하도록 하겠다. 이 문제도 동적계획법으로 풀린다.(당연하지.. 동적계획법 강좌에 나온 문젠데) 풀이법은 1차원 Up sequence문제와 별로 다를 것이 없다. 우선 이차원 배열 L(2차원 버젼이므로)을 다음과 같이 잡는다. L[i , j] = i행 j열에 있는 숫자로 끝나는 오름차순 수열의 최대길이 1차원 버젼과 별로 다르지 않다. 그럼 점화식은? L[i , j] = 1 L[i , j] = maximum( L[k1 , k2] + 1 ) 역시 1차원 버젼과 다를것은 별로 없다.(음.. 그러고 보니 "다를것이 없다"라는 말을 지난 강좌에서부터 너무 많이 쓰고 있는 듯..-_-) 그 전까지의 최대.. 더보기 알고리즘 강좌 3회 다이나믹 #2 - 4. 동적계획법의 실제 #3 자, 이번에도 역시 문제를 풀어봄으로서 동적계획법을 더 연습해 보자. 이번에 연습해 볼 문제도 역시 너무도 유명한 동적계획법 예제인 Knap sack문제이다. 설마 모르는 분이 있을까봐 문제설명을 드리자면. 소유권 이전 전문가(이하 도둑)가 직업인 동섭이는 어느 날 밤 귀금속 가게를 털었다. 숙련된 솜씨로 문을 따고 가게 안에 들어가 보니 오색찬란 금덩어리 은덩어리 보석덩어리 똥덩어리(엥~ 이건 아닌가) 등등 각종 덩어리들로 눈이 부실 지경이었다. 동섭의 마음 같아서는 몽땅 털어가고 싶지만 자신이 가져온 가방이 그렇게 큰 편이 되지 못했다. 그래서 가장 값을 높게 쳐주는 보석덩어리들만 가져가려고 한다. 동섭이 가장 비싸게 처분할 수 있도록 배낭을 채워주면 된.. 더보기 이전 1 ··· 31 32 33 34 35 36 다음