목록알고리즘 (6)
Developer_Neo
[알고리즘] 최단경로 알고리즘(다익스트라 알고리즘)
최단 경로 문제란? 두 노드를 잇는 가장 짧은 경로를 찾거나 가중치가 있는 그래프(Weighted Graph)에서 간선의 가중치의 합이 최소가 되도록 하는 경로를 찾으려는 것이 목적 최단 경로 문제 종류 단일 출발 및 단일 도착 (single-source and single-destination shortest path problem) 최단 경로 문제 그래프 내의 특정 노드 u 에서 출발, 또다른 특정 노드 v 에 도착하는 가장 짧은 경로를 찾는 문제 단일 출발 (single-source shortest path problem) 최단 경로 문제 그래프 내의 특정 노드 u 와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제따지고 보면 굉장히 헷깔릴 수 있으므로 명확히 하자면, 예를 들어 A,..
[알고리즘] BFS(Breadth First Search), DFS(Depth-First Search)
대표적인 그래프 탐색 알고리즘 너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식 깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식 BFS(Breadth First Search) - 너비 우선 탐색으로써 같은 레벨에 있는 노드들을 왼쪽에서부터 모두 탐색한 후에 다음 레벨로 넘어가는 것이다. - A - B - C - D - G - H - I - E - F - J 순서이다. 코드로 나타내어보자 파이썬에서 제공하는 딕셔너리와 리스트 자료 구조를 활용해서 그래프를 표현할 수 있음 graph = dict() graph['A'] = ['B', 'C'] graph['B'] = ['A', 'D'] g..
[알고리즘] 이진탐색(Binary Search)
이진 탐색 - 컴퓨터과학, 수학등에서 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘 리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다 위의 이미지 출처 Binary Vs Linear Search Through Animated Gifs Average Case Worst Case Binary Search Best Case Binary Search If you're into searching, maybe you're also into sorting! Check out our Sort Detective for exploring com..
[알고리즘] 동적 계획법(Dynamic Programming, DP)
동적 계획법 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법으로 이미 했던 연산이 반복되는 결점을 보완하기 위해서 고안되었다 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다. 링크 동적 계획법 - 위키백과, 우리 모두의 백과사전 수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 ..
[알고리즘] 정렬 with 버블 , 삽입, 선택, 퀵, 병합 정렬
정렬이란 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것 정렬 종류 버블 정렬 삽입 정렬 선택 정렬 퀵 정렬 병합 정렬 평균 시간복잡도 최악의 시간복잡도 최선의 시간복잡도 O(n) O(n) Runtime (60,000개 입력시) 단위 : sec 22.894 7.438 10.842 0.014 0.026 버블 정렬 (bubble sort) 란? 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘 서로 비교해서 큰 값을 뒤로 보내는 것이다. (오름차순으로) 핵심 SWAP 방식 2021.09.04 - [프로그래밍/알고리즘 with Java] - [자바] 정렬 알고리즘 - 버블정렬 [자바] 정렬 알고리즘 - 버블정렬 버블 정렬(Bubble So..
[알고리즘] 알고리즘 복잡도(시간복잡도,공간복잡도)
왜? 배우는가 하나의 문제를 푸는 알고리즘은 다양할 수 있다 이 다양한 알고리즘 중 어느 알고리즘이 더 좋은지 분석하기 위해, 복잡도를 정의하고 계산한다. 종류 시간복잡도 : 얼마나 빠르게 실행되고 결과를 도출하느냐 공간복잡도 : 얼마나 공간(메모리 사이즈)을 쓰느냐 둘 중에 더 중요한 것은 시간복잡도이다. 왜냐하면 요즘은 메모리가 매우 커졌기 때문에 시간복잡도보다는 중요도가 후 순위이다. 시간복잡도의 주요요소 - 반복문이 주요요소이다. 즉 반복문이 가장 영향을 많이 미친다.(입력의 크기가 커지면 반복문이 알고리즘 수행시간을 지배한다.) 그러면 시간복잡도를 우리 눈에 보기 좋게 객관적으로 표현을 해야 비교가 가능하다. 그래서 나온것이 빅오 표기법이다. 알고리즘 성능 표기법 Big O (빅-오) 표기법: ..