[Computer Science]

[Algorithm] 다이나믹 프로그래밍(DP) - 탑다운, 바텀업

컴퓨터의 연산 속도에는 한계가 있고 그 속도를 단축 시켜줄 방법이 필요합니다. 연산속도와 메모리 공간을 효율적으로 활용할 수 있는 알고리즘 방법이 있습니다. 다이나믹 프로그래밍 우리말로는 동적 계획법이라고 불리우는 알고리즘입니다. 다이나믹 프로그래밍을 이용하여 풀 수 있는 문제를 알아보겠습니다. 피보나치 수열 : 인접 한 두 수를 더해서 다음 수를 구하는 수열 1 1 2 3 5 8 13 21 34 55 89.... 피보나치 수열 코드 def fibo(x): if x == 1 or x == 2: return 1 else: return fibo(x-2) + fibo(x-1) print(fibo(10)) 결과) 55 10을 수행하는데 시간이 조금 걸린다. 더 빠르게 수행하기 위해 다이나믹 프로그래밍을 사용할 ..

[Math] 음수 모듈러 연산 파이썬과 C언어 방식 - 정리(feat.윈도우 계산기)

프로그래밍 언어에 따라 음수 모듈러 연산을 처리하는 방식이 다릅니다. 언어마다 방식이 다르기 때문에 혼동이 생기므로 혼란을 피하기 위해 차이를 알아야 합니다. 자주 사용하는 언어는 c언어의 방식과 파이썬의 방식이 있으므로 두 언어의 따라 차이점을 설명하고 예제를 통해 간단한 계산하는 방식을 알아보겠습니다.  1. 파이썬 기준  프로그래밍 언어는 파이썬 기준입니다.(설명을 위한 계산기는 윈도우 공학용 계산기입니다)  파이썬은 나머지 연산 시 몫에 대해 내림 처리(Floored)를 하기 때문에 아래와 같은 결과가 나오게 됩니다.  나머지는 두 정수의 나눗셈 이후 딱 떨어지지 않은 남은 값입니다.a = q X d + r0   -5를 3으로 나머지 연산을 하면 값이 얼마일까요?    1이 됩니다.   -5 = ..

[Algorithm] 다익스트라 알고리즘

데이크스트라 또는 다익스트라 알고리즘이라 불리는 알고리즘을 알아보겠습니다. 다익스트라 알고리즘은 특정 노드에서 다른 노드로의 최단경로를 구하는 알고리즘입니다. 다익스트라 알고리즘에는 그리디와 다이나믹 프로그래밍이 녹아들어 있습니다. 이전 최소거리를 기억한다는 점에서는 다이나믹 프로그래밍이 현재 시점에서 항상 최소값을 찾는다는점이 그리디 알고리즘이 녹아있음을 알 수 있습니다. 다익스트라 알고리즘은 음의 간선이 존재하지 않을때 정상적으로 작동하는 알고리즘입니다. 모든 간선의 값은 0이상이며 그래서 GPS등에 활용할 수 있는 실생활에 적합한 알고리즘입니다. 다익스트라 알고리즘의 과정을 그림으로 알아보겠습니다. 시작 노드 A에서 도착 노드 F까지의 과정을 알아보겠습니다. 간선은 노드간 이동값(거리)입니다. 노드..

[Algorithm] 플로이드 워셜 알고리즘

플로이드 워셜 알고리즘 : 시작 노드에서 도착 노드로 갈때 특정 노드를 거쳐가는것이 더 빠르다면 최소값을 갱신해 주는 알고리즘 플로이드 워셜 알고리즘에는 다이나믹 프로그래밍이 녹아들어 있습니다. 두 알고리즘 모두 문제를 해결할때 점화식을 사용하기 때문입니다. 점화식은 다음과 같습니다. Dab = min(Dab, Dak + Dkb) a에서 b로 가는 값을 a에서 b로 가는 값과 a에서 k를 거쳐 b로 가는 값중 작은 값으로 갱신하라는 의미입니다. 플로이드 워셜 알고리즘은 이미 값을 가지고 있는 노드간의 거리에 특정 노드 k를 거쳐가는 과정을 수행해 줘야 하기에 3중 for을 사용합니다. 그래서 시간 복잡도는 O(N3)이 됩니다. 다음은 플로이드 워셜 알고리즘의 최소값 갱신 과정입니다. 이렇게 최소값을 갱신..

[Algorithm] 0-1 BFS

0-1 BFS : 가중치가 0과 1만 있는 그래프에서 작동하는 알고리즘 0-1 bfs는 시간 복잡도 O(V+ E)로 다익스트라 알고리즘의 O(ElogE) 또는 O(VlogV) 보다 빠릅니다. 가중치가 0인 정점이 존재하기 때문에 정점의 방문 횟수가 더 많더라도 가중치가 더 낮은 경우를 고려해야 합니다. 결괏값이 방문 횟수가 아니라 가중치의 최소를 구하는 문제에서는 가중치가 낮은 경로부터 찾아야 합니다. 정점 1에서 2로 이동 = 방문 횟수 1, 가중치 1 정점 1에서 3, 4를 거쳐 2로 이동 = 방문 횟수 4, 가중치 0 탐색을 할때 가중치가 낮은 노드를 먼저 돌아야 하므로 가중치가 낮은 노드는 큐의 앞(front)에 삽입합니다. 파이썬의 우선순위 큐에서는 리스트의 앞에 삽입하는 기능이 없으므로 deq..

[Algorithm] 에라토스테네스의 체, 소수 판정시 제곱근까지 확인하는 이유(python)

에라토스테네스의 체 소수를 구할때 많이 사용되는 에라토스테네스의 체를 알아보겠습니다. 소수를 구하는 첫번째 방법으로는 모든 숫자를 1에서부터 원하는 수 n까지 완전 탐색으로 소수를 찾아주는 방법이 있습니다. 가장 확실한 방법이지만 시간이 많이 걸린다는 단점이 있습니다. n까지의 소수를 구하는 코드 : 시간복잡도(O2) def PrimeNumber(n): res = [] for i in range(2, n+1): check = True for j in range(2, i): if i % j == 0: check = False break if check: res.append(i) return res 완전탐색을 사용해서 하나하나 모든 수를 체크해주는 방법입니다. 에라토스테네스의 체는 소수를 구하는데 시간을 단..