신찬수 교수님의 알고리즘 - 동적계획법 소개 영상을 정리했습니다. 동적계획법 (Dynamic Programming) - 소개 n까지의 수의 합을 구하는 경우 sum(n) = sum(n-1) + n (단, sum(1) = 1) 위처럼 함수를 재귀호출해서 사용해서 구할 수 있다. 이때 만약 sum 값이 S라는 배열에 저장된다면 아래와 같은 코드가 된다. S[n] = S[n-1] + n (단, S[1] = 1) 첫 번째의 경우는 재귀호출을 사용하는 경우로 분할정복 방법이고, 두 번째 경우는 값을 배열에 저장해 재사용하는 경우로 동적계획법이다. 분할정복은 어떤 문제를 계속해서 작은 문제로 쪼갠 뒤, 작은 문제의 답을 통해 원 문제의 해답을 얻는 방법이다. 분할정복의 경우 분할된 각각의 작은 문제들이 중복이 없지..
Tushar Roy - Coding Made Simple님의 Knuth–Morris–Pratt(KMP) Pattern Matching(Substring search) 영상을 정리했습니다. KMP 하위 문자열 검색(KMP Substring Search) 문자열이 있을 때, 패턴 문자열이 문자열 안에 존재하는지 여부를 판단하는 알고리즘 문자열 abcbcglx에 패턴 bcgl이 존재하는지의 여부를 확인할 때, 일반적인 방법은 반복문을 돌리면서 문자열을 하나씩 비교하는 것이다. 이 경우 시간복잡도는 문자열의 길이 M, 패턴 길이 N에 비례하는 O(MN)이다. KMP 검색은 O(M+N) 시간에 하위 문자열 검색을 수행할 수 있다. 알고리즘 문자열 abxabcabcaby에서 패턴 abcaby이 존재하는지 KMP 알..
문제 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다. 강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다. 강토의 각 강의의 길이가 ..
문제 KOI 중학교에는 N개의 학급이 있으며, 각 학급의 학생 수는 모두 M명으로 구성된다. 이 중학교에서는 체육대회에 새로운 종목의 경기를 추가하였다. 이 경기에 대해 모든 학생들은 저마다의 능력을 나타내는 능력치를 가지고 있으며, 이 능력치는 모든 학생이 서로 다르다. 이 경기는 한반에서 한 명의 대표선수를 선발하여 치른다. 경기의 형평성을 위하여, 각각의 반에서 대표로 선발된 모든 학생들의 능력치 중 최댓값과 최솟값의 차이가 최소가 되도록 선수를 선발하려고 한다. 예를 들어, N=3, M=4인 경우 학생들의 능력치가 1반=[12, 16, 67, 43], 2반=[7, 17, 68, 48], 3반=[14, 15, 77, 54]로 주어질 때, 각 학급으로부터 능력치 16, 17, 15를 가진 학생을 각각..
들어온 문자열의 알파벳 개수를 세서 배열에 저장한다. 새로운 문자열을 생성해서 개수가 0이 아닌 알파벳을 붙인다. 생성된 문자열에 개수가 0 이상이고, 문자열의 맨 뒤 알파벳과 같지 않은 알파벳을 붙여준다. 재귀호출하여 문자열 뒤에 알파벳을 계속 붙여준다. 생성된 문자열의 길이가 처음 들어온 문자열의 길이와 같아지면 정답에 1을 더하고 리턴한다. int [] counts = new int[26]; int idx = (int)input.charAt(i)-'a'; counts[idx]++; 아스키코드를 이용해서 알파벳의 개수를 셌다. (해시맵으로 했다가 너무 오래걸리는 거 같아서 수정함~!) void check(String str, String input){ if (str.length() == input.l..
문제 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5개인 경우의 예시이다. 입력 첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 100)이 주어진다. 출력 첫째 줄에 옮긴 횟수 K를 출력한다. N이 20 이하인 입력에 대해서는 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K..
