본문 바로가기

Python/알고리즘 (Algorithm)

 (10)
11. 동적 계획법 (Dynamic Programming): 파이썬 자료구조와 알고리즘 동적 계획법 (dynamic programming) 은 복잡하 문제를 재귀를 통해 간단한 하위 문제로 분류하여 단순화하여 해결하는 방법이다. 어떤 문제가 최적 부분 구조 (optimal substructure) 와 중복되는 부분 문제 (overlapping subproblem) 를 갖고 있다면 동적 계획법으로 해결할 수 있다. 최적 부분 구조는 답을 구하기 위해서 했던 계산을 반복해야 하는 문제의 구조를 말한다. 동적 계획법을 사용하려면 먼저 최적 부분 구조가 있는지 확인해야 한다. 동적 계획법은 부분 문제를 풀고 결과를 저장한 후 다음 부분 문제를 푸는 과정에서 저장된 결과를 사용한다. 메모이제이션 메모이제이션 (memoization) 은 프로그램이 동일한 계산을 반복할 때 이전에 계산한 값을 메모리에..
탐욕법 (Greedy Algorithm) 탐욕법 (Greedy Algorithm) 은 최적해를 구하는 상황에서 사용하는 방법이다. 여러 경우 중 하나를 선택하고 싶은 경우, 각 상황마다 그 상황에서 가장 좋다고 생각하는 것을 선택해 나가는 방식으로 진행하여 답을 구하는 알고리즘이다. 그러나 그 상황에서 가장 좋다고 생각하는 것이 무조건적으로 가장 좋은 결과를 얻는 것은 당연히 아니다. 예를 들어 위와 같은 상황에서 0에서 시작했을 때 탐욕법을 사용하면 첫 번째 선택에서 가장 큰 결과값인 10의 경로를 택할 것이고, 그 다음 선택에서 가장 큰 결과값인 40의 경로를 택하여 총 50의 보상을 받게되지만, 실제 가장 큰 보상을 받을 수 있는 경로는 5를 선택한 후 100을 선택하는 경로이다 (최적의 해). 그러나 탐욕법은 최적의 해와 근접한 답을 주..
10-2. 검색 연습문제 (Searching Examples): 파이썬 자료구조와 알고리즘 행렬 검색 각 행과 열이 정렬되어 있는 행렬에서 한 항목을 검색한다고 해보자. 즉 모든 행은 왼쪽에서 오른쪽으로, 모든 열은 위에서 아래로 첫 번째 항목을 기준으로 정렬 (오름차순) 되어 있다. 예제 리스트는 아래와 같다. m1 = [ [1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15] ] 책의 정답: matrix = [ [1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15] ] def search_matrix(m1, value): found = False row = 0 col = len(m1[0]) - 1 while row = 0: if m1[row][col] =..
10-1. 검색 (Searching): 파이썬 자료구조와 알고리즘 검색 알고리즘은 배열이 정렬되어 있는 경우 순차 검색 (sequential search) 를 흔히 사용하며 정렬되어 있지 않은 경우 이진 검색 (binary search) 을 많이 사용한다. 해시 테이블은 보조 메모리 공간을 사용하지만, 키를 이용하면 O(1)에 원하는 값을 검색할 수 있다. 정렬되지 않은 배열 검색 순차 검색 순차 검색 (sequential search) 은 아주 당연히도 순차적으로 배열을 돌면서 해당하는 항목을 검색하는 것이다. 최선의 경우 시간 복잡도는 O(1) 이며, 평균은 O(n/2), 최악의 경우는 O(n)이다 (굉장히 당연히도). 만약 리스트에 검색하려는 항목이 없다면 최악/최선/평균 모두 O(n)이다. def sequential_search(seq, n): for item ..
9-2. 로그 선형 정렬, 고급정렬 (Log-linear Sorting, Advanced Sorting) 지금까지 다뤄왔던 정렬 알고리즘들은 모두 최악의 경우의 시간 복잡도가 O(n^2)였다. 저번에 시간 복잡도에서 다뤘듯, 시간 복잡도가 기본적으로 O(n^2) 이상이 되면 비효율적이라고 한다. 연산시간이 오래 걸리기 때문이기도 하고, 데이터 수에 따라 수 초나 수 시간이 아닌 이론적으로 수 년이 걸릴 수도 있는 작업이 될 수 있기 때문이다. 그러나 정렬은 필수적인 작업이다. 따라서 이를 해결하기 위해 더 고급의 정렬 방식들이 등장하게 되었는데, 이 고급 정렬 방식들은 모두 O(n log n)의 시간 복잡도를 갖고 있다. sort( )와 sorted( ) 파이썬에수 흔히 사용되는 sort() 메서드는 원본 리스트를 정렬된 상태로 변환하며, sorted() 메서드는 원본의 변경 없이 정렬된 새로운 리스트를 반..
9-1. 2차 정렬과 선형 정렬 (Quadratic and Linear Sorting) : 파이썬 자료구조와 알고리즘 어떤 항목들을 크기가 작은 순서대로 정렬 (sorting) 하고 싶다고 하면, 가장 간단한 방법은 가장 작은 항목을 그룹에서 맨 앞으로 이동시키는 것을 반복하는 것이다. 그러나 이 알고리즘은 시간 복잡도가 O(n^2) 이므로, 더 나은 알고리즘을 찾아야 한다. 제자리 정렬 (in-place sort) 은 정렬할 항목의 수에 비해 아주 작은 저장 공간을 더 사용하는 정렬 알고리즘을 뜻한다. 삽입 정렬은 주어진 원소들을 옮긴 뒤 적절한 위치에 원소를 삽입하는 연산을 반복하는데, 이로 인해 항목을 담는 공간 외에 추가로 사용될 수 있는 공간은 옮겨지는 항목이 저장되는 공간과 반복문 변수 정도에 불과하다. 안정적 정렬 (stable sort) 은 데이터 요소의 상대적인 순서를 보존한다. 데이터의 두 항목이 크기..
8. 점근적 분석 (Asymptotic Analysis): 파이썬 자료구조와 알고리즘 점근적 분석 (asymptotic analysis) 은 어떤 알고리즘에 큰 입력 데이터셋을 적용할 때 알고리즘의 제한 동작과 성능을 설명하기 위한 방법이다. 일반 컴퓨터에서 10억개의 숫자 (10^9) 를 정렬한다고 가정해보자. 숫자는 1 바이트라고 가정하고. 컴퓨터의 CPU 클록은 1GHz (초당 약 10^9 번의 연산) 라고 가정하면, 만약 실행 시간이 O(n^2) 인 알고리즘을 사용하여 숫자를 정렬한다면, 최악의 경우 약 10억초 (약 32년) 가 걸릴 것이다. 끔찍하다. 그러나 O(n)인 알고리즘을 사용하면 대략 수 초가 걸릴것이며, O(log n) 또는 O(1)인 알고리즘을 사용한다면 그보다 훨씬 작은 시간 내에 연산을 완료할 수 있을 것이다. 이와 같이 알고리즘의 시간 복잡도는 알고리즘에 있어..
7-2-2. 큐, 우선순위 큐, 힙, 연결 리스트 예제 (Other Types Examples): 파이썬 자료구조와 알고리즘 큐 데크와 회문 데크를 사용하면 문장이 회문인지 쉽게 확인할 수 있다. 내 정답: from deque import Deque def check_palindrome(string): d = Deque() for i in string: d.enqueue_back(i) h_leng = d.size() // 2 for i in range(h_leng): if d.dequeue() == d.dequeue_front(): continue else: return False return True palindrome = '다시합창합시다' not_palindrome = '안녕하세요' print(check_palindrome(palindrome)) print(check_palindrome(not_palindrome)) 책의 ..

티스토리툴바