[알고리즘] 그래프 - 최단거리 구하기(cpp)
N개의 노드와 M개의 에지가 있는 그래프에서, 세 노드 s, a, t가 주어졌을 때 s에서 a를 반드시 지나서 t까지 도달하는 가장 짧은 거리를 구하는 프로그램을 작성하시오. 입력 표준 입력으로 입력을 받는다. 첫 줄에는 노드의 개수 N과 에지의 개수 M이 주어진다. 노드의 개수는 3 이상 100 이하이고, 에지의 개수는 0개 이상 N(N-1)개 이하이다. 두번째 줄에는 세 정수 s a t가 주어진다. 노드들은 0 이상 N 미만인 정수들로 표현되며, 이 세정수는 각각 시작 노드, 중간 노드, 도착 노드를 나타낸다. 세번째 줄부터 총 M줄에 에지 정보가 주어진다. 한 줄은 에지 하나에 대한 정보를 나타내며, 세 정수 U V W로 이루어진다. U는 에지의 시작 노드, V는 에지의 도착 노드, W는 에지의 가..
[알고리즘] 실패 함수 - 중복 최대 부분문자열(cpp)
영어 소문자로 이루어진 최대 길이 1,000인 문자열에서, 두 번 이상 나오면서 가장 긴 부분문자열의 길이를 출력하는 프로그램을 작성하시오. 예를 들어, banana의 경우 길이가 5인 부분 문자열은 banan, anana, 길이가 4인 부분 문자열은 bana, anan, nana, 길이가 3인 부분 문자열은 ban, ana, nan, ana이므로 ana가 2번 나오면서 가장 길이가 길다. 답은 따라서 이 경우 3이 된다. 힌트: 실패함수를 잘 이용해보자. 입력 표준 입력으로 입력을 받는다. 입력은 한 줄로 이루어지며, 최대 길이가 1,000인 영어 소문자로 이루어진 문자열이다. 출력 표준 출력으로 출력한다. 출력은 한 줄로 이루어지며, 입력된 문자열에서 두번 이상 나오면서 가장 길이가 긴 부분 문자열의..
[알고리즘] 문자열 다루기 - 로마숫자(cpp)
로마인들은 로마 숫자를 사용했다. 1은 I, 5는 V, 10은 X로 표현했고, I, V, X가 나타내는 문자열은 각 글자가 나타내는 수의 합이다. 예를 들어 XVI = 10 + 5 + 1 = 16이다. 단, IV는 4이고 IX는 9이다. 예를 들어 IVI = 4 + 1 = 5이다. 위의 예외에 추가로, IIV는 3이고 IIX는 8이라고 하자. 반드시 IIV, IIX는 3, 8이어야 한다. 즉 IIV는 1 + 1 + 5 = 7도 아니고, 1 + 4 = 5도 아니고, 반드시 3이어야 하는 것이다. 최대 길이가 10인 로마 숫자를 나타내는 문자열이 주어질 때 이 문자열이 나타내는 수를 출력하는 프로그램을 작성하시오. 입력 표준 입력으로 입력을 받는다. 최대 길이가 10인 문자열이 주어지고, 이 문자열은 I, ..
[알고리즘] DP - 계단 오르기(cpp)
N단의 계단이 있고, 한번에 계단을 한 단 또는 두 단을 올라갈 수 있다고 하자. 최대 두 군데의 계단에는 장애물이 있어서 올라갈 수 없다. 이 때 N단까지 올라가는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오. 입력 표준입력으로 세 정수 N A B가 주어진다. N은 계단의 단수로, 1 이상 30 이하이다. A와 B는 장애물이 있는 계단의 위치이다. A와 B는 0 이상 N 이하인 수이며, A와 B가 같을 수 있다. A, B 값이 0이라면, 이는 장애물이 없다는 뜻이다. 예를 들어 N, A, B가 3, 0, 1이라고 주어지면 총 3단의 계단이 있고, 장애물은 1단에만 있다. 조금 더 생각해보면 N, A, B가 3, 1, 0으로 주어져도 같다는 것을 알 수 있다. 출력 표준출력으로 하나의 정수를 출력..
