Programming/Algorithm
문제 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, ab는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, ab="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다면, 음이 아닌 정수의 제곱도 정의할 수 있다. a^0 = "" (빈 문자열) a^(n+1) = a*(a^n) 문자열 s가 주어졌을 때, 어떤 문자열 a에 대해서 s=a^n을 만족하는 가장 큰 n을 찾는 프로그램을 작성하시오. 입력 입력은 10개 이하의 테스트 케이스로 이루어져 있다. 각각의 테스트 케이스는 s를 포함한 한 줄로 이루어져 있다. s의 길이는 적어도 1이며, 백만글자를 넘지 않는다. 마지막 테스트 케이스의 다음 줄은 마침표이다. 출력 각각의 테스트 케이스에 대해, ..
문제 워드프로세서 등을 사용하는 도중에 찾기 기능을 이용해 본 일이 있을 것이다. 이 기능을 여러분이 실제로 구현해 보도록 하자. 두 개의 문자열 P와 T에 대해, 문자열 P가 문자열 T 중간에 몇 번, 어느 위치에서 나타나는지 알아내는 문제를 '문자열 매칭'이라고 한다. 워드프로세서의 찾기 기능은 이 문자열 매칭 문제를 풀어주는 기능이라고 할 수 있다. 이때의 P는 패턴이라고 부르고 T는 텍스트라고 부른다. 편의상 T의 길이를 n, P의 길이를 m이라고 하자. 일반적으로, n>=m이라고 가정해도 무리가 없다. n 0 and p[i] != p[j]: j = tmp[j-1] if p[i] == p[j]: j += 1 tmp[i] = j return tmp def KMP(s, p): cnt =..
KMP(Knuth-Morris-Pratt)은 무엇인가? KMP는 대표적인 문자열 매칭 알고리즘으로, 문자열과 패턴이 주어질 때 문자열 안에서 주어진 패턴을 찾아내는 알고리즘이다. 만약, 길이가 1,000,000인 문자열과 길이가 10,000인 패턴이 주어졌을 때 단순하게 모든 문자열의 경우의 수를 확인한다면 시간 복잡도는 1,000,000 * 10,000이 될 것이다. 즉, O(N^2)이 된다. 그러나 KMP 알고리즘을 사용한다면 사실상 O(N)으로 시간 복잡도를 줄일 수 있다. 이렇게 시간 복잡도를 줄일 수 있는 이유는 접두사, 접미사를 이용하여 불필요하게 반복되는 연산을 줄이기 때문이다. 접두사, 접미사 최대 개수를 담은 table 생성 앞서 말한 과정에서 미리 계산해 둔 접두사, 접미사 정보를 활용..
문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다. 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1..
문제 두 문자열 A와 B가 주어졌을 때, A에 연산을 최소 횟수로 수행해 B로 만드는 문제를 "최소 편집" 문제라고 한다. A에 적용할 수 있는 연산은 총 3가지가 있으며 아래와 같다. 삽입: A의 한 위치에 문자 하나를 삽입한다. 삭제: A의 문자 하나를 삭제한다. 교체: A의 문자 하나를 다른 문자로 교체한다. 두 문자열이 주어졌을 때, 최소 편집 횟수를 구하는 프로그램을 작성하시오. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 최소 편집 횟수를 출력한다. 예제 입력 1 abc ab예제 출력 1 1예제 입력 2 ca abc예제 출력 2 3 나의 풀이 해당 문제는 두 문자열의 편집 거리(edit dis..
문제 2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다. 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다) 의 경우에서 위로 블록을 이동시키면 의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 의 상태가 된다. 의 상태에서 블록을 오른쪽으로 이동시키면 가 되고, 여기서 다시 위로 블록을 이동시키면 이 된다. 여기서 오른쪽으로 블록을..
문제 링크 나의 풀이 우선 문제를 푸는 방법을 크게 정리하면 다음 과정을 거친다. 주어지는 블럭을 내려보낸다. 행(green) 또는 열(blue)가 꽉 찬 곳이 있는지 확인 있다면 해당 행 또는 열을 비워준다. 아래 빈 공간이 있는 블럭들을 아래로 내려보낸다. 2번의 과정을 반복한다. 연한 색의 칸에 블럭이 존재하는지 확인 존재한다면 해당 개수만큼 pop -> append [주의해야할 점] 큰 흐름으로 보면 그다지 어려워보이지 않지만 까다로운 조건들이 몇가지 있었다. 첫번째로 가로로 된 블록의 경우 붙어있어야 된다는 것이다. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -> 0 0 0 0 2 2 0 0 -> 2 2 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0..
문제 Your friend is an organizer of the International Chess Playing Championship. He is worried that some of the contestants may be cheating, and he has asked you to help out. The chess players are allowed to report matches to the jury themselves, and this is not checked with the reported opponent. So, it is possible for competitors to make up matches and falsely report themselves as the winners. ..
문제 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표하려고 한다. (작년에는 순위를 발표했다) 예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다. 창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 한다. 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하시오. 하지만, 본부에서 발표한 정보를 가지고 확실한 올..
