1. Sorting Problem 이란? Input n개의 숫자로 이루어진 sequence sequence를 이루는 각 요소를 KEY, 혹은 ITEM이라고 부름. EX ) OUTPUT 주어진 조건에 따라 Input sequence를 재정렬한 sequence EX ) 2. Insersion Sort Insertion Sort 란? - Insertion 을 이용한 sorting algorithm Insersion 이란? - 새로운 KEY와 이미 정렬된 sorted list가 주어졌을 때, 정렬을 유지한 채 새로운 KEY를 list에 넣는 것. - EX ) Insert "7" into Insertion sort는 Insertion 방법을 증가적으로 이용해서 정렬한다. 예를들어, 라는 정렬되지 않은 list A..

1. rod - cutting problem 이란 rod-cutting 이란 전체 길이 n인 막대와 길이 별 가격이 주어졌을 때, 해당 막대를 잘라서 얻을 수 있는 최대수익을 r_n을 구하는 문제이다. brute-force approach 를 사용하면 2^(n-1)의 possible way를 전부 계산해야 한다. 길이가 n인 막대는 n-1번의 자를 수 있는 틈이 있고, 각각의 틈에는 자른다vs자르지 않는다의 경우가 있기 때문에 2^(n-1)개의 possible way가 있다. 2. 동적 프로그래밍을 이용해서 rod - cutting problem 해결하기 위 그림을 통해 rod - cutting problem을 해결하기 위한 동적 프로그래밍을 이해할 수 있다. p_1 + r_n-1 식은 길이가 1일 때 ..

본 포스팅을 한양대학교 박희진 교수님의 알고리즘 및 문제해결을 정리한 포스팅이다. 교수님이 만든 ppt... 올려도 되는 거겠지...? 교수님 사랑합니다 사랑합니다 사랑합니다. 3번 외쳤으니 됨. 1. Assembly - line scheduling 이란? Assembly line은 말 그대로 조립라인을 말한다. 하나의 조립과정에 n개의 단계(Si)가 있고 각 단계에서 ai 의 조립시간이 걸린다. 수많은 조립라인 중 가장 빠른 조립시간을 결정하는 것이 assembly - line scheduling의 문제이다. 2. Brute - force approach Brute : 무식한 / 짐승같은 & force : 힘 & approach : 접근 말 그대로 무식하게 가능한 경우의 수 하나하나 열거한 후 가장 좋..