Computer Science 썸네일형 리스트형 알고리즘 강좌 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문제이다. 설마 모르는 분이 있을까봐 문제설명을 드리자면. 소유권 이전 전문가(이하 도둑)가 직업인 동섭이는 어느 날 밤 귀금속 가게를 털었다. 숙련된 솜씨로 문을 따고 가게 안에 들어가 보니 오색찬란 금덩어리 은덩어리 보석덩어리 똥덩어리(엥~ 이건 아닌가) 등등 각종 덩어리들로 눈이 부실 지경이었다. 동섭의 마음 같아서는 몽땅 털어가고 싶지만 자신이 가져온 가방이 그렇게 큰 편이 되지 못했다. 그래서 가장 값을 높게 쳐주는 보석덩어리들만 가져가려고 한다. 동섭이 가장 비싸게 처분할 수 있도록 배낭을 채워주면 된.. 더보기 알고리즘 강좌 2회 알고리즘 강좌 2회 - 다이나믹 #1 - 1. 동적계획법의 특징 다이나믹 프로그래밍(dynamic programming : 이하 동적계획법) 이란 무엇일까. 이 역시 문제를 푸는 알고리즘의 일종이다. 다이나믹의 가장 큰 특징은 이것이다. "작은 문제들을 해결한 다음 이 결과들을 바탕으로 더 큰 문제의 해답을 찾는 방법이다." 물론 이 말 한마디만으로 동적계획법에 대해 알수는 없다. 동적계획법의 특징들을 하나씩 살펴보자. 우선, 동적계획법은 작은문제를 먼저 해결하고 그 결과를 저장한 다음, 나중에 그 결과가 필요할때 다시 계산하는 대신 저장된 결과를 이용한다. 탑을 쌓을때 밑둥부터 차근차근 쌓아가는 것 처럼, 그 전의 결과를 바탕으로 새로운 결과를 만들어 낸다. 이를 상향식 접근방법이라고 한다. 나중에 배.. 더보기 알고리즘 강좌 1회 알고리즘 강좌 1회 - 알고리즘 개론 - 1. 알고리즘 알고리즘을 한마디로 정의하면, "어떤 문제의 해답을 찾아주는 일반적인 단계별 절차" 간단한 예를 하나 들어보자. 여러분은 전화번호부에서 사람을 찾을때 어떻게 찾는가? 혹시 전화번호부의 첫장부터 끝장까지 넘겨가면서 원하는 사람의 이름을 찾는가?-_-;; 아마 정상적인 사회생활이 가능한 사람이라면 그런 미친짓은 하지 않으리라 믿는다. 그러면 어떻게 찾는가? 그렇다. 여러분도 아시다시피 전화번호부에 있는 사람들의 이름은 가나다 순으로 정렬이 되어있다. "정동섭"이라는 인물을 찾고자 할 경우 전화번호부의 'ㅈ'항목을 찾은 다음, '정'으로 시작하는 사람들의 이름을 찾고, '동'이라는 글자가 이어지는 이름을 찾아낸 후, 마지막으로 '섭'을 찾으면 "정동섭"이.. 더보기 이전 1 2 3 4 다음