본문 바로가기
728x90
반응형

Algorithm

 (12)
탐욕 알고리즘 (Greedy Algorithm) 그리디(탐욕) 알고리즘 : 그리디 알고리즘은 동적 프로그래밍(Dynamic Programming) 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다. 여러 경우 중 하나를 결정해야할 때마다 각 단계에서 가장 최선의 선택을 하는 기법으로 이 선택이 전체적으로도 최선이기를 바란다고 볼 수 있다. ! 항상 최적의 답을 구해주지는 않음 ! -> 그리디 알고리즘은 주로 정렬 알고리즘과 짝을 이뤄 출제되는데 "가장 큰 or 작은 순서대로"라는 기준을 제시해줌. * 최단 경로를 빠르게 찾아야 하는 문제 = 플로이드 워셜 or 다익스트라 알고리즘 대표적인 그리디 문제 : 거스름돈 문제 -> 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다. 이 때, 손님에게 거슬러 줘야 할 돈이 N..
깊이 우선 탐색(Depth-First Search) : DFS 깊이 우선 탐색(Depth-First Search) - 그래프 탐색 방법 중 한 가지 종류 "그래프 탐색은 BFS로 하는 것이 훨씬 쉽지만, 재귀함수 사용(백 트래킹에서 쓰임)을 익히기 위해서 DFS가 용이" Stack 사용 아이디어 - 시작점에 연결된 Vertex 찾기 - 찾은 Vertex를 계속해서 찾음(끝날 때까지) - 더이상 연결된 Vertex가 없을 경우 다음으로 넘어감 [그래프 예시] 파이썬으로 구현한 DFS 알고리즘 # 재귀함수로 구현한 DFS def dfs(graph, start, visited): visited[start] = True print(start, end=' ') for i in graph[start]: if visited[i] == False: dfs(graph, i, vis..
투포인터(Two Pointer) 알고리즘 투포인터(Two Pointer)알고리즘 : 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 것을 의미하는 알고리즘 특징 1) 각 원소마다 모든 값을 순회해야할 때 사용 특징 2) 연속하다는 특성을 이용해서 철 특징 3) 두 개의 포인터(커서)가 움직이면서 계산 특징 4) 처음부터 생각하기 어려움 -> 쉬운 방법부터 생각하기 투포인터 알고리즘의 과정 1. 시작점(start)과 끝점(end)이 첫 번재 원소의 인덱스(0)를 가리키도록 한다. 2. 현재 부분 합이 M과 같다면 카운트한다. 3. 현재 부분 합이 M보다 작다면 end를 1 증가시킨다. 4. 현재 부분 합이 M보다 크거나 같다면 start를 1 증가시킨다. 5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복..
백 트래킹(Back Tracking) 알고리즘 백트래킹(Back Tracking)이란? - 모든 경우의 수를 확인해야 할 때 => (ex) 순열 : for문으로는 확인 불가한 경우에 사용(깊이가 달라질 때) "깊이 우선 탐색(DFS)과 마찬가지로 스택(Stack)을 사용" => DFS는 현재 지점에서 방문할 곳이 있으면 재귀 호출을 이용해서 계속 이동하지만 모든 곳을 방문하기 때문에 목표지점이 있지 않는 경로로 빠져서 비효율적인 결과를 초래할 수도 있음. 따라서, 이와 같은 비효율적인 경로를 차단하고 목표지점에 갈 수 있는 가능성이 있는 루트를 검사하는 방법이 백트래킹(Backtracking)알고리즘! # 백트래킹의 특징 : N이 작음(N이 10근처여야 사용가능함.) # => 재귀함수를 사용할 때, 종료 시점 잊지말기!!!
너비 우선 탐색(Breadth-First Search) : BFS 너비 우선 탐색(Breadth-First Search) - 그래프 탐색 방법 중 한 가지 종류 "시작 정점에 인접한 노드를 중심으로 탐색함" 아이디어 - 시작점에 연결된 Vertex 찾기 - 찾은 Vertex를 Queue에 저장 - Queue의 가장 먼저 것 뽑아서 반복 [그래프 예시] 파이썬으로 구현한 BFS 알고리즘 from collections import deque # BFS 함수 정의 def bfs(graph, start, visited): # 큐(Queue) 구현을 위해 deque 라이브러리 사용 - 젤 처음에는 큐에 1만 들어가있음 queue = deque([start]) # 현재 노드를 방문 처리 visited[start] = True # 큐가 빌 때까지 반복 while queue: # 큐..
이진 탐색 (Binary Search) 이진 탐색 : 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 반으로 쪼개가면서 탐색을 하는데 내부의 데이터가 반드시 정렬되어있어야 함. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 x와 비교한다. x가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로 비교하고, 크다면 배열의 우측을 대상으로 다시 탐색한다. -> 해당 값을 찾을 때까지 중간 값을 임의로 선택하고 비교하는 과정을 반복함. 예시) my_list = [1, 9, 3, 5, 7, 13, 11, 17, 15] 라는 배열이 있음. 반드시 정렬 과정이 필요! 1 3 5 7 9 11 13 15 17 중에서 5를 찾고자 한다면 1 3 5 7 9 11 13 15 17 처음값 1, 끝값 17 일때, 중간값은..
합병 정렬 (Merge Sort) 합병 정렬 : 배열을 좌 우로 나눈 후, 나눈 배열을 정렬하고 다시 붙인다. 퀵 정렬(Quick Sort)과 마찬가지로 재귀 용법을 활용하는 알고리즘이다. 분할 정복 알고리즘 중 하나로, 리스트 길이가 1 이하면 이미 정렬된 것으로 본다. 분할 : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 리스트로 만든다. 정복 : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합 : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이 때 정렬 결과가 임시 배열에 저장된다. 복사 : 임시 배열에 저장된 결과를 원래 배열에 복사한다. 알게된 개념 1. 리스트 요소 끄집어내기(pop) -> pop()은 리스트의 맨 마지막 요소를 돌려주고 그 요소는 삭제한다. >>> a = [1,2,3] ..
힙 정렬 (Heap Sort) 힙 정렬 : 힙은 완전 이진트리의 구조를 갖고 있는데, 자식 노드의 값이 부모 노드의 값보다 클 수 없다(작거나 같아야 함)는 조건을 만족해야 한다. 1. 최대 힙을 구성한다. (인덱스의 0번째 값이 최댓값이 된다) 2. 최댓값을 배열의 가장 마지막 위치에 놓는다. (큰 값을 뒤로 보내주는 과정 - 교환) 3. 그 다음 새로운 루트 노드에 대해 최대 힙을 수행한다. 4. 원소의 개수만큼 2~3번의 과정을 반복한다. 주어진 자료 구조에서 힙 성질을 만족하도록 하는 연산을 heapify라고 한다!!! heapify에서는 left = index * 2 +1, right = index * 2 + 2 공식을 만족한다. 파이썬으로 구현한 힙 정렬 def heapify(arr, index, heap_size): la..
728x90
반응형

티스토리툴바