Park Jinseok - Game Developer

동적 계획법(Dynamic Programming) 분할 정복 기법과 많은 부분이 비슷함. 같은 부분 문제를 다시 풀지 않도록 하는 것이 핵심 ex)한번 푼 문제의 답을 저장하고 다음에 다시 풀어야 할 때는 그 문제에 대한 해답만 이용하는 방법 메모이제이션(Memoization) 문제를 풀 떄마다 이미 풀린 문제인지를 먼저 확인하는데, 풀린 문제이면 저장된 답을 이용하고 풀리지 않은 문제이면 그 문제를 풀고 답을 저장한다. 하향식(Top-bottom)식으로 문제를 해결 테이블화(Tabulation) 결과를 저장할 테이블을 먼저 만든다. 다음으로 답이 이미 알려진 상황인 기반 상황(Base Case)에 대한 테이블 항목을 먼저 채우고, 이를 바탕으로 테이블을 채워 올라간다. 동적 계획법을 이용한 문제 해결 ..

공간 복잡도를 이용한 시간 복잡도 줄이기 많은 메모리를 희생하면 답을 더 빨리 구할 수 있음. 하지만, 대부분의 문제에서는 가능한 모든 입력이 거의 무한하게 많아 미리 답을 계산 할 수 없고, 답을 저장할 공간도 부족함. 현실적으로 가능한 수준에서 공간을 희생해서 시간 복잡도를 줄이는 방법을 선택해야 함. 기수 정렬 기수 정렬의 아이디어 이전까지의 정렬 방법들은 비교 기반의 정렬 방법들이었다면, 분배 방식의 정렬들은 메모리 공간에 나누어 저장하는 방식이다. 분배 방식의 정렬에는 기수 정렬과 카운팅 정렬이 있다. 기수 정렬은 숫자의 자릿수를 의미하는데 자릿수의 값에 따라서 정렬하기 떄문에 기수 정렬이라는 이름을 얻음. 기수 정렬은 다단계 정렬인데, 단계의 수는 데이터의 전체 자릿수와 일치함. 기수 정렬 방..

분할 정복(Divide and Conquer) 하나의 문제를 여러 개의 작은 부분 문제로 나누고, 이 부분 문제들을 각각 해결한 다음 결과를 모아서 원래의 문제를 해결하는 전략 분할 된 부분 문제가 충분히 작지 않으면, 분할 정복을 연속으로 적용하면 되는데 보통 순환 호출을 사용한다 축소 정복은 분할 한 후에 부분문제가 하나만 남는 특별한 경우의 분할 정복이다. ex) 이진 탐색은 분할된 두 부분에서 한쪽은 필요가 없기 때문에 문제의 크기가 절반으로 축소되는 것 분할 정복 기법의 문제 해결 순서 분할(Divide) 주어진 문제를 같은 유형의 부분문제들로 분할 정복(Conquer) 부분문제들을 해결하여 부분 해를 만듦 병합(Combine) 부분적인 결과들을 묶어 최종 해를 만듦 병합 정렬(Merge Sor..

축소 정복(Decrease-and-Conquer) 기법 주어진 문제를 해결하기 위해 이 문제와 좀 더 작은 문제간의 관계를 이용하는 전략 문제 사이의 관계가 구해지면 하향식(Top-Down)이나 상향식(Bottom-Up)으로 적용할 수 있다. 하향식은 보통 순환구조를 이용하고 상향식은 반복구조로 표현하며 점증적(Incremental) 기법이라고도 한다. 축소 정복 기법은 분할 정복 기법의 한가지 유형으로도 볼 수 있음 문제의 크기가 줄어드는 방식에 따른 3가지 유형 고정 크기 축소(Decrease by a constant) 순환이나 반복에 따라 문제의 크기가 일정 수만큼 줄어드는 경우 ex) 팩토리얼 고정 비율 축소(Decrease by a constant factor) 문제의 크기가 일정한 비율로 줄어..

선택 정렬 억지 기법에서의 전략 정렬이 안된 리스트에서 최솟값이 선택되면 이 값을 새로운 리스트에 저장하는 것이 아니라 첫 번째 요소와 교환한다. 어떤 정렬 알고리즘이 입력 리스트 이외에 추가적인 메모리를 사용하지 않으면 "제자리(In-place) 정렬"이라고 부른다. 선택 정렬의 장점 알고리즘이 간단하고, 입력자료의 구성과 상관없이 자료 이동 횟수가 결정된다는 장점 입력의 크기가 크지 않은 실제 문제에 충분히 사용 가능 선택 정렬의 단점 다른 정렬 알고리즘에 비해 효율적이지도 않고, 안정성을 만족하지도 않음 Python Code 더보기 data = [5,3,8,4,9,1,6,2,7] def printStep(arr, val): print(" Step %2d = " % val, end='') print(..

점근적 표기(Asymptotic notation) 알고리즘의 복잡도 함수 T(n)는 입력의 크기 n에 대한 수식으로 보통 여러개의 항을 가진 다항식 형태가 된다. ex)n^2 + 3n - 5 만약 n이 무한대에 가까워진다면 복잡도 함수는 최고차항만으로도 실행시간의 대부분이 반영될 수 있다 점근적 표기는 입력의 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 방법으로 복잡도 함수를 최고차항만을 꼐수없이 취해 단순화 시킴. ex)3n^2-100n+10000는 n^2으로, 2n!+ 100^n은 n!로 나타냄 효율성 분석에서 중요한 것은 n에 대해 "연산이 정확히 몇번 필요한가?"가 아니라 n이 증가함에 따라 "무엇에 비례하는 수의 연산이 필요한가?"이다 점근적 표기는 함수에 상한(Uppe..