[CS(Computer Science)]/[Algorithm]

[Algorithm] 누적 합(prefix sum) 알고리즘 by python

누적 합(prefix sum) 알고리즘이 있습니다. 배열의 일부 구간에 대해 아주 빠른 속도로 구해줄 수 있는 알고리즘입니다. 일반적으로 배열에서 일부분의 값을 구하기 위해선 O(N)의 시간이 소요되지만, 누적 합 알고리즘을 사용하면 O(1)의 시간 복잡도를 기대해 볼 수 있습니다. 누적 합 알고리즘을 구하는 2가지 방법이 있습니다. 1. 1차원 배열일 때 주어진 배열 arr와 누적합을 구할 0 * (arr의 길이 + 1)로 초기화된 배열 sum_arr가 있어야 합니다. 그리고 주어진 배열을 순차적으로 탐색하면서 sum_arr 배열을 완성시키면 됩니다. 누적합 배열이기 때문에 sum_arr[i]에는 arr[0] + arr[1] + ... + arr[i-1]까지의 수의 합이 들어가 있다고 생각해야 합니다...

[Algorithm] 가장 긴 증가하는 부분 수열(longest increasing subsequence)

가장 긴 증가하는 부분 수열이라는 알고리즘이 있습니다. 어떠한 수열의 부분수열에서 증가하는 부분수열 중 가장 긴 부분수열을 의미합니다. 다이나믹 프로그래밍 문제를 해결할때 주로 사용됩니다. 특정 수열 A가 주어졌을때 가장 긴 증가하는 부분 수열의 길이를 찾는 문제가 있습니다. A = [ 10 20 10 30 20 50 ] 가장 긴 증가하는 부분 수열은 두가지 방법으로 해결할 수 있는데 하나는 시간복잡도 O(N2)로 해결하는 방법이고 다른 하나는 시간복잡도 O(NlogN)으로 해결하는 방법입니다. 1. 시간복잡도 O(N2) 가장 긴 증가하는 부분수열 문제에서 각 dp[i]값은 주어진 수열의 특정 값을 마지막 원소로 가지는 부분 수열의 최대 길이를 의미합니다. 여기서 특정값은 인덱스 i를 의미하고 A[i]의..

[Algorithm] monotone stack 알고리즘

monotone stack이란 단조로운 스택이란 뜻입니다. 단조로운 스택이란 무슨 말이냐면 항상 오름차순 또는 내림차순이 유지되는 스택을 의미합니다. 스택의 원소들을 O(n)시간복잡도를 가지면서 중복을 허용하지 않고 오름차순 또는 내림차순 상태를 유지하게 합니다. stack의 top에 있는 원소들을 새롭게 들어오려는 원소와 비교하여, 경우에 따라 pop을 진행합니다. 1. 중복없는 오름차순 stack의 경우, 들어오려는 원소가 stack의 top보다 작거나 같은경우 오름차순을 만족할떄까지 pop을 반복한 후 원소를 삽입해주어 오름차순을 유지합니다. 2. 중복없는 내림차순 stack의 경우, 들어오려는 원소가 stack의 top보다 크거나 같은경우 내림차순을 만족할때까지 pop을 반복한 후 원소를 삽입해주..

[Algorithm] BackTracking(백트래킹) 알고리즘

백트래킹 알고리즘은 기본적으로는 완전탐색이면서 DFS에서 가능성이 없는 경우를 가지치기하면서 탈출조건을 만들어 DFS의 성능을 높이는 알고리즘 입니다. 백트래킹에 대해 설명한 블로그의 링크를 걸어놓겠습니다. https://velog.io/@mmindoong/알고리즘-백트래킹BackTracking [알고리즘] 백트래킹(BackTracking) 백준 문제를 풀면서 알고리즘도 같이 정리해두면 좋을 것 같아서 정리해보겠다-! 💡 백트래킹 백트리킹이란 "가능한 모든 방법을 탐색한다"의 아이디어를 가진다. 즉, 백트래킹은 현재 상태에 velog.io 백트래킹의 입문문제인 N과 M 시리즈의 1번 문제입니다. https://hgk5722.tistory.com/84 [백준] 15649 파이썬(python) : N과 M ..

[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을 수행하는데 시간이 조금 걸린다. 더 빠르게 수행하기 위해 다이나믹 프로그래밍을 사용할 ..

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

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