지금까지 알고리즘을 풀면서 재귀와 반복문은 많이 사용했을 것이다. 똑같은 상황에서 사용가능 한 이 두가지 방법을 언제 사용하는 것이 좋은지 알아보자. 목차 1. 재귀? 2. 반복문 3. 비교 1. 재귀(Recursion) 우선 재귀를 사용하기 위해서 수학적 귀납법 증명에 대해 간단히 알아보자. n이 0일 때 문제를 풀 수 있고 n-1에서 문제를 풀 수 있으면 n에서도 문제를 풀 수 있다 위의 2가지가 사실이면 모든 가능한 n에 대해 문제를 풀 수 있다는 것이 사실!! 이렇게 프로그램을 돌리면 순차적인 코드에서와 마찬가지로 필요한 계산이 완전히 동일하지만 단순히 표현하는 방법이 달라지는 것 재귀 위의 수학적 귀납법의 풀이 과정을 이용한 것이 재귀이다. 재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 ..

저번에 배웠던 버블, 선택 정렬은 비교와 교환에 기반한 정렬 방식이었고 카운팅 정렬은 비교환 방식이었다. 이번엔 분할 정복 알고리즘에 기반한 퀵 정렬과 합병 정렬에 대해서 알아보자. # 합병 정렬 컴퓨터에 관해 일을 한다면 꼭 알아야 되는 '존 폰 노이만'이 제안한 방법 일반적으로 구현 시 중복된 값을 입력 순서와 동일하게 정렬하는 '안정 정렬' 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법 과정 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 보고 그렇지 않다면 리스트를 절반으로 자른다. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬하고 다시 하나의 정렬된 리스트로 합병 추가적인..

지난 시간의 배열도 그렇고 오늘 배울 정렬은 대체 어떤 것을 위해 배우는 것일까? 그걸 알기 위해 '인덱스'에 대해 조금 알아보고 가자. 인덱스 인덱스라는 용어는 데이터베이스에서 유래했으며, 테이블에 대한 동작 속도를 높여주는 자료 구조이다. Database 분야가 아닌 곳에서는 Look up table 등의 용어를 사용하기도 한다. 인덱스를 저장하는데 필요한 디스크 공간은 보통 테이블을 저장하는데 필요한 디스크 공간보다 작다. 왜냐하면 인덱스는 키-필드만 갖고 있고, 테이블의 다른 세부 항목들은 갖고 있지 않기 때문이다. 배열을 사용한 인덱스 대량의 데이터를 매번 정렬하면, 프로그램의 반응은 느려질 수 밖에 없다. 이러한 대량 데이터의 성능 저하 문제를 해결하기 위해 배열 인덱스를 사용 정렬 2개 이상..

DP 문제를 풀다보니 자주 등장하는 유형이 있어 구글링을 해보니 '최장 증가 부분 수열'이라는 유형이였다. # 최장 증가 부분 수열 (Longest Increasing Subsequence) DP 문제로 자주 나오는 유형 O(N^2)의 시간 복잡도 아니면 O(NlogN)의 시간 복잡도를 가진다. 어려운 문제의 경우 당연히 후자.. 개념 단어 그대로 가장 긴 증가하는 부분 수열을 구하는 것 어떤 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 '오름 차순을 유지하면 증가하는 부분 수열' 즉, 만들 수 있는 부분 수열 중 가장 길면서 오름차순을 유지하는 수열이 LIS 위의 여러 수열 중 가장 길이가 긴 수열은 [2,3,5,6,7] 뿐만 아니라 [1..

그래프를 탐색하는 방법에는 크게 두 가지가 있다. 깊이 우선 탐색(Depth First Search, DFS) 저번에 봤듯이 Stack 또는 재귀의 단계를 활용하여 구현 너비 우선 탐색(Breadth First Search, BFS) 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후, 방문헀던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로 선입선출 형태의 자료구조인 큐를 활용 순서 def BFS(G, v): # 그래프 G, 탐색 시작점 v visited = [0]*(n+1)# n: 정점의 개수 queue = [] # 큐 생성 queue.append(v) # 시작점 v를 큐에 삽입 while que..

분할 정복이란 말 그대로 분할(Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다. 정복(Conquer) : 나눈 작은 문제를 각각 해결한다. 통합(Combine): (필요하다면) 해결된 해답을 모은다. 거듭제곱을 통한 예제를 통하여 분할 정복을 알아보자. 기존의 함수를 구현한다면 O(n)의 시간 복잡도가 걸린다. def Power(Base, Exponent): if Base == 0: return 1 result = 1 # Base^0는 1이므로 for i in range(Exponent): result *= Base return result 분할 정복 기반 알고리즘을 통한다면 O(log 2 n)의 시간 복잡도가 걸리는데 어떻게 이렇게 될 수 있을까? 어떤 정수 C^8 = C x C x C..

# 백트래킹 해를 찾는 도중에 '막히면' (해가 아니면) 되돌아가서 다시 해를 찾아가는 기법 최적화(optimization) 문제와 결정(decision) 문제를 해결할 수 있다. 결정 : 문제의 조건을 만족하는 해가 존재하는지의 여부를 'yes' 또는 'No'가 답하는 문제 미로 찾기, n-Queen 문제, 부분 집합의 합 등.. 정의를 보면 앞서 봤던 DFS-깊이 우선 탐색과 비슷한 것 같다. 미로 찾기 예를 통해서 어떤 차이가 있는지 알아보자. 미로 찾기 아래 그림과 같이 입구와 출구가 주어진 미로에서 입구부터 출구까지의 경로를 찾는 문제 이동할 수 있는 방향은 4가지로 제한된다. 내가 지나가는 경로를 스택에 저장해준 후 pop을 이용해 다시 경로를 되돌아 갈 수 있다. # 백트래킹과 깊이우선탐색의..

LIFO 구조의 Stack을 이용하여 계산기를 구현해보자. 여기서의 계산기는 중위 표기법(infix notation) (A+B)를 후위 표기법(postfix notation)(AB+)으로 변경하여 스택을 이용하여 계산한다. 중위 표기식의 후위 표기식 변환 방법 1 수식의 각 연산자에 대해 우선순위에 따라 괄호를 사용하여 다시 표현 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다. 괄호를 제거한다. 변환 알고리즘 2 (스택 이용) 입력받은 표기식에서 토큰을 읽는다. 토큰이 피연산자이면 토큰 출력 토큰이 괄호를 포함한 연산자일 때, 토큰이 스택의 TOP에 저장되어 있는 연산자보다 우선순위가 높으면 스택에 PUSH 하고, 그렇지 않다면 스택 top의 연산자의 우선순위가 토큰의 우선순위보다 작을 때까지..

1ㄷ1 관계는 선형구조라고 불렀고 1ㄷN의 관계는 트리라고 불렀다. 그럼 N:N의 관계는 어떤 구조일까? 바로 그래프 구조라고 부른다. 비선형 구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요하다. 특히, 그래프와 비슷한 트리와의 큰 차이점은, 순환(Cycle) 할 수 있다는 것 이를 위한 탐색 방법 2가지가 있는데 오늘은 우선 DFS에 대해 알아볼 것이다. 깊이 우선 탐색 (Depth First Search, DFS) 너비 우선 탐색 (Breadth First Search, BFS) 두 방법의 차이 DFS는 탐색을 한 뒤 이전의 정점으로 돌아온다 이것은 백트래킹(Backtracking)이라고 부른다 # DFS - 깊이 우선 탐색 시작 정점의 한 방향으로 갈 수 있는 경로가 ..