알고리즘/이론

데이크스트라(다익스트라) 알고리즘 요약 정리

다익스트라 알고리즘이란? 매 단계마다 최단 거리 테이블을 확인하여 가장 가까운 거리의 정점을 찾고 찾은 정점의 인접한 정점에 대한 최단 거리의 값을 갱신하는 것으로 최단거리를 구하는 알고리즘 [!] 주의사항 그래프에 음수 간선이 포함되어있을 경우 다익스트라 알고리즘에 적합하지 않다!!! -> 벨만포드 알고리즘을 사용할 것 다익스트라 알고리즘은 힙을 이용해서 풀면된다. [!] pseudo 알고리즘 힙에 (거리, 시작점)을 입력한다. 처음에 넣는 값은 자기 자신이기 때문에 (0, 시작점)이 됨. 해당 정점을 기준으로 최단 거리를 계산하게 된다. 힙에서 하나의 원소를 pop하여 꺼낸다. 힙을 사용하므로 거리가 가장 작은 정점이 반환된다 반환된 값이 최단거리 테이블과 동일하지 않을 경우 제외한다. 초기 정점을 ..

플로이드 워샬 알고리즘 요약 정리

플로이드 워샬 알고리즘 이란 모든 정점의 쌍 사이의 최단 거리를 구하는 알고리즘 정점 사이의 최단 거리를 구하기 때문에 방향 그래프와 무방향 그래프 모두 상관없이 해당 알고리즘을 사용할 수 있다. 푸는 방법은 꽤 단순한데 N개의 정점이 있다면 NxN의 배열로 그래프를 나타낸 후에 해당 그래프를 최단거리 그래프로 교체해준다. 교체하는 방법은 거쳐가는 임의의 정점이 있다고 할때의 최단거리를 차례로 구한 후에 최솟값을 구하는 것. 보통 3중 for문을 사용해서 풀며 다음과 같이 가장 첫 for문의 k가 거쳐가는 정점을 의미한다. 그리고 j와 i는 시작 정점과 도착 정점을 의미한다. 여기서 아래 코드와 같이 거쳐가는 정점이 있을 때의 거리와 원래의 j -> i로 가는 거리 중 최단거리를 선택하도록 하면 된다. ..

재귀 (== 분할정복)

재귀란? 하나의 함수에서 자기 자신을 다시 호출하는 것으로 작업을 수행하는 알고리즘을 의미한다. 즉 귀납적인 사고 방식으로 문제를 해결하겠다는 뜻. 귀납적 사고는 위키백과 정의로 살펴보면 다음과 같다. 개개의 구체적인 사실이나 현상에 대한 관찰로 얻어진 패턴을 일반적인 규칙으로 이끌어나가는 절차 우리는 기본적으로 절차지향적 사고방식을 가지고 있다. 그렇다면 귀납적인 사고 방식과 절차 지향적 사고방식의 차이는 무엇일까? 다음과 같은 함수가 있다고 가정하자. # 기본적인 재귀함수 def func(n: int): if n == 0: return func(n-1) 절차지향적 사고방식 : func(2)를 호출함 -> 2를 출력 -> func(1) 을 호출함 -> 1을 출력 -> func(0)을 호출함 -> 종료 ..

그래프 관련 알고리즘 요약 정리 (크루스칼, 프림, 위상 정렬)

그래프를 사용하는 알고리즘은 뭐가 있을까? - 크루스칼, 프림, 위상 정렬 https://seclab-j.tistory.com/86 그래프 이론 요약 정리 그래프란? 그래프란 정점(Edge)과 간선(Vertex/Node)으로 이루어진 자료구조를 의미한다. 그림으로 나타내자면 다음과 같다. 차수(degree)는 간선으로 연결된 이웃한 정점의 개수를 의미한다. 그래프는 seclab-j.tistory.com 앞선 정리 내용에서는 코드로 그래프를 어떻게 표현하는가를 중점적으로 살펴보았다. (인접 행렬과 인접 리스트..) 오늘은 여기서 좀 더 나아가 그래프를 사용하는 알고리즘에는 무엇이 있으며 어떻게 사용하는지에 대해서 다루어 보고자 한다. 먼저 복잡도를 언급해보자면 다음과 같다. 알고리즘 종류 시간 복잡도 크루..

그래프 이론 요약 정리

그래프란? 그래프란 정점(Edge)과 간선(Vertex/Node)으로 이루어진 자료구조를 의미한다. 그림으로 나타내자면 다음과 같다. 차수(degree)는 간선으로 연결된 이웃한 정점의 개수를 의미한다. 그래프는 특징에 따라서 여러 종류로 구분할 수 있다. 1. 방향성 그래프에는 간선에 방향성이 존재하느냐 존재하지 않느냐에 따라서 무방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph)로 나뉜다. 2. 사이클 그래프안에 사이클이 존재하느냐 존재하느냐에 따라서 순환 그래프(Cyclic Graph)와 비순환 그래프(Acyclic Graph)로 나눌 수 있다. 이때의 사이클이란 임의의 한점에서 출발했을 때 다시 자기 자신으로 돌아오는 경로가 있을 때 이를 사이클이 존재한다고 한..

동적 계획법, 다이나믹 프로그래밍

다이나믹 프로그래밍의 Key Idea 다이나믹 프로그래밍으로 풀 수 있는 대표적인 문제는 피보나치 수열이다. 큰 문제를 작은 문제로 나누어 푼 후에 합치는 방법론. 이라고 보면될 것 같다. 하지만 모든 문제에 다이나믹 프로그래밍을 사용할 수는 없으며 다음 두 조건을 만족할 때만 가능하다. 큰 문제를 여러개의 작은 문제로 나눌 수 있는가? 작은 문제에서 구한 정답이 이를 포함하는 큰 문제에서도 도출되는 방식이 동일한가? Top-Down 방식(하향식) : 큰 문제를 작게 나누는 방법. 이는 분할 정복 알고리즘 (Divide and Conquer)와도 동일하다. Bottom-Up 방식(상향식) : 작은 문제부터 차근차근 답을 도출하는 방법론. 주로 단순 반복문을 사용하는 것에 해당한다. 피보나치 수열은 Top..

[알고리즘 파이썬편] 큐와 힙의 사용법

Python:: 큐, 힙 사용방법 큐 개념 및 사용방법 Queue == FIFO 구조 (선입선출) 파이썬 에서 큐를 사용할 때는 collections 모듈의 deque 객체를 사용하는 것이 가장 효율적이다. 가장자리에 존재하는 원소를 넣거나 뺄 수 있음. from collections import deque deque의 초기화 from collections import deque queue1 = deque() #빈큐 만들기 queue2 = deque([1, 2, 3]) #원소가 있는 큐 만들기 queue3 = deque(maxlen = 5) #최대 길이가 명시된 큐 만들기 ( maxlen에 도달시 그 후에 넣는 값은 pop->새값이 채워지는 구조) deque :: push 연산 from collectio..

[알고리즘 파이썬편] 해시와 셋의 사용방법

Python:: 해시, 셋 사용방법 해시 개념 및 사용방법 Python의 Hash는 Dictionary는 기본으로 dict 클래스에 구현되어있음 해시는 언제 사용해야하는가. 데이터의 중복이 없어도 될 때 : 집합의 모든 데이터는 유일함. 동일 원소를 제거할 때 사용하자. 빠른 접근 / 탐색이 필요할 때 : 딕셔너리는 대부분의 시간복잡도가 O(1)로 탐색이 매우 빠른 자료구조임 집계를 할때 : 코딩테스트에서는 각 원소의 개수를 세야하는 문제가 많이 나온다. 이때 사용하기 유용함! (collections의 모듈 Counter 클래스!!) Dictionary와 리스트의 시간 복잡도를 비교해보자. Operation Dictionary List Get Item O(1) O(1) Insert Item O(1) O(..