본문 바로가기

윤코딩

Notice

Recent Posts

Popular Posts

Recent Comments

Link

Calendar

Tags

더보기

Archives

Visits

Today

Yesterday

코딩테스트/기본 알고리즘

코딩테스트/기본 알고리즘 2022. 2. 24. 최단 경로 (simple_dijkstra) simple_dijkstra (간단한 다익스트라) 여러 노드가 있을 때, 측정한 노드에서 출발하여 다른 노드로 가는 각각의 최단경로를 구해주는 알고리즘 (음의 간선)이 없을때 정상적으로 작동한다. 그래서 현실세계의 길을 토대로 gps등에 주로 쓰이는 알고리즘이다. 기본적으로 가장 비용이 적은 노드를 찾아 갱신하므로 그리드 알고리즘으로 분류된다 알고리즘의 원리로는 출발 노드를 설정 최단 거리 테이블을 초기화 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 위 과정에서 3과 4를 반복 한단계를 완료하면 그 단계의 노드는 최단거리가 확실히 구해진것이다. 간단한 다익스트라 알고리즘은 O(v^2)의 시간복잡도를 가지는데 이때 ..

코딩테스트/기본 알고리즘 2022. 2. 24. 최단거리 (improved_dijkstra) improved_dijkstra 간단한 다익스트라는 O(v^2)의 시간복잡도를 가져 노드의 개수가 10000개를 넘어가면 풀수가 없다. 하지만 개선된 다익스트라는 최악의 경우에도 O(ElogV)를 보장하여 해결할 수 있다. (V는 노드의 개수, E는 간선의 개수) 기존 간단한 다익스트라는 최단거리를 앞에서부터 하나씩 확인했는데 이를 더욱 빠르게 heap구조의 우선순위 큐로 찾는다는것이 핵심 포인트이다. 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 특징이 있고 heapq 라이브러리를 통해 사용한다. 우선 순위 큐는 일반적으로 정수형 자료형의 변수를 사용하며 (가치, 무게)로 이루어진 데이터를 우선순위 큐에 집어넣으면 항상 가치가 높은 물건부터 먼저 나오게된다.(만약 (무게, 가치)로 ..

코딩테스트/기본 알고리즘 2022. 2. 23. 최단거리 (Floyd_Warshall) Floyd_Warshall 1.Floyd_Warshall 이란 플로이드 워셜 알고리즘은 '모든지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야할 경우' 사용한다. 총시간복잡도는 O(n^3)으로 많은 노드가 주어진 경우 사용하기 어렵다. 최단 거리를 저장하기 위해 1차원 리스트를 이용한 다익스트라와 다르게 모든 노드에서 다른 모든 노드로 가는 최단거리 정보를 담기위해 2차원 리스트를 처리해야한다. 점화식은 D(a,b) = min(D(a,b), D(a,k) + D(k,b) 이다. (A에서 B로가는 최소비용과 A에서 K를 거쳐 B로 가는 비용)을 비교하여 더 작은값으로 갱신한다. (직항과 경유의 비교) 2.예제코드 INF = int(1e9) n = int(input()) m = int(in..

코딩테스트/기본 알고리즘 2022. 2. 20. 다이나믹 프로그래밍(Dynamic_Programming) 1. Dynamic_Programming 이란 큰문제를 작은 문제로 나눌 때 주로 사용한다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할때 사용할 수 있다. 주의사항 : 재귀함수로 다이나믹 프로그래밍을 구현시 재귀함수를 적재하는 메모리에서 오버헤드가 발생할수있다. 따라서 다이나믹 프로그래밍에서는 재귀함수보다 반복문을 사용하여 오버헤드를 줄일 수 있다. 피보나치 수열은 다이나믹 프로그래밍의 대표 문제이다. 파보나치를 통해 다이나믹 함수를 이해해보자. 2. 예시코드(재귀함수 사용) d = [0] * 100 # 한 번 계산된 결과를 메모이제이션(memoization)하기 위한 리스트 초기화 def fibo(x): # 피보나치 수열을 재귀함수로 구현(탑 다운 다이나믹 프로그래밍) if x =..

코딩테스트/기본 알고리즘 2022. 2. 20. 순차탐색(Sequential_Search) Sequential_Search(순차 탐색) 1. Sequential_Search란 탐색 알고리즘 중 가장 간단한 알고리즘으로 단순히 앞에서부터 순차적으로 비교하며 찾아간다. 구현이 간단하지만 효율적이지 못하다. 2. 예시 코드 def sequential_search(n, target, array): # n : 문자열개수, target : 찾을값, array : 문자열 리스트 for i in range(n): if array[i] == target: # array[0]부터 순차적으로 target과 같은지 탐색한다. return i + 1 # i는 0부터 이므로 + 1

코딩테스트/기본 알고리즘 2022. 2. 20. 이진탐색(Binary_Search) Binary_Search(이진 탐색) 1. Binary_Search란 배열의 내부 데이터가 정렬되어 있어야 사용가능한 알고리즘으로 조건만 맞다면 매우 빠르다. (O(logn)의 시간복잡도) 데이터를 절반씩 좁혀가므로 위치를 나타내는 변수 (시작점, 중간점, 끝점) 3개가 필요하다. 찾으려는 데이터와 중간점 위치의 데이터를 반복적으로 비교하는것이 진행방식이다. 2. 예시코드 2.1 재귀함수 방식 def binary_search(array, target, start, end): if start > end: # array에 target값이 존재하지 않아 계속된 재귀함수 호출로 start > end가 된경우 None return return None mid = (start + end) // 2 # 중간점 if ..

코딩테스트/기본 알고리즘 2022. 2. 20. 깊이 우선 탐색(DFS) DFS(깊이 우선 탐색) 1. DFS(Depth First Search)란? 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 방법이다. 그래프는 노드(Node)와 간선(Edge)로 표현되며 노드는 정점(Vertex)라고도 한다. 그래프는 인접리스트(리스트로 그래프의 연결관계 표현)와 인접행렬(2차원 배열로 그래프의 연결 관계를 표현)로 표현할 수 있다. DFS(깊이우선탐색)는 스택 자료구조를 사용하며 동작과정은 아래와 같다. 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3. 2번위 과정을 더 ..

코딩테스트/기본 알고리즘 2022. 2. 20. 너비 우선 탐색(BFS) BFS(너비 우선 탐색) 1. BFS(Breadth-First Search)란? BFS알고리즘은 너비 우선 탐색이란 의미를 가진다. 이는 가까운 노드부터 탐색하는 알고리즘이란 뜻이다. DFS는 최대한 멀리있는(깊은) 노드부터 탐색하는것에 비해 BFS는 가까운 노드부터 탐색하므로 이 두개를 적절하게 사용해야 한다. BFS 구현에서는 선입선출, 즉 큐 자료구조를 사용하는것이 정석이다. BFS 알고리즘의 동작방식에는 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 2. 예시 코드 from collections import d..

이전 1 2 다음

티스토리툴바