어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.
어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 N이 주어진다.
출력:
첫째 줄에 조건을 만족하는 수를 출력한다.
풀이방법:
소수를 판정하는 알고리즘 중 에라토느테네스의 체와 팰린드롬 알고리즘을 함께 사용하는 알고리즘이다. N으로 들어올 수 있는 가장 큰 숫자인 1,000,000에 해당하는 답은 1003001이라는 사실을 사용해서 그 만큼을 sosu 리스트를 초기화했다. (혹은 넉넉하게 큰 길이로 초기화해도 된다.) 이 sosu 리스트를 에라토스테네스의 체를 사용해서 소수만 남겨둔다.
이후 while 반복문을 통해서 sosu이면서 팰린드롬인 경우에 그 숫자를 출력하고 break를 통해 정지시키면 된다.
그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.
그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.
입력:
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.
출력:
K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.
풀이방법:
위키피디아에 따르면 이분 그래프란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다. 즉 한 변의 양 끝은 빨강과 파랑으로 서로 달라야 한다는 것이다.
dfs로 정점을 탐색하며, visited에다 색을 기록한다. dfs로 탐색하는 도중에 visited에 서로 다른 색이 들어오게 되면 이분그래프가 아니므로 False를 반환하도록 한다.
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?
입력:
입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.
출력:
각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.
풀이방법:
너비 우선 탐색의 가장 기초적인 문제다. 이미 지나온 곳을 다시 방문하지 않도록 0으로 초기화된 visited 배열을 만들었고, 현재 stage에서 나이트가 있을 수 있는 위치를 able이라는 배열에 저장하도록 했다.
bfs 함수 내에선 우선 able 내에 목적지가 있는지 확인하는 과정을 먼저 거친다. 있다면 현재 stage(count)를 출력하도록 하고, 없으면 나이트가 움직일 수 있는 경우의 수인 candidate를 able을 각 케이스에 대해 더해줘서 새로운 able을 만들도록 한다. 이 과정을 재귀적으로 반복하면서 값을 찾는다.
흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.
주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다.
위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다. N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.
입력:
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.
출력:
영상을 압축한 결과를 출력한다.
풀이방법:
분할정복을 사용해서 풀어야 하는 문제다. 반복해서 영상을 4분할로 나누면서, 같은 숫자로 구성되어 있는지 파악하면 된다.
각 분할된 분면에서 왼쪽 상단에 있는 점을 기준점으로 삼아서, 반복문을 순회하면서 같은 숫자로 구성되어 있는지 확인한다.
만약 같은 숫자로 구성되어 있으면 더 이상 분할할 필요가 없으니 현재 기준점을 출력하도록 한다. 하지만 같은 숫자로 구성되어 있지 않다면 재귀적으로 지금 영상을 4분할로 나눠서 위의 작업을 반복해주면 된다.
주사위는 위와 같이 생겼다. 주사위의 여섯 면에는 수가 쓰여 있다. 위의 전개도를 수가 밖으로 나오게 접는다.
A, B, C, D, E, F에 쓰여 있는 수가 주어진다.
지민이는 현재 동일한 주사위를 N^3개 가지고 있다. 이 주사위를 적절히 회전시키고 쌓아서, N*N*N크기의 정육면체를 만들려고 한다. 이 정육면체는 탁자위에 있으므로, 5개의 면만 보인다.
N과 주사위에 쓰여 있는 수가 주어질 때, 보이는 5개의 면에 쓰여 있는 수의 합의 최솟값을 출력하는 프로그램을 작성하시오.
입력:
첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수는 50보다 작거나 같은 자연수이다.
출력:
첫째 줄에 문제의 정답을 출력한다.
풀이방법:
주사위를 쌓아서 N*N*N 크기의 정육면체를 만들게 되면, 밖으로 노출되는 면이 가장 많은 경우는 3개인 면인 경우이다. 정육면체에서 3개의 면 주사위의 개수, 2개의 면 주사위의 개수, 1개의 면 주사위의 개수는 N에 따라서 달라지게 된다.
1. 3개의 면 주사위의 개수는 항상 위쪽 면의 꼭짓점에서만 나타나므로 N과 상관없이 4번만 등장하게 된다.
2. 2개의 면이 나타나는 주사위의 개수는 모서리에서만 나타나게 된다. 이 때 위쪽 면에서는 꼭짓점에서 이미 사용한 주사위가 있으므로 이를 제외해주고 계산해줘야 한다. 따라서 (N-1)*4+(N-2)*4개가 존재한다.
3. 1개의 면이 나타나는 주사위는 ((N-2)^2)*5+(N-2)*4 개 있다.
주사위는 위 그림에서 나타나는 것처럼 전개도를 따라서 접게 되므로, 모든 숫자 중에서 가장 작은 3개(혹은 2개)를 골라서 최솟값을 구하면 안된다. A에 있는 숫자는 F와 만날 수 없기 때문이다. 따라서 나타날 수 있는 3개인 경우는 [(0,1,2),(0,1,3),(0,2,4),(0,3,4),(1,2,5),(1,3,5),(2,4,5),(3,4,5)]와 같기 때문에 이 중에서 가장 작은 값을 가지는 경우를 찾도록 하고, 2개인 경우는 서로 반대 면에 있는 숫자만 피하면 되므로, 이를 제외하고 계산하도록 한다.
구간 [A,B]란 A보다 크거나 같고, B보다 작거나 같은 모든 정수가 있는 구간이다. 이때, A와 B는 모두 양수이고, B는 A보다 크다.
구간 [A,B]가 Unlucky가 되기 위해선 구간에 속한 모든 정수가 Lucky Set에 없어야 한다.
Lucky Set과 N이 주어질 때, N을 포함하는 Unlucky 구간의 개수를 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 Lucky Set에 포함된 숫자의 개수 L이 주어진다. 둘째 줄에는 L개의 수가 주어진다. 이 수는 1,000보다 작거나 같은 자연수이고, L은 50보다 작거나 같은 자연수이다. 그리고 중복되지 않는다. 마지막 줄에는 N이 주어진다. N은 lucky Set에서 가장 큰 수보다 작거나 같은 자연수이다.
출력:
첫재 줄에 문제의 정답을 출력한다.
풀이방법:
N이 Lucky set의 어느 구간에 속해 있는지 파악해야 한다. 이 때, N이 lucky set의 원소일 수 있으므로 주의해서 탐색해야 한다. 반복문을 사용해서 N이 속해 있는 구간을 파악하고 왼쪽 값을 left, 오른쪽 값을 right라고 설정한다. N이 lucky set의 원소보다 다 작은 경우는 예외케이스로 판단하도록 한다.
left 와 right를 구한 뒤에는 이중반복문을 사용해서 구간을 생성하여, 이 구간 내에 N이 있는 경우에만 answer에 값을 더하도록 한다.
공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi(1 ≤ gi≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.
신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?
입력:
첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.
두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.
이후 P개의 줄에 gi(1 ≤ gi≤ G) 가 주어진다.
출력:
승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.
풀이방법:
유니온-파인드 알고리즘을 사용해서 문제를 풀려고 한다. 우선 초기 게이트들은 각자 번호로 초기화를 한다. 그리고 앞으로 들어오는 비행기를 게이트에 할당하기 시작한다. 이 때 할당하는 방법은 find()함수로 진행을 하며, 비행기의 번호에 따라 가장 큰 게이트에 도킹을 한다. 즉 gi번 비행기는 gi게이트에 할당하도록 하고, 만약 gi게이트에 이미 도킹 된 비행기가 있다면 그 전 게이트(gi-1)에 할당한다. 이렇게 계속해서 할당을 하다가 0번째 게이트를 만나게 되면 더 이상 도킹을 진행할 수 없기 때문에 공항을 폐쇄한다.
워드프로세서 등을 사용하는 도중에 찾기 기능을 이용해 본 일이 있을 것이다. 이 기능을 여러분이 실제로 구현해 보도록 하자.
두 개의 문자열 P와 T에 대해, 문자열 P가 문자열 T 중간에 몇 번, 어느 위치에서 나타나는지 알아내는 문제를 '문자열 매칭'이라고 한다. 워드프로세서의 찾기 기능은 이 문자열 매칭 문제를 풀어주는 기능이라고 할 수 있다. 이때의 P는 패턴이라고 부르고 T는 텍스트라고 부른다.
편의상 T의 길이를 n, P의 길이를 m이라고 하자. 일반적으로, n>= m 이라고 가정해도 무리가 없다. n < m이면 어차피 P는 중간에 나타날 수 없기 때문이다. 또, T의 i번째 문자를 T[i]라고 표현하도록 하자. 그러면 물론, P의 i번째 문자는 P[i]라고 표현된다.
문자열 P가 문자열 T 중간에 나타난다는 것, 즉 문자열 P가 문자열 T와 매칭을 이룬다는 것이 어떤 것인지 아래의 두 예를 통해 알아보자. 위의 예에서 P는, T의 1번 문자에서 시작하는 매칭에 실패했다. T의 7번 문자 T[7]과, P의 7번 문자 P[7]이 서로 다르기 때문이다.
그러나 아래의 예에서 P는, T의 5번 문자에서 시작하는 매칭에 성공했다. T의 5~11번 문자와 P의 1~7번 문자가 서로 하나씩 대응되기 때문이다.
가장 단순한 방법으로, 존재하는 모든 매칭을 확인한다면, 시간 복잡도가 어떻게 될까? T의 1번 문자에서 시작하는 매칭이 가능한지 알아보기 위해서, T의 1~m번 문자와 P의 1~m번 문자를 비교한다면 최대 m번의 연산이 필요하다. 이 비교들이 끝난 후, T의 2번 문자에서 시작하는 매칭이 가능한지 알아보기 위해서, T의 2~m+1번 문자와 P의 1~m번 문자를 비교한다면 다시 최대 m번의 연산이 수행된다. 매칭은 T의 n-m+1번 문자에서까지 시작할 수 있으므로, 이러한 방식으로 진행한다면 O((n-m+1)*m = O(nm)의 시간복잡도를 갖는 알고리즘이 된다.
더 좋은 방법은 없을까? 물론 있다. 위의 제시된 예에서, T[7] ≠ P[7] 이므로 T의 1번 문자에서 시작하는 매칭이 실패임을 알게 된 순간으로 돌아가자. 이때 우리는 매칭이 실패라는 사실에서, T[7] ≠ P[7] 라는 정보만을 얻은 것이 아니다. 오히려 i=1,...,6에 대해 T[i] = P[i]라고 하는 귀중한 정보를 얻지 않았는가? 이 정보를 십분 활용하면, O(n)의 시간 복잡도 내에 문자열 매칭 문제를 풀어내는 알고리즘을 설계할 수 있다.
P 내부에 존재하는 문자열의 반복에 주목하자. P에서 1, 2번 문자 A, B는 5,6번 문자로 반복되어 나타난다. 또, T의 1번 문자에서 시작하는 매칭이 7번 문자에서야 실패했으므로 T의 5,6번 문자도 A,B이다.
따라서 T의 1번 문자에서 시작하는 매칭이 실패한 이후, 그 다음으로 가능한 매칭은 T의 5번 문자에서 시작하는 매칭임을 알 수 있다! 더불어, T의 5~6번 문자는 P의 1~2번 문자와 비교하지 않아도, 서로 같다는 것을 이미 알고 있다! 그러므로 이제는 T의 7번 문자와 P의 3번 문자부터 비교해 나가면 된다.
이제 이 방법을 일반화 해 보자. T의 i번 문자에서 시작하는 매칭을 검사하던 중 T[i+j-1] ≠ P[j]임을 발견했다고 하자. 이렇게 P의 j번 문자에서 매칭이 실패한 경우, P[1…k] = P[j-k…j-1]을 만족하는 최대의 k(≠j-1)에 대해 T의 i+j-1번 문자와 P의 k+1번 문자부터 비교를 계속해 나가면 된다.
이 최대의 k를 j에 대한 함수라고 생각하고, 1～m까지의 각 j값에 대해 최대의 k를 미리 계산해 놓으면 편리할 것이다. 이를 전처리 과정이라고 부르며, O(m)에 완료할 수 있다.
이러한 원리를 이용하여, T와 P가 주어졌을 때, 문자열 매칭 문제를 해결하는 프로그램을 작성하시오.
입력:
첫째 줄에 문자열 T가, 둘째 줄에 문자열 P가 주어진다. 문자열 내에 공백이 포함되어 있을 수도 있음에 유의한다. 물론 공백도 하나의 문자로 인정된다. T와 P의 길이 n, m은 1이상 100만 이하이다.
출력:
첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 일치한다면, i를 출력하는 식이다.
풀이방법:
이 문제에 대한 설명은 KMP 알고리즘에 대한 설명이다. KMP 알고리즘은 bowbowbow.tistory.com/6이 곳에서 정말 잘 설명하고 있는 것 같다. 다음은 해당 링크의 설명을 바탕으로 작성한 코드입니다.
하지만 기억력이 좋지 못한 영재는 시상이 떠오르면 그 순간 컴퓨터로 기록해야만 안 까먹는다! 시는 대문자, 소문자 알파벳과 빈칸으로 이루어져 있따. 시상은 매번 훌륭하지만 제목 짓는 센스가 부족한 영재는 시에 나오는 단어들의 첫 글자를 대문자로 바꾼 뒤 순서대로 이어서 제목을 만든다. 만약 시의 내용이 'There is no cow level' 이라면 시의 제목은 'TINCL'이 된다.
시도 때도 없이 시를 기록하느라 낡아버린 영재의 키보드는 수명이 얼마 남지 않았다. 앞으로 스페이스 바와 영자판을 누를 수 있는 횟수가 정해져 있어 이를 초과하면 키보드가 수명이 다 하여 어떠한 작업도 하지 못하게 된다. 하나 다행인 점은, 키보드를 쓸 때 같은 문자가 연속으로 나오거나 빈칸이 연속으로 나오는 경우 영재는 자판을 꾹 눌러 한 번만 사용해서 키보드를 좀 더 효율적으로 쓸 수 있다. (A와 a는 다른 문자이므로 'Aa'는 2번의 a자판을 누른 것으로 한다.
시의 내용과 시의 제목은 Enter 키로 구분된다. 다향히 Shift 키와 Enter 키는 항상 수명이 무한한 상황이다!
음유시인 영재가 이번에 지은 시의 내용과 스페이스 바와 영자판을 누를 수 있는 횟수가 주어졌을 때, 시의 내용과 제목을 모두 기록할 수 있다면 시의 제목을 출력하고, 만약 키보드의 수명이 다 하여 기록을 완벽하게 못 하게 된다면 -1을 출력하여라.
입력:
첫 줄에 시의 내용이 주어진다.
둘째 줄에는 스페이스 바의 남은 사용 가능 횟수가 주어진다.
셋째 줄에는 대소문자를 구별하지 않고, 26개의 알파벳에 대한 영자판의 남은 사용 가능 횟수가 알파벳순으로 주어진다.
출력:
시의 내용과 제목을 모두 기록할 수 있다면 제목을 출력하여라.
만약 키보드의 수명이 다 하여 기록을 완벽하게 못 하게 되어 작업을 하지 못한다면 -1을 출력하여라.
풀이방법:
주어진 조건대로 구현을 해서 풀면 된다. 이 문제에서 고려해야 하는 조건들은 다음과 같다.
1. 시의 내용과 제목을 모두 작성할 수 있어야 한다.
2. 연속된 문자는 효율적으로 작성을 할 수 있지만 대,소문자 구분은 해야 한다.
1을 위해서 두 번 체크 하는 과정이 필요하다. 2를 위해서는 문자열을 비교하는 것은 대소문자로 비교를 하고, 남은 횟수를 줄일 때는 소문자로 바꿔서 진행하도록 한다.
하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.
- 3 : 3 (한 가지)
- 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
- 53 : 5+7+11+13+17 = 53 (두 가지)
하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.
자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 자연수 N이 주어진다. (1<=N<=4,000,000)
출력:
첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.
풀이방법:
투 포인터를 사용하는 슬라이딩 윈도우랑 소수를 구하는 알고리즘 중 하나인 에라토스테네스의 체를 사용하도록 한다.
우선 자연수 N 이하의 소수들을 에라토스테네스의 체를 이용해서 찾는다. 이 때, 소수인 값들만 남기기 위해서 set을 사용해서 소수가 아닌 것들을 제거하도록 했다.
이렇게 자연수 N 이하의 소수들이 담긴 배열을 구했으면, 이를 투 포인터를 이용한 슬라이딩 윈도우를 통해서 부분합을 구한다. 자연수 N보다 부분합이 작다면 end를 움직여서 부분합을 증가시키고, 부분합이 더 크다면 start를 줄여서 부분합을 증가시킨다.
