문제를 방향 그래프로 만들어 오일러 경로 또는 오일러 트레일을 구하는 문제로 변환할 수 있다. a부터 z를 정점으로 두고 단어의 시작 알파벳에서 단어의 마지막 알파벳으로 가는 간선을 추가한다. 예를 들어 dog 단어가 나온다면 d에서 g로 가는 간선을 추가한다. 그런 다음 방향 그래프에 오일러 경로 혹은 트레일이 존재할 수 있는지 확인 후 오일러 경로 또는 오일러 트레일을 구해 단어를 출력한다. (모든 정점) 진입 차수 = 진출 차수 → 오일러 경로 존재 (시작점) 진출 차수 = 진입 차수 + 1, (끝점) 진출 차수 = 진입 차수 - 1, (나머지 정점) 진입 차수 = 진출 차수 → 오일러 트레일 존재 import java.util.*; import java.io.*; public class Main ..
주어진 단어들을 가지고 DAG를 만들어 위상 정렬 하는 문제이다. 임의의 알파벳 a, b에 대해서 a가 b보다 사전 순으로 앞선다면 a에서 b로 가는 간선이 존재하도록 DAG를 만든다. DFS()가 종료될때마다 리스트에 정점을 넣고 모든 DFS가 끝난 후 리스트를 역순으로 정렬하면 위상 정렬 결과를 얻을 수 있다. DAG에 사이클이 존재한다면 모순이 발생한다. 사이클 발생 여부를 직접 체크할수도 있지만 어차피 위상 정렬을 해야 되기에 간단하게 위상 정렬 후 결과에서 오른쪽에서 왼쪽으로 가는 간선이 있다면 DAG에 사이클이 존재한다는 걸 알 수 있다. import java.util.*; import java.io.*; public class Main { public static void main(Strin..
이미 비슷한 문제를 푼 적이 있다. LIS 문제를 풀어보았다. 비슷한 형태의 문제들은 비슷한 부분 문제 정의를 사용해 풀 수 있는 경우가 많다. 기존 LIS를 푸는 문제 f는 다음과 같았다. f(start_idx) : start_idx 위치의 수에서 시작하는 LIS 개수 리턴 합친 LIS를 푸는 문제 f의 정의를 다음과 같이 정의한다. f(indexA, indexB) : indexA와 indexB 위치의 수에서 시작하는 합친 LIS 개수 리턴 indexA와 indexB위치의 수에서 시작하므로 다음에 오는 수는 indexA, indexB 위치의 수들보다 더 커야한다. 따라서 아래의 점화식이 만족한다. nextA는 다음에 올 수 있는 A의 수들의 인덱스이며 nextB도 다음에 올 수 있는 B의 수들의 인덱스..
처음엔 무식하게 풀어본다. 이때 해당 문제가 최적 부분 구조를 만족한다는 것을 쉽게 알 수 있다. 예를 들어 임의의 위치에 있는 수 A를 LIS의 첫 숫자로 골랐다고 가정하면 A부터 시작한 LIS 개수는 A보다 뒤에 있고 큰 원소부터 시작한 LIS 개수(B) + 1이라는 것을 알 수 있다. B를 구할 때 이전에 선택한 수 A는 알 필요가 없다. 최적 부분 구조를 만족하므로 DP를 적용해 중복되는 부분 문제를 제거한다. 백준 11053번 가장 긴 증가하는 부분 수열 문제이다. 함수 f는 start_idx 위치의 수를 시작으로 하는 LIS 개수를 리턴한다. 함수 f를 호출 할 때마다 최대 n개의 부분 문제가 발생하고 함수 f를 n번 반복 호출하므로 O(n²)의 성능을 보인다. import java.lang...
무식하게 풀 수 없을까? 한국 선수들의 순열을 만들어 러시아 선수들과 매칭 시킨다면 n!의 경우의 수가 발생하므로 시간 초과가 발생한다. 그럼 러시아팀을 상대로 최다승을 할 한국 선수들을 탐욕적으로 선택할 수는 없을까? → 남은 선수 중 상대방 선수를 한명이라도 이길 수 없는 선수가 있다면 가장 레이팅이 높은 러시아 선수와 매칭시킨다. 남은 선수 중 상대방 선수를 이길 수 있는 선수들이 있다면 그 선수들 중 가장 레이팅이 낮은 선수를 매칭시킨다. import java.lang.*; import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { Buffered..
무식하게 풀 수 없을까? 모든 회의의 선택을 고려하려면 각 회의를 선택할 것인지 말 것인지 결정하면 된다. 따라서 2ⁿ의 경우의 수가 생기므로 시간 초과가 발생한다. 그럼 가장 많은 회의를 할 수 있도록 각 회의를 탐욕적으로 선택할 수 없을까? → 가장 빨리 끝나는 회의만을 선택한다. 가장 빨리 끝나는 회의만을 선택해도 문제의 답을 구할 수 있게 된다. 백준 1931번 회의실 배정 문제이다. import java.lang.*; import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(..
처음엔 무식하게 풀어본다. 이때 해당 문제가 최적 부분 구조를 만족한다는 것을 쉽게 알 수 있다. 예를 들어 임의의 수 A부터 시작한 최대 경로는 A 바로 아래 수부터 시작한 최대 경로(i), A 바로 오른쪽 아래 수부터 시작한 최대 경로(ii) 둘 중 하나다. i나 ii를 구할때 이전에 선택한 값 A는 필요없다. 최적 부분 구조를 만족하므로 DP를 적용해 중복되는 부분 문제를 제거한다. 함수 f는 x,y수를 시작으로 한 최대 경로의 숫자 합을 반환한다. 삼각형의 원소 개수만큼 부분 문제가 발생하므로 O(n)의 성능을 보인다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) thr..
아래는 종만북의 DP의 메모이제이션 코드 패턴이다. //메모이제이션 사용 예 //전부 -1로 초기화 int cache[2500][2500] //a와 b는 각각 [0,2500) 구간 안의 정수 //반환 값은 항상 int형 안에 들어가는 양수 int someObscureFunction(int a, int b) { //기저 사례 처리 if(...) return ...; //답을 구한적이 있으면 곧장 반환 if(cache[a][b] != -1) return cache[a][b]; //답을 구한적이 없으면 여기서 답을 계산 cache[a][b] = ...; return cache[a][b]; } 외발뛰기 코드 import java.util.*; import java.io.*; public class Main { ..
