본문 바로가기

Python

 (28)
12. 그래프 기초 (Graph Basics): 파이썬 자료구조와 알고리즘 그래프란 여러 노드 (node, 또는 정점, vertex) 들이 간선 (edge, 또는 아크, arc) 으로 연결된 추상 네트워크를 뜻한다. 가장 기본적인 용어들부터 알아보도록 하자. 용어 그래프 그래프는 아까 말했듯 여러 노드와 간선으로 연결된 추상 네트워크를 뜻한다. 즉, 그래프는 노드와 간선의 집합으로 정의되며 이를 수식으로 쓰면 다음과 같다. G는 그래프 (graph), V는 노드 (vertex) 의 집합, 즉 아래와 같은 그래프에선 {a,b,c,d} 이고, E는 간선 (edge) 의 집합, 즉 노드 쌍들의 집합이며, 아래와 같은 그래프에선 {{a,b}, {b,c}, {c,d}, {d,a}}이다. 그래프의 방향 그래프에는 방향이 있는 유향 (directed) 그래프와 방향이 없는 무향 (undir..
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)인 알고리즘을 사용한다면 그보다 훨씬 작은 시간 내에 연산을 완료할 수 있을 것이다. 이와 같이 알고리즘의 시간 복잡도는 알고리즘에 있어..

티스토리툴바