Backtracking 백트래킹

• 정답을 찾는 도중 정답의 조건에서 벗어난다면 다른 가능성으로 되돌아가서 정답을 찾아가는 기법
• 가능한 모든 방법을 탐색하는 완전 탐색의 일종이지만 가지치기를 통해 비효율적인 경로를 배제하고 탐색하기에 가지치기의 효율에 따라 효율성 극대화
• 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건이 부합하는지 확인(Promising)하고 만약 해당 트리에서 조건에 맞지 않는 노드는 더 이상 탐색을 진행하지 않고 가지를 쳐버림(Pruning)
  • 주로 재귀 혹은 스택을 통한 DFS로 구현
  • 유망성 검토 (Promising) 후 조건에 부합하지 않으면 가지치기(Pruning)를 통해 다른 자손 노드를 탐색함으로서 풀이시간 단축

State Space Tree 상태 공간 트리

• 실제 구현 시 고려할 수 있는 모든 경우의 수를 상태 공간 트리(State Space Tree)를 통해 표현

N-Queen 문제

• N x N 크기의 체스판에 가로,세로,대각선으로 어느 위치든 이동할 수 있는 퀸을 서로 공격할 수 없는 위치로 최대한 많이 배치하는 대표적인 백트래킹 문제

N-Queen 문제 해결 로직

• 퀸은 수평 이동이 가능하므로 한 행에는 하나의 퀸 밖에 위치할 수 없음
• 맨 위에 있는 행부터 퀸을 배치하고, 다음 행에 해당 퀸이 이동할 수 없는 위치를 찾아 퀸을 배치
• 만약 앞선 행에 배치한 퀸으로 인해, 다음 행에 해당 퀸들이 이동할 수 없는 위치가 없을 경우에는, 더 이상 퀸을 배치하지 않고, 이전 행의 퀸의 배치를 바꿈
  • 맨 위의 행부터 전체 행까지 퀸의 배치가 가능한 경우의 수를 상태 공간 트리 형태로 만든 후, 각 경우를 맨 위의 행부터 DFS 방식으로 접근
  • 해당 경우가 진행이 어려울 경우, 더 이상 진행하지 않고, 다른 경우를 체크

N-Queen 문제 알고리즘 구현

```python def is_available(candidate, current_col): current_row = len(candidate) for queen_row in range(current_row):
if candidate[queen_row] == current_col or abs(candidate[queen_row] - current_col) == current_row - queen_row: return False return True

Continue reading

Shortest Path Problem 최단 경로 문제

• 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제
• 가중치 그래프 (Weighted Graph) 에서 간선 (Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적

최단 경로 문제 종류

• 단일 출발 및 단일 도착 (single-source and single-destination shortest path problem) 최단 경로 문제
  • 그래프 내의 특정 노드 u 에서 출발, 또다른 특정 노드 v 에 도착하는 가장 짧은 경로를 찾는 문제
• 단일 출발 (single-source shortest path problem) 최단 경로 문제
  • 그래프 내의 특정 노드 u 와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제
• 전체 쌍(all-pair) 최단 경로 문제
  • 그래프 내의 모든 노드 쌍 (u, v) 에 대한 최단 경로를 찾는 문제

Dijkstra Algorithm 다익스트라 알고리즘

• 하나의 노드에서 다른 모든 노드 간의 각각 가장 짧은 거리를 구하는 단일 출발 최단 경로 문제에 적합
• 첫 노드을 기준으로 연결되어 있는 노드들을 추가해 가며, 최단 거리를 갱신하는 기법으로 BFS와 유사

다익스트라 알고리즘 로직

• 다익스트라 알고리즘의 다양한 변형 로직이 있지만, 본 포스팅에서는 가장 개선된 우선순위 큐를 사용하는 방식을 사용
  • 우선순위 큐는 최소 힙 방식을 활용해서, 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼냄

1. 첫 노드를 기준으로 배열을 선언하여 첫 노드에서 각 노드까지의 거리를 저장
   • 시간을 단축시키기 위해 접근이 빠른 해시테이블의 성질을 띄는 딕셔너리로 선언
   • 초기에는 첫 노드의 거리는 0, 나머지는 무한대(inf)로 저장
   • 우선순위 큐에 (첫 노드, 거리 0)만 먼저 넣음
2. 우선순위 큐에서 노드를 꺼냄
   • 처음에는 첫 노드만 저장되어 있으므로, 첫 노드가 꺼내짐
   • 첫 노드에 인접한 노드들 각각에 대해, 첫 노드에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 노드에서 각 노드까지의 거리를 비교
   • 배열에 저장되어 있는 거리보다, 첫 노드에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리로 업데이트
   • 배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 삽입
   • 결과적으로 너비 우선 탐색 방식과 유사하게, 첫 노드에 인접한 노드들을 순차적으로 방문
   • 만약 배열에 기록된 현재까지 발견된 가장 짧은 거리보다, 더 긴 거리(루트)를 가진 (노드, 거리)의 경우에는 해당 노드와 인접한 노드간의 거리 계산을 하지 않음
3. 2번의 과정을 우선순위 큐에 꺼낼 노드가 없을 때까지 반복

다익스트라 알고리즘 구현

Continue reading

BFS (Breadth First Search) 너비 우선 탐색

• 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 방식
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택함
• 주로 queue를 활용하여 구현함

Continue reading

Search Algorithm 탐색 알고리즘

• 탐색은 여러 데이터 중 원하는 데이터를 찾아내는 것을 의미함
• 검색 엔진에 탐색 알고리즘이 많이 사용되기도 함 (그래서 검색 알고리즘이라고도 함)

Sequential Search Algorithm 순차 탐색 알고리즘

• 리스트의 가장 처음부터 시작하여 찾으려는 데이터가 나올 때까지 하나씩 리스트의 각 요소와 비교하는 탐색 알고리즘
• Linear Search Algorithm (선형 탐색 알고리즘)이라고 하기도 함
• O(n)의 시간 복잡도를 가짐

def sequencial_Search(data_list, search_data):
    for index in range(len(data_list)):
        if data_list[index] == search_data:
            return True
    return False

Binary Search Algorithm 이진 탐색 알고리즘

• 찾으려는 데이터가 나올 때까지 탐색할 리스트를 둘로 나누어가며 탐색 하는 알고리즘
• 이진 탐색은 반드시 리스트가 정렬되어 있는 상태에서 탐색을 진행
• O(nlogn)의 시간 복잡도를 가짐

Continue reading

날짜: 2021년 7월 24일
소요 시간: 19분 21초
카테고리: 그리디 알고리즘
태그: 레벨1, 파이썬

Continue reading

Greedy Algorithm 탐욕 알고리즘

• 매 순간 최적이라고 생각되는 해를 구해나가는 알고리즘
• 순간순간 최적이라고 생각되는 해를 구해나가기 때문에 보다 빠르게 최적에 가까운 값을 구하기 위해 사용되지만, 그 해가 무조건 최적이 아닐 수도 있기 때문에 상황에 맞게 잘 활용 해야 함
  • (특정한 상황일 경우 그리디 알고리즘도 최적의 해를 보장해 줄 수도 있음)
• 대표적으로 그리디 알고리즘을 응용한 알고리즘으로는 다익스트라 알고리즘, 허프만 코드, 크러스컬 알고리즘 등이 있음

대표적인 그리디 알고리즘을 활용한 문제

가장 적은 동전의 수

• 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현

```python coin_list = [500, 100, 50, 1]

Continue reading

날짜: 2021년 7월 21일
소요 시간: 42분 53초
카테고리: 그리디 알고리즘, 정렬
태그: gold.5, 1092, 파이썬

Continue reading

날짜: 2021년 7월 19일
소요 시간: 23분 33초
카테고리: 완전 탐색
태그: 레벨1, 파이썬

Continue reading

Dynamic Programing 동적 계획법

• 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법
• Dynamic이라는 이름과는 다르게 전혀 동적이진 않은데 이는 처음 이 방식을 사용한 벨만이 다른 이유 없이 Dynamic 이라는 단어가 그저 멋있어서 선택했다고 함
• 분할 정복과는 다르게 동적 계획법은 두가지 전제 조건이 있어야 동적 계획법으로 문제를 해결 가능
  1. Overlapping Subproblem : 겹치는 작은 문제
     • 어떤 문제가 여러개의 항상 새로운 부분 문제를 생성해내기 보다는 계속해서 같은 부분 문제가 여러번 재사용되거나 재귀를 통해 해결되는 부분 문제로 쪼개질 수 있을 때
  2. Optimal Substructure : 최적 부분구조
     • 어떤 문제의 최적의 해결책이 그 부분 문제의 최적의 해결책으로 부터 설계될 수 있을 때, 즉, 최적 부분구조 일때 문제의 정답을 작은 문제의 정답에서 부터 구할 수 있음
     • 이 속성은 동적 계획법이나 그리디 알고리즘의 유용성을 판별하는데 사용되기도 함

Memoization 메모이제이션

• 동일한 문제를 반복해야 할 경우, 한 번 계산된 결과를 저장해 두었다가 활용하는 방식으로 중복 계산을 줄이는 것
• 동적 계획법을 분할 정복과 나누는 가장 큰 차이점 중 하나
  
  

Continue reading

Divide and conquer 분할 정복

• 분할정복법은 주어진 문제를 작은 사례로 나누고 각각의 작은 문제들을 해결하여 정복 (Conquer)하는 방법
• 분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산, 각 부분 문제의 답으로부터 전체 문제의 답을 계산
• 주로 재귀함수를 이용하여 구현하는 것이 일반적이나, 재귀호출을 사용하지 않고 스택, 큐 등의 자료구조를 이용하여 구현하기도 함
• 대표적인 분할 정복법을 활용한 알고리즘으로는 퀵 정렬과 병합 정렬이 있음

분할 정복 프로세스

1. Divide (분할) : 문제를 동일한 유형의 여러 하위 문제로 분할
2. Conquer (정복) : 가장 작은 단위의 하위 문제들을 해결하며 정복
3. Combine (조합) : 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합

문제를 제대로 분할하면 정복하는 것은 쉽기 때문에 제대로 분할하는 것이 중요
분할 정복법은 재귀 호출이 자주 사용되는데, 이 부분에서 분할 정복법의 효율성이 떨어질 수도 있음

분할 정복의 장단점

장점

• 문제를 나누어 해결함으로써 어려운 문제를 보다 쉽게 해결할 수 있음
• 문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결하는 데 큰 강점이 있음

단점

• 함수를 재귀적으로 호출하게 되면 함수 호출로 인한 오버헤드가 발생하며, 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 하게 됨

분할 정복 vs 재귀 호출

• 일반적인 재귀 호출과의 차이점은 항상 문제를 한 조각과 나머지로 쪼개는 방식인 재귀 호출과는 달리 분할정복법은 항상 문제를 절반씩으로 나누어 문제를 해결
  
  

Continue reading