알고리즘

[알고리즘] 최단경로 찾기

최단경로 다익스트라 최단 경로 알고리즘 플로이드 워셜 알고리즘 그리디알고리즘과 다이나믹 알고리즘이 적용됨! 다익스트라 최단 경로 알고리즘 다익스트라(Dijkstra) 알고리즘은 여러개 노드가 있을 떄 특정노드에서 다른 노드로 도착하는 각각의 최단 경로를 구하는 알고리즘이다. 매번 가장 비용이 적은 노드를 선택하는 과정을 반복하기 떄문에 그리디 알고리즘으로 분류 음의 간선이 없을 때 적용가능하다. 과정 1. 출발 노드 선정 2. 최단 거리 테이블 초기화(무한으로 초기화) 3. 방문 하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택 4. 노드를 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블을 생성 5. 3번과 4번의 과정 반복! import sys input=sys.stdin.readline ..

[알고리즘] 다이나믹 프로그래밍

다이나믹 프로그래밍 다이나믹 프로그래밍(Dynamic Programming)기법은 동적계획법이라고도 하는데, 메모리공간으 더 사용해서 연산속도를 증가시킬 수 있는 알고리즘이다. 탑다운 방식 보텀업 두가지 방식이 있다. 다이나믹 프로그래밍을 사용할 수 있는 조건 큰 문제를 작은 문제로 나눌 수 있을때 작은 문제에서 구한 답이 작은 문제를 포함하는 큰 문제에서도 답이 동일할 때 대표적인 예시로 피보나치 수열로 설명을 할 수 있다. 피보나치 수열은 이전 두항의 합이 현재의 항이 되는 수열이다. 1 1 2 3 5 8 13 21 34 55 ... 이런식으로 말이다. 이를 점화식으로 표현하면 an=an-1+an-2, a1=1, a2=1 단순히 코드로 표현하면 def fibo(a)i : if a==1 or a==2:..

[알고리즘] 이진탐색

이진탐색 이진탐색(Binary Search)은 반으로 쪼개가면 탐색하는 알고리즘이다. 단, 데이터가 정렬되어있다는 것을 전제조건으로 깔고 간다. 이를 위해 시작, 끝, 중간점을 변수로 지정하여 찾으려는 값과 배열의 중간점에 있는 데이터를 반복적으로 비교한다! 시간복잡도 : O(logN) 코드 구현 #이진탐색은 전제조건을 정렬이다. #처리해야할 데이터 개수나 값이 1000만 단위 이상으로 넘어가면 이진탐색과 같이 o(logn)의 속도를 내는 이진탐색을 고려야한다 def binary_search(array, target, start, end) : if start>end : return None pivot=(start+end)//2 if array[pivot]==target : return pivot elif..

[알고리즘] DFS/BFS

DFS DFS(Depth-First Search)는 깊이 우선 탐색 알고리즘이다. 그래프에서 깊은 부분을 우선으로 탐색하는 것이다. 그래프가 그럼 뭘까? 그래프는 Node(혹은 정점이라고 부르기도함(vertex))와 Edge(간선)로 표현된다. 예를 들어 노드를 장소, 간선을 거리라고 생각할 수도 있다. 약국에서 병원까지의 거리를 3km, 약국에서 학교를 5km라고 한다면 아래 이미지처럼 표현할 수 있다. 약국 병원 학교 약국 0 3 5 병원 3 0 무한 학교 5 무한 0 ※ 연결되지 않은 노드는 무한으로 표현한다 그래프는 두가지 방식으로 표현된다. 인접 행렬 : 2차원 배열로 그래프의 연결관계를 표현 인접 리스트 : 리스트로 그래프의 연결관계를 표현 인접행렬(Adjacency Matrix) INF= 9..