본문 바로가기

알고리즘10

백 트래킹 기법 1. 백 트래킹 기법 백트래킹 (backtracking) 또는 퇴각 검색 (backtrack)으로 부름 제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack (다시는 이 후보군을 체크하지 않을 것을 표기)하고, 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법이다. 실제 구현시, 고려할 수 있는 모든 경우의 수 (후보군)를 상태공간트리(State Space Tree)를 통해 표현 각 후보군을 DFS 방식으로 확인 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 곳으로 바로 넘어가서.. 2022. 8. 11.
[알고리즘] algosopt - 여행 짐 싸기 (동적계획법) 여행 짐 싸기 문제 정보 시간 제한 메모리 제한 2000ms 65536kb 문제 여행을 떠나기 전날까지 절대 짐을 싸지 않는 버릇이 있는 재훈이는 오늘도 비행기 타기 전날에야 가방을 싸기 위해 자리에 앉았습니다. 비행기 규정상 재훈이는 캐리어를 하나만 가지고 갈 수 있는데, 아무래도 가져가고 싶은 물건들이 캐리어 안에 다 들어가지 않을 것 같습니다. 재훈이는 가져가고 싶은 각 물건들의 부피와 얼마나 필요한지를 나타내는 절박도를 조사해 다음과 같은 목록을 만들었습니다. 물건 노트북 컴퓨터 카메라 XBOX365 커피그라인더 아령 백과사전 부피 4 2 6 4 2 10 절박도 7 10 6 7 5 4 캐리어의 용량이 정해져 있기 때문에 가져갈 수 있는 물건들의 부피 합은 캐리어의 용량 w 이하여야 합니다. 이때 .. 2022. 4. 1.
[알고리즘] 플로이드 와샬 알고리즘 정의 모든 정점에서 모든 정점으로의 최단 경로를 구하는 최단 경로 알고리즘이다. 거쳐가는 기준을 최단거리를 구한다는 특징이 있다. 코드 import math INF = math.inf def floyid(graph): for k in range(len(graph)): for i in range(len(graph)): for j in range(len(graph)): if graph[i][k] + graph[k][j] < graph[i][j]: graph[i][j] = graph[i][k] + graph[k][j] print(graph) _graph = [ [0, 5, INF, 8], [7, 0, 9, INF], [2, INF, 0, 4], [INF, INF, 3, 0] ] floyd(_graph) 2021. 10. 24.
[알고리즘] 다익스트라 알고리즘 정의 특정한 정점으로부터 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘이다. 음의 간선은 포함시킬 수 없다. 활용 현실 생활에서 많이 사용되는 알고리즘으로 인공위성 GPS 등이 있다. 코드 시간 복잡도 O(N * log N)를 가지는 코드이다. import heapq import math def dijkstra(graph, start): distances = {node : math.inf for node in graph} distances[start] = 0 queue = [] heapq.heappush(queue, [distances[start], start]) while queue: curr_distance, curr_dest = heapq.heappop(queue) if distances[c.. 2021. 10. 24.
[알고리즘] 크루스칼 알고리즘 정의 Spanning Tree, 최소 비용 신장 트리를 O(ElogV)O(ElogV)만에 구하는 알고리즘이다. 신장 트리의 조건 본래의 그래프의 모든 노드를 포함해야함 모든 노드가 서로 연결 트리의 속성 만족 (사이클 존재하지 않음) 코드 parent = {} rank = {} def find(node): if parent[node] != node: parent[node] = find(parent[node]) return parent[node] def union(node_v, node_u): root1 = find(node_v) root2 = find(node_u) if rank[root1] > rank[root2]: parent[root2] = root1 else: parent[root1] = root.. 2020. 11. 18.
[알고리즘] 그리디 (탐욕법) 알고리즘 정의 그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지는 알고리즘 설계 기법이다. 단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 사용되는 예시 AI에 있어서 결정 트리 학습법(Decision Tree Learning) 활동 선택 문제(Activity selection problem) 거스름돈 문제 최소 신장 트리 (Minimum spanning tree) 제약조건이 많은 대부분의 문제 다익스트라 알고리즘 허프만 코드 크러스컬 알고리즘 2020. 11. 15.
[알고리즘] 다이나믹 프로그래밍 정의 중복되는 연산을 줄이기 위하여 메모리 공간을 최대한 활용하여 연산 속도를 증가시키는 방법이다. 다이나믹 프로그래밍(dynamic programming)이라 표기하고 한국어 표기로는 "동적 계획법" 이라고 한다. 방식 탑다운 방식 (메모이제이션 활용) 보텀업 방식 구현 예시로 피보나치 수열이 있다 탑다운 방식 def fibo(x): if x == 1 or x == 2: return 1 if d[x] != 0: return d[x] d[x] = fibo(x - 1) + fibo(x - 2) return d[x] d = [0] * 100 answer = fibo(99) print('answer: {}'.format(answer)) # answer: 218922995834555169026 보텀업 방식 de.. 2020. 11. 8.
[알고리즘] BFS 알고리즘 정의 루트 노드에서 시작해서 가장 가까운 노드부터 찾는 알고리즘 BFS (Breadth First Search) 약자로 한국어 표기로는 "넓이 우선 탐색" 또는 "너비 우선 탐색" 이라고 한다. 코드 구현 from collection import deque def bfs(index, graph, visited): queue = deque([index]) while queue: v = queue.popleft() visited[v] = True for i in range(len(graph)): if visited[i] == False: queue.append(i) return visited DFS vs BFS 그림으로 보면 차이점이 명확해질 것이다. 2020. 11. 6.
[알고리즘] DFS 알고리즘 정의 루트 노드에서 시작해서 다음 분기를 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 DFS (Depth First Search) 약자로 한국어 표기로는 "깊이 우선 탐색" 이라고 한다. 장단점 장점 단지 현 경로상의 노드들만을 기억하면 되므로 저장 공간의 수요가 비교적 적다. 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 해가 없는 경로에 깊이 빠질 가능성이 있다. 얻어진 해가 최단 경로가 된다는 보장이 없다 코드 구현 def dfs(index, graph, visited): stack = [index] while stack: v = stack.pop() visited[v] = True for i in range(len(graph)): if visited[i] == False.. 2020. 10. 17.
[알고리즘] 이진탐색 정의 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘 코드 구현 def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 if array[mid] == target: return mid if array[mid] > target: end = mid - 1 else: start = mid + 1 return binary_search(array, target, start, end) target = 3 array = [5, 4, 2, 1, 3] result = binary_search(array, target, 0, len(array)) if result == None: pri.. 2020. 10. 12.
728x90
반응형

티스토리툴바