Patrick's Devlog

1. 누적합누적합은 앞에서부터 차례대로 누적된 합을 구하고 이를 이용해 구간 합을 구할 수 있다.2. 문제크기가 N인 정수 배열 arr가 존재할 때 다음과 같은 연산을 M번 수행해야하는 문제가 존재한다. - 구간 l, r(l l부터 r까지를 구하기 위해, 반복문을 통해 단순히 구하게 된다면 시간 복잡도는 O(NM)이 나오게 된다. 여기서, 누적합 아이디어로 변경해보자.sum[i] = arr[1] +... + arr[i], sum[0] = 0으로 정의하고, l부터 r까지의 합은 sum[r] - sum[l - 1]과 동일하다.sum[r] = arr[1] + ... + arr[r], sum[l - 1] = arr[1] + ... + arr[l-1] 으로 정의되므로, 따라서 sum[r] - sum[l - 1]은..

1. Monotonic Stack단조 스택(Monotic Stack)은 알고리즘 문제 해결에 사용되는 특수 구조이며, 각 element들을 오름, 내림 차순으로 유지하는 알고리즘 기법이다. 일반적으로 배열에서 다음으로 크거나 작은 element를 찾는 등의 문제를 효율적으로 해결하는데  사용된다. 기존의 스택과 달리 단조 스택의 조건은 스택의 내부 element가 들어오는 element에 따라 증가, 감소하는 배열이 되도록 순서를 구성해주어야 한다. 2. 유형단조 스택의 유형은 두가지로 분류될 수 있다. 오름차순 단조 스택 (Monotic Increasing Stack)스택에 추가되는 현재 들어오려는 element는 스택에 저장된 element들보다 크거나 같아야 한다. 새 element의 크기가 작으면..

1. 트라이탐색 트리의 일종이며, 동적 집합이나 연관 배열을 저장하는데 사용되는 트리 자료구조이다. 문자열을 저장하고 효율적으로 탐색하기 위한 자료구조로 생각하면 된다. 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다. 대신 노드가 트리에서 차지하는 위치가 연관된 키를 정의한다. 즉, 키의 값은 자료 구조 전체에 분산됨을 의미한다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 메모리에 최적화된 경우에는 기수 트리가 된다.   2. 장단점문자열 검색 시 빠른 검색 가능문자열 탐색 시 하나씩 전부 비교하는 것 보다 시간 복잡도 측면에서 효율적각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있으므로 공간적인 측면(메모리)에서는 비효율적3..

1. 위상 정렬 방향 그래프의 정점(vertex)들의 방향(순서)에 거스르지 않도록 나열하는 것을 의미한다. 순서가 정해져있는 작업들이 존재한다고 가정해보자. 특정한 작업을 수행하고 싶을 때, 그 작업을 바로 수행하는 것이 아닌 해당 작업을 위한 선행 작업을 해야한다. 이때, 작업들의 순서를 결정하는 알고리즘이 위상 정렬 알고리즘이다. 2. 수행 과정 자기 자신이 가리키는 방향이 없는 정점(진입 차수가 0인 노드)을 찾음 찾은 정점을 출력 후, 출력한 정점과 해당 정점에서 출발하는 간선을 삭제 아직 그래프에서 정점이 남아있으면 처음으로 돌아가고 아니면 알고리즘 종료 수행 과정을 예시로 들어보자. 아래의 그래프가 존재한다고 가정하자. 참고로 이 그래프는 사이클이 없는 방향 그래프(DAG)여야 한다. 예시로..

1. 최대공약수(Greatest Commom Divisor, GCD) 공약수는 두 수 이상의 여러 수의 공통된 약수를 의미한다. 여기서 최대공약수는 두 수 이상의 여러 수 공약수 중 최대인 수를 가리킨다. 예제를 통해 살펴보자. 여기서 50과 90의 최대공약수를 구해보자 최대 공약수는 10임을 확인할 수 있다. 2. 최소공배수(Lowest Common Multiple, LCM) 공배수는 두 수이상의 여러 수의 공통된 배수를 의미한다. 여기서 최소공배수는 두 수 이상의 여러 수 공배수중 최소인 수를 가리킨다. 예제를 또 하나 살펴보자. 여기서 10과 30의 최소공배수를 구해보자 최소 공배수는 30이 됨을 확인할 수 있다. 최소 공배수는 (두 자연수의 곱 / 최대 공약수)로도 구할 수 있다. 3. 유클리드 ..

1. 투 포인터 알고리즘 투포인터 알고리즘 or 슬라이딩 윈도우라고 부르며, 배열에 순차적으로 접근해야 할 때 두 개의 점 위치를 기록하며 처리하는 알고리즘이다. 정렬되어 있는 두 리스트 합집합에도 사용된다. 문제 상황에 맞게 투 포인터를 적절히 사용하면 된다. 정확한 사용법은 아래의 예제를 확인해보자. 2. 특정 합을 가지는 부분 연속 수열 찾기 예제 특정 숫자의 배열이 주어질 때, 해당 배열의 연속 수열 합이 특정값을 가지는 것을 확인하는 문제이다. 앞 전에 풀었을땐, 완전 탐색으로 했으나 이번에는 투 포인터 알고리즘을 사용해보았다. 대략적인 순서는 우선 start와 end를 0으로 초기화 한 후, 현재 부분 배열 합이 특정값과 동일하면 count를 하나 올려준다. 그러나, 현재 부분 배열 합이 특정..

1. Dijkstra Algorithm 음의 가중치가 없는 그래프의 한 정점(Vertex)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다. 처음 알고리즘의 시간복잡조는 O(V^2)이나, 우선순위 큐 등을 이용해 더욱 개선된 알고리즘이 나오면서 최종적으로 O((V+E)logV)의 시간복잡도를 가지게 되었다. 여기서 V는 정점의 개수, E는 한 정점의 주변 노드이다. 그래프 방향 유무는 상관없으나, 간선(Edge)중 하나라도 가중치가 음수이면 알고리즘은 사용될 수 없다. 다익스트라를 확장시킨 알고리즘이 바로 A* 알고리즘이다. 1-1. Aigorithm P[A][B] -> A와 B사이의 거리라고 가정 1. 출발점으로부터 최단거리를 저장할 배열 d[v] 생성, 출발 노드에는 0을 출발점을 제외한 다른..

1. Greedy Algorithm(탐욕 알고리즘) 탐욕 알고리즘은 탐욕적인 방법으로 문제를 풀 수 있으나, 그 문제가 정말 맞는 방법인지 알기 어렵다. 만약 탐욕 알고리즘을 통해 최적의 알고리즘을 찾았지만, local minimum일 수 있으므로 global minimum만 존재하는 알고리즘인지 아는 것이 중요하다. example> 동전 바꾸기 문제 1. [10, 100, 500] 동전들이 존재할 때 최소한의 동전으로 710원을 만들어라. solution 1 > 가장 큰 동전으로 먼저 이용하고 이용한 동전을 빼주며 맞춰가면 된다. 500 x 1, 100 x 2, 10 x 1 2. [10, 30, 40, 50] 동전들이 존재할 때 최소한의 동전으로 70원을 만들어라. 여기서는 위의 방법으로 풀어버리면 풀..