CS/자료구조,알고리즘 (19) 썸네일형 리스트형 배낭문제에서 넣은 것을 저장하는 아이디어 문제는 https://www.acmicpc.net/problem/14728 문제를 예로 들었다. 배낭문제를 푸는데 어떤 것을 넣었는지 기억해야하는 문제가 있었다. 나의 경우 trace 벡터를 만들고 배낭에 넣을 때의 따라 벡터를 조절하며 문제를 해결했다. 그러나 2차원 크기의 벡터가 필요하기 때문에 메모리가 상당히 많이 필요할 것으로 보여서 N이 충분히 작을 때만 사용할 수 있을 것 같다. 더 좋은 방법이 있을까... 트레이스 벡터는 만약 갱신하게 되면 i번 물건을 가져간다는 의미로 인덱스를 넣는다. dp와 거의 유사하게 동작한다. #include#includeusing namespace std;int N, M;int dp[101][10001];int main(){ cin >> N >> M; vector.. 누적합 알고리즘(1차원, 2차원 누적합) 누적합 알고리즘은 1~N까지 합을 효율적으로 구할 수 있는 알고리즘이다. 11 + 21 + 2 + 31 + 2 + 3 + 4 라고하면 sum[1] = 1sum[2] = 3sum[3] = 6sum[4] = 10 이고 여기서 2~4까지의 합을 구하면 sum[4] - sum[1] 과 같다. 즉 answer = sum[end] - sum[start - 1] 이다. 그리고 중요한건 모든 sum 배열을 구성하는 것이다. 이 때 O(N^2)의 시간을 사용하는 것은 너무 비효율적이다. 효율적으로 사용하기 위해 sum[2] = sum[1] + arr[2]sum[3] = sum[2] + arr[3]... 식을 사용하면 O(N)으로 prefix배열을 구성할 수 있다. 1차원 배열 누적합은 쉽게 구성이 가능하다. 이것을 응용.. 최소 스패닝 트리 (MST) - 크루스칼 알고리즘 MST는 최소 스패닝 트리의 줄임말로 어떤 그래프가 있을 때 모든 노드를 포함하여 사이클이 생기지 않는 트리를 뜻한다. 한붓그리기를 생각하면 편하다. 크루스칼 알고리즘은 Greedy 알고리즘의 일종이다. 간선을 선택할 때 가장 비용이 적은 간선을 선택하면서 사이클이 생기면 넘어가는 식으로 진행된다.그렇기 때문에 크루스칼 알고리즘은 모든 간선의 정보가 정렬되어 있어야 사용할 수 있고 모든 간선을 한번씩 검사하기 때문에 시간 복잡도 = 모든 간선의 수 + 정렬 시간 이 소요된다. 사이클을 검사해야하기 때문에 필연적으로 유니온 파인드 알고리즘도 필요하다. 나름 여러 알고리즘이 합쳐진 고급 알고리즘이라 할 수 있다. 정리해보면 1. 간선의 정보들을 모두 정렬한다. 간선의 비용이 적은 순서대로2. 선택한 간선들.. Dynamic Programming - Top Down, Bottom Up 다이나믹 프로그래밍은 메모이제이션을 사용해 이전에 사용한 값을 그대로 읽어 사용함으로서 극적으로 줄일 수 있다. 여기서 메모이제이션의 개념을 보면 마치 캐시 와 비슷해보인다. 그래서 혹자는 캐시질이라고도 한다. Top - Down큰 숫자에서 작은 숫자까지 내려가면서 솔루션을 구하는 방법이다. rec(N){ dp[N] = min(rec(N - 1), rec(N - 2))}Bottom - Up작은 숫자부터 시작하며 다음 숫자에서 이전의 값을 사용하는 정석적인 dp 방식이다. 주로 점화식을 찾아서 적용시킬 때 사용된다.for(int i = 2; i 알고리즘 - 에라토스테네스의 체(C++) 최근 코딩테스트에서 소수를 판별해야하는 문제가 나왔다. 그래서 에라토스테네스의 체를 사용해야함을 바로 알았지만 아쉽게 떠올리지 못하여 정리해두려고 한다. 원래 소수를 판별하는 방법은 대학교 1학년 C언어 시간에 배울 정도로 쉽다. N까지 모두 나눠보며 나눠 떨어지는 수가 2이면 소수이다. 그러나 이것은 매우 시간이 오래걸린다. 에라토스테네스의 체는 이 수가 소수인지 아닌지 판별하는 것이 아니라 1~100만 등 어떠한 범위내에서 소수인지 아닌지 판별할 때 유용하다. 즉 1~100만 중 소수가 몇개인가? 이러한 것을 해결하는 방법이다. 알고리즘은 다음과 같다. 1. 2 ~ N까지 2의 배수를 false 처리한다. 2. 3 ~ N까지 3의 배수를 false 처리한다.4. 5 ~ N까지 5의 배수를 fals.. unordered_map을 이용한 노드 개수 최적화 알고리즘 문제를 풀다가 이런 문제를 발견했다. 다익스트라 문제인데 노드는 50개 뿐이지만 노드의 번호 범위가 무려 1~10억이었다. 다익스트라는 dp기반이기 때문에 dp[노드의개수]로 맞춰놓는 것이 일반적이다. 그런데 dp[10억]은 엄청난 메모리 낭비를 초래한다. 그래서 사용할 수 있는 방법이 바로 unordered_map을 이용한 노드 개수 최적화이다. unordered_map는 자동으로 키값으로 정렬하는 맵과 달리 정렬하지 않는 해싱기법이다. unordered_map nodes; int get_idx(int v) { return nodes[v]; } 먼저 맵을 선언해두고 인덱스를 겟할 수 있는 함수를 만들어준다. for (int i = 0; i < N; i++) { if (nodes.count(원래.. 문자열 찾기 - KMP 알고리즘 KMP 알고리즘이란? KMP 알고리즘이란 문자열에서 단어를 빠르게 골라낼 수 있는 알고리즘이다. 러프하게 생각하면 쉽게 문자를 찾아낼 수 있지만 이것은 아주 느리다. KMP의 아이디어 KMP의 중요한 아이디어는 접미사와 접두사이다. 접미사와 접두사는 단어를 반으로 잘라 왼쪽이 접두사 오른쪽이 접미사가 된다. ABCDAB 가 있으면 ABC는 접두사 DEF는 접미사가 된다. 자, 이걸 어떻게 쓸 수 있을까. 위 단어는 접두사와 접미사가 일치하는 것이 없다. 그러니 다른 예제를 보자. ABA 라고 생각하자. 접두사와 접미사에 모두 A가 있다. 그리고 ABAABA 라는 인풋에서 ABA를 찾는다고 생각해보자. ABAABA ABA 1개를 찾았다. 원래같으면 ABAABA ABA ABA 이런식으로 슬라이딩 윈도우처럼 .. 최소 스패닝 트리 (MST) - 프림 알고리즘 최단거리 알고리즘에는 우리가 익히 잘 아는 다익스트라 알고리즘, BFS가 대표적이다. 그러나 이 두개의 알고리즘은 모든 정점을 지나지 않고 무조건 최단거리를 찾는다. 그래서 모든 정점을 방문해야하는 문제를 해결할 수 없다. 때문에 MST 최소 스패닝 트리가 필요하다. 그래프에서 모든 정점을 지나는 트리를 그린다는 의미이다. 1. 프림 알고리즘 프림 알고리즘은 "정점" 을 아무거나 한 개 선택한다. 그리고 정점의 인접 정점들 중 가장 거리가 가까운 정점으로 이동한다. 그리고 지금까지 지나온 정점들 중 가장 가까운 곳으로 간다. 그림을 통해 이해하자. 자세히 설명해보면, 스탭1: 아무 정점이나 넣는다. 보통 1을 넣는다. 그리고 1에서 가장 가까운 곳으로 이동하면서 dist 배열을 업데이트한다. 스탭2: 현.. 이전 1 2 3 다음
