김머성 블로그

KMP Best-Practice

#include #include #include #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); string t, s; getline(cin, t); getline(cin, s); int ts = t.size(); int ss = s.size(); vector pi(ss);//pi[x] = y 일 때, x 지점에서 이전 문자열과 y만큼 접 미/두 사가 일치함. // 부분 문자열 별 접두사 접미사 최대 중첩 길이 전처리 int cur = 0;//부분 문자열 포인터 for (int i = 1; i 0 && s[i] != s[cur..

동적계획법 PS 팁

동적계획법이란 큰 문제를 같은 해법을 가지는 재귀적인 부분문제들로 나눠서 각각의 해를 더해나가며 큰 덩어리의 해를 구하는 알고리즘이다. 문제 난이도가 올라갈 수록 점화식이나 DP테이블을 만들 때 어떻게 만들어야 할지 헷갈린다. 그래서 테이블 형태를 구상하거나 점화식을 구현할 때 도움이 됐던 팁 몇가지를 적어보겠다. 1. 문제 단계 분할 말 그대로 문제를 단계별로 분할한다. 이전 단계와 현재 단계에 관계가 있도록 분할 해야한다. 다음 단계의 최적해를 유추해 낼 때 현재(혹은 이전) 단계의 최적해를 사용해야한다. 만약 다음 단계의 최적해를 유추해 낼 때 현재 단계의 최적해를 전혀 사용하지 않는다면 문제를 잘못 이해했을 가능성이 상당히 높다. 2. 각 단계마다 영향을 주는 요소 갯수로 테이블 생성 - 만약 각..

동적 계획법::메모이제이션

동적 계획법이란:: 문제를 같은 해법을 가지는 재귀적인 덩어리로 분할 해서 각각 분할된 부분 문제들을 해결하고 이를 합쳐나가며 전체의 해를 찾는 풀이법을 말한다. 완전 탐색과 다른 점은 이미 계산된 해를 계산하지 않는다는 점이다. 이 때, 나눠진 부분 문제들이 같은 문제 일 경우, 의미없는 중복계산이 발생되어 코드가 느려진다. 메모이제이션은 각각의 부분문제들의 대한 해법을 따로 테이블에 계산해놓고 같은 부분 문제가 나올 경우, 그 해를 사용하는 알고리즘 기법이다. 이를 통해서 중복된 계산을 피하고 백트래킹으로는 답을 구하기 힘든 문제들을 비교적 쉽게 계산 할 수 있다. 중복 계산을 소거하기 위해서 사용되는 대표적인 기법이다. 부분 문제에 대한 해를 구했을 경우 그 해를 저장해놓고 이 후, 풀이과정에서 같..

[위상정렬]

위상 정렬이란:: 사이클이 존재하지 않는 방향 그래프에서 간선의 방향을 거스르지 않는 순서로 정점들을 정렬하는 알고리즘을 의미한다. 구현:: 그래프 데이터를 입력 받을 때 각 정점에 대한 진입간선의 수를 별도로 저장해 놓는다. 루프를 돌며 ㄱ. 현재 진입 간선의 수가 0개인 정점을 찾는다. ㄴ. 해당 정점에 연결된 정점들의 진입 간선 수를 1 내리고 해당 정점을 방문 불가 상태로 바꾼다. 위의 과정을 반복하며 정점을 방문 순서대로 찍으면 위상 정렬이 완료된다. for(i=1;i> s; cin >> e; arr[s][++arr[s][0]] = e; enterdg[e]++; 진입간선 카운트 } for(i=1;i

[Spanning Tree]

스패닝 트리란:: 1. 그래프에서 최소 간선만을 사용하여 그래프의 모든 정점을 잇는 부분 그래프이다. 즉 v - 1개의 간선을 사용해 모든 정점을 이어야 하며 내부 사이클이 없어야한다. 2. 한국말로 신장트리 최소 비용 스패닝 트리 1. 간선에 가중치가 주어졌을 때 스패닝 트리를 완성하면서 최소비용을 구하는 알고리즘을 말한다. 2. 문제는 대부분 이걸로 나온다. 구현:: 최소 비용 스패닝 트리를 구축하는 방법은 2가지가 있다. 1. 정점 위주 연결 ㄱ. 시작 정점에 이어진 정점중 비용인 최소이고 연결되지 않은 정점을 하나 골라 연결하고 [연결된 정점]으로 분류한다. ㄴ. [연결된 정점]에 이어진 정점 중 하나를 골라 연결하고 [연결된 정점]으로 분류한다. v - 1개의 [연결된 정점]이 추가 될 때 까지..

[기타] 라인 스윕

위처럼 위치가 표시되어이있는 직선에 임의의 점 2개를 찍고 직선을 긋는다. 직선끼리 일부분이 겹칠 수도 있다. 총 N개의 직선을 그었을 때 그어진 선의 전체 길이를 구하는 문제이다. 간단하게 직선마다 배열에 1을 찍으며 길이를 구할 수도 있지만 그렇게 하면 선분의 수가 많아졌을 때 매우 비효율적인 알고리즘이 되어버린다. 극단적인 예를 들었을 때 위 문제의 최대 데이터가 +-10,0000이고 길이 최대인 선분 1,0000개를 그린다고 하면 총 20,0000,0000번 반복하는 알고리즘이 되어버리는 것이다. 위 문제는 대부분 주어지는 N과 전체 구간의 크기가 크기 때문에 O(n) 복잡도를 가지도록 구현 해야한다. a. 기본 개념 풀이 직선의 양 끝단을 받을 때 a가 b보다 작다면 a와 b를 바꿔 저장한다. ..