모든 경우의 수를 전부 고려하는 알고리즘이며, 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. DFS를 사용하여 만약 조건에 맞지 않으면 그 즉시 중단하고 이전으로 돌아가여 다시 확인하는 것을 반복하면서 원하는 조건을 찾는 알고리즘 한정 조건 백트래킹은 모든 경우의 수에서 한정 조건에 유망한 promissing 경우를 탐색하는 것이기 때문에 완전탐색기법인 BFS 나 DFS 모두 구현이 가능하다. 하지만 백트래킹의 특성에서 한정 조건에 부합하지 않다면 이전 수행으로 돌아와야하기 때문에 BFS보다 DFS가 구현에 편하다. 백트래킹을 구현할 때 가장 중요한 것은 한정 조건이다. 한정 조건을 걸어 완전 탐색에서 유망하지 않은 시도를 걸러내는 것이 백트래킹의 본질이다. n, m = map(int, inpu..
대표적인 그래프 탐색 알고리즘 DFS Depth-First Search 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이며, 스택 자료구조나 재귀 함수를 이용한다. 탐색 시작 노드로 재귀함수를 호출해 방문 처리한다. 현재 방문 노드에서 방문하지 않은 인접 노드가 하나라도 있으면 그 노드로 재귀함수를 호출해 방문 처리한다. 방문하지 않은 인접 노드가 없으면 해당 재귀 함수는 종료된다. 더 이상 2 - 3번의 과정을 수행할 수 없을 때까지 반복한다. # 재귀함수로 구현한 DFS def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in g..
Dynamic Programming, 다이나믹 프로그래밍 : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방식의 알고리즘 메모리를 적절하게 사용하여 수행시간 효율성을 비약적으로 향상시킨다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 구현은 일반적으로 탑다운과 바텀업 방식으로 나뉜다. DP의 조건 1. 최적 부분 구조 Optimal Substructure : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제 Overlapping Subproblem : 동일한 작은 문제를 반복적으로 해결해야 한다. 메모이제이션 한 번 계산한 결과를 메모리 공간에 기록해두고 다시 계산하지 않는 방법 같은..
Recursive Function, 재귀함수 : 하나의 함수에서 자기 자신을 다시 호출하는 함수 귀납적 사고 어떤 문제를 재귀로 푼다는 것은 귀납적인 방식으로 문제를 해결하겠다는 것이다. 1번 도미노가 쓰러진다. k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다. 위 조건 두 가지만 생각한 후 바로 "모든 도미노가 쓰러진다"라는 사고로 이어져야 한다. 귀납법 개별적인 특수한 사실이나 현상에서 그러한 사례들이 포함되는 일반적인 결론을 이끌어내는 또는 역으로 보편성에서 구체성을 유도하는 추론 형식 · 추리 방법 절차지향적 사고 vs 귀납적 사고 def recursive(n): if n == 0: # base condition return print(n) recursive(n-1) 절차지향적 사고 recurs..
hashing 된 맵, 해싱 함수를 사용하여 key와 value 쌍으로 데이터를 보관하는 맵 자료구조 특성 순차적으로 데이터를 저장하지 않는다. key를 통해 value 를 얻는다. value값은 중복가능하지만 key는 중복될 수 없다. 수정 가능(mutable)하다. 시간복잡도 삽입 : O(1) 탐색 : O(1) Dictionary ### 선언 및 초기화 d = {} d = {'alice': 1, 'bob': 20, 'tony': 15, 'suzy': 30} d = dict() d = dict(alice = 5, bob = 20, tony = 15, suzy = 30) # 컴프리헨션 초기화 num_d = {key: 0 for key in range(10)} # {0: 0, 1: 0, 2: 0, 3: 0..
먼저 들어간 데이터가 먼저 나오는 FIFO (First In First Out)의 성질을 가진 자료구조 특성 삭제 연산이 수행되는 곳을 front, 삽입연산이 수행되는 곳을 rear 라 한다. 요소는 rear로 들어와서 front로 빠진다. 접근은 가장 첫 원소와 끝 원소만 가능하다. rear에서 수행되는 삽입연산을 enQueue, front에서 수행되는 삭제연산을 deQueue라 한다. 시간복잡도 삽입/삭제 : O(1) 탐색 : O(n) Queue 사용 with Python # 데이터 흐름: 왼쪽방향 queue = [1, 2, 3] # enQueue queue.append(4) # queue = [1, 2, 3, 4] # deQueue queue.pop(0) # 1 반환, queue = [2, 3, 4..