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. 개요 https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 1-1. 설명 총 N개의 문자열로 이루어진 집합 S가 주어진다. 입력으로 주어지는 M개 문자열 중 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성한다. 1-2. 제한 사항 - 첫째 줄에 문자열 개수 N과 M이 주어지며, 각각 1 이상 10,000이하 자연수 - 다음 줄 N개에는 집합 S에 포함되어 있는 문자열 - 다음 M개 줄에는 검사..

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원을 만들어라. 여기서는 위의 방법으로 풀어버리면 풀..

1. DP vs Backtracking DP는 problem과 sub-problem을 나누어 진행하고, 이 sub-problem은 더 작은 sub-problem으로 나누어 질 수 있다. 겹치는 sub-problem은 memorization을 통해 저장하면서 중복된 계산을 줄여갔다. 그러나, Backtracking은 우리가 가져갈 수 있는 모든 경우의 수를 하나씩 살펴보고, Decision space를 만들어 나간다. 여기서 어떠한 경우의 수가 의미가 없게되면 가지치기를 하게 되고 backtracking을 하면 된다. 2. Backtracking ex> Phone keypad 문제(leetcode 17) 우리가 아는 휴대폰의 키패드는 아래의 사진과 같다. "25"가 입력이 되었을 때, AJ / AK / A..