CodeDrive

문제:

 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림(a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 뗴면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

모든 스티커를 붙일 수 없게 된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

위의 그림의 경우에 점수가 50,50,100,60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 가장 높은 점수를 가지는 두 스티커(100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

입력:

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1<=n<=100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력:

각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

풀이 방법:

 열 단위로 끊어가면서 동적계획법을 적용하면 된다. 한 열에서 뗄 수 있는 경우의 수는 총 3가지이다.

  1 . 위, 아래 둘다 뜯지 않을 경우

  2.  위만 뜯을 경우

  3.  아래만 뜯을 경우

따라서 이 규칙대로 뜯어나가면서 최댓값을 찾아나가면 된다.

 i번째 열에서 1번의 경우로 뜯기 위해선 i-1열에는 1,2,3 모든 경우의 수가 올 수 있다. 따라서 i-1열의 값 중 최댓값을 그대로 가져오면 된다.

 i번째 열에서 2번의 경우로 뜯기 위해선 i-1열에는 1,3만 올 수 있다. 따라서 이 두 값중 최대값과 i번째 위 값을 더해주면 된다.

 i번째 열에서 3번의 경우로 뜯기 위해선 i-1열에는 1,2만 올 수 있다. 따라서 이 두 값중 최대값과 i번째 아래 값을 더해주면 된다.

이렇게 n번째 열(인덱스 상으론 n-1)까지 위와 같은 규칙으로 계속 업데이트 해준 다음에 최댓값을 찾으면 전체의 최댓값을 알 수 있게 된다.

문제 링크:

https://www.acmicpc.net/problem/9465

문제:

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으며, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

 L : 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)

 D : 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)

 B : 커서 왼쪽에 있는 문자를 삭제함(커서가 문장의 맨 앞이면 무시됨), 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처       럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임.

 P $ : $라는 문자를 커서 왼쪽에 추가함

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오.  단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

입력:

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 N(1<=N<=500,000)이 주어진다. 셋째 줄부터 N개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

출력:

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

풀이방법:

 명령어대로 구현을 하는 것은 어렵지 않은 것 같지만 시간 제한이 빡세게 걸려있기 때문에 효율적으로 구현을 하는 것이 어려운 문제인 것 같았다. 명령어를 그냥 구현하는 것은 idx , insert함수, pop함수를 사용하면 쉽게 구현할 수 있지만 시간 초과가 발생할 것 같다. insert함수, pop함수는 각각 O(n)의 시간복잡도를 가지고 있기 때문이다. (실제로 구현해보진 않았지만 아마 날 것이다.)

 그래서 넣고 빼는 것의 시간복잡도를 줄일 수 있는 자료구조가 무엇인지 생각해보니 스택과 큐가 생각났다. (이들은 넣고 뺌이 O(1)이다.) 따라서 두 개의 스택을 이용해서 이 문제를 해결하고자 하였다.

 기본적인 개념은 커서를 기준으로 왼쪽에 있는 값들의 스택, 오른쪽에 있는 값들의 스택을 만들어 두 개의 스택을 운영했다. 커서가 이동하는 것은 왼쪽스택->오른쪽스택, 오른쪽스택->왼쪽스택으로 옮기는 행위로 판단을 하였고, B는 그냥 pop, P는 append라고 생각하면 쉽게 구현 할 수 있다. '커서가 문자의 맨 앞(뒤)이면 무시됨'과 같은 말은 스택의 크기가 0임을 판단하는 것으로 해결했다.

 명령어를 다 수행하고 출력을 할 때에는 하나의 스택에 다 몰아넣고 출력해도 되지만 파이썬의 join 함수를 사용해서 한 줄로 코드를 줄일 수 있었다.

 그리고 파이썬의 경우에는 시간초과를 해결하기 위해서 입출력시에 input() 함수를 사용하지 말아야 한다고 한다. 따라서 sys 모듈에서 sys.stdin.readline().rstrip()을 사용해서 값들을 읽었다. (rstrip()은 끝에 '\n'이 붙어있다고 해서 제거하기 위함이다.)

문제 링크:

https://www.acmicpc.net/problem/1406

문제:

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A={10, 20, 10, 30, 20, 50}이고, 길이는 4이다.

입력:

첫째 줄에 수열 A의 크기(1<=N<=1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1<=Ai<=1,000)

출력:

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

풀이 방법:

배열을 하나씩 커지게 만들어 가면서 증가하는 부분 수열을 찾도록 한다. 가장 큰 값을 빠르게 찾기 위해서 뒤에서 부터 값을 탐색하도록 하게 한다.

https://www.acmicpc.net/problem/11053

문제:

케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람의 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?

천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Backjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.

케빈 베이컨은 미국 헐리우드 영화배우들끼리 케빈 베이컨 게임을 했을 때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.

오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 적은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.

1은 2까지 3을 토해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+1+2 = 6 이다.

2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다.

3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4를 통해 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 1+1+1+2 =5 이다.

4는 1까지 1단계, 2까지 3을 통해 2단계, 3까지 1단계, 5까지 1단계 만에 알 수 있다. 4의 케빈 베이컨의 수는 1+2+1+1 = 5가 된다.

마지막으로 5는 1까지 4를 통해 2단계, 2까지 4와 3을 통해 3단계, 3까지 4를 통해 2단계, 4까지 1단계 만에 알 수 있다. 5의 케빈 베이컨의 수는 2+3+2+1 = 8이다.

5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다.

BOJ 유저의 수와 친구 관계 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 유저의 수 N(2<=N<=100)과 친구 관계의 수 M(1<=M<=5,000)이 주어진다. 둘째 줄부터 M

개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다.

출력:

첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 적은 사람을 출력한다. 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다.

풀이방법:

일단 모든 사람들에 대해서 케빈 베이컨의 수를 계산해야 하므로 BFS로 값을 탐색해야 한다고 생각했다.  for를 사용한 반복문은 입력값을 정리하기 위한 반복문이다. (보통 저는 bfs, dfs는 이와 같이 입력값들을 정리합니다.) answer는 각 사람 별로 count의 값을 담아주는 배열이고, 인덱스를 편리하기 관리하기 위해 1번 사람이 1번째 인덱스를 가지도록 하였다. person은 인덱스 값으로 교체해줘도 괜찮을 것 같지만 bfs 내에서 한 단계 이상 넘어간다면 여러 개의 값을 가져야 할 것 같아서 애초에 배열 값으로 넣게 되었다. 그리고 또한 자기 자신의 값을 탐색하지 않도록 자신의 값은 -1로 초기화 한 상태로 값을 넣었다.

문제링크:

https://www.acmicpc.net/problem/1389

문제:

개미 여러 마리가 길이가 lcm인 막대 위에 있다. 각 개미의 이동 속도는 모두 일정하며, 1cm/s이다. 개미가 막대의 마지막까지 걸어간다면, 개미는 그 즉시 떨어지게 된다. 또, 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다.

가장 처음에 막대 상에서 개미의 위치를 알고 있다. 하지만, 개미가 어느 방향으로 움직이는지는 알 수가 없다. 이때, 모든 개미가 땅으로 떨어질 때까지 가능한 시간 중 가장 빠른 시간과 느린 시간을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 막대의 길이와 개미의 수 n이 주어진다. 다음 n개 줄에는 숫자가 하나씩 주어지며, 이 숫자는 개미의 초기 위치를 나타낸다. 입력으로 주어지는 모든 수는 1,000,000보다 작거나 같으며, 공백으로 구분되어 있다.

출력:

각 테스트 케이스에 대해서, 두 숫자를 출력한다. 첫번째 숫자는 개미가 모두 땅으로 떨어지는 가능한 시간 중 가장 빠른 시간, 두 번째 숫자는 가장 늦은 시간이다.

풀이 방법:

  문제가 엄청 어려워 보이지만 "또, 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다. " 이 문장이 함정이라는 것을 알면 어렵지 않게 된다. 실제로 예제 입력에 대해서 계속해서 부딪히게 만들어보았더니 개미가 먼 방향으로 걸어가서 떨어지는 것과 같은 값을 얻는다는 것을 알 수 있었다. (정확한 이유는 모르겠다.)

 따라서 가장 빠른 시간은 각자 개미들이 자신이 위치에서 막대가 짧은 쪽으로 이동하도록 하고, 가장 느린 시간은 개미들이 막대가 긴 쪽으로 이동하도록 한다면 값을 구할 수 있다. 배열에 넣어서 각 값을 구하도록 했더니 시간 초과가 발생해서 각 개미마다 비교해서 최솟값, 최댓값을 구하도록해서 시간을 줄이도록 했다.

문제 링크:

https://www.acmicpc.net/problem/1309

문제:

어떤 동물원에 가로로 두 칸 세로로 N칸인 아래와 같은 우리가 있다.

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 불어 있게 배치할 수는 없다.

이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

입력:

첫째 줄에 우리의 크기 N(1<=N<=100,000)이 주어진다.

출력:

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

풀이 방법:

 dp문제인데 N마다 생성되는 규칙을 찾아내거나 아니면 점화식을 찾으면 된다. 따라서 찾은 점화식은 다음과 같다. 

an = a(n-1) + 2*a(n-2)

따라서 이 규칙에 따라서 값을 구해주면 된다.

문제 링크:

https://www.acmicpc.net/problem/1309

문제:

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 숫자를 버린느 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0<=n<=100,000)

다음 줄에는 [x1,...., xn]과 같은 형태로 배열에 들어 있는 수가 주어진다. (1 <=xi <=100)

전 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

출력:

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

풀이 방법:

 명령어를 수행하는 것은 별로 어렵진 않았지만, 이를 위해 사전에 입력값을 전처리하고, 다시 이를 패키징 하는 것이 귀찮았다. 입력이 [1,2,3,4]와 같이 들어오게 되는데 리스트로 들어온다는 것이 아니라, 리스트처럼 생긴 스트링으로 들어오는 것이다. 따라서 이를 구분해서 배열에 담아야 한다. 명령어를 수행하는 것은 비교적 간단하다.

 처음에는 R이 들어오면 reverse를 D가 들어오면 pop(0)을 하는 방식으로 진행했더니 시간 초과가 발생하게 되었다. reverse를 하는 연산의 시간이 크다고 해서 이를 줄이기 위해서 마지막에 딱 한 번만 하는 방식으로 바꾸게 되었다.

RR이 두 번 들어온다면 두 번 뒤집는 것이기 때문에 결국 다시 처음 배열로 돌아오는 것과 같다. 즉 R이 짝수 번 들어온다면 뒤집을 필요가 없는 것이다. D는 R이 몇 번 나왔는지에 따라 빼는 위치만 달라지게 하면 된다. R이 한 번 나와 뒤집어져 있는 상태라면 맨 앞이 아닌 맨 뒤를 빼야 정상적으로 D의 명령어가 수행되는 것이다. 따라서 이를 구분하기 위해서 ReverseCount를 만들었으며, 비정상적인 명령어를 구분하기 위해서 예외처리 구문과 Error 변수를 만들었다.

문제 링크:

https://www.acmicpc.net/problem/5430

문제:

양의 정수 N이 주어졌을 때, 이 수를 소인수분해 한 결과를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2<=N<=100,000)이 주어진다.

출력:

각 테스트 케이스마다 각 인수와 그 인수가 곱해진 횟수를 한 줄씩 출력한다. 출력 순서는 인수가 증가하는 순으로 한다.

풀이 방법:

소인수분해는 말 그대로 소수로만 분해가 된다. 따라서 2부터 시작해서 n이 1이 될 때까지 소수로 나눠주면 된다. 소수인지 따로 판별이 필요하지 않다.(이전에서 이미 다 나눠버렸기 때문에) 따라서 각 count별로 answer를 계산하고 더 이상 나눠주지 못한다면 초기화를 하고 다음으로 넘어가면 된다.

문제 링크:

https://www.acmicpc.net/problem/2312

문제:

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력:

첫째 줄에 자연수 N과 M이 주어진다. (1<= M <= N < 8)

출력:

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이 방법:

재귀적인 방법으로 길이가 M이 될 때까지 계속해서 넣어준다. 대신 이 문제에서는 중복을 허용하지 않았기 때문에 이에 대한 조건도 있어야 하고 증가하는 순서로 출력해야 하므로 배열에 들어있는 끝 값보다 클 때만 넣어줘야 한다는 조건 역시 필요하다. 이 문제에 대한 시리즈가 여러개 있는데 이에 맞는 조건을 넣어주면 된다.

문제 링크:

https://www.acmicpc.net/problem/15649

문제:

 재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.

 1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 데이터, ....,

 10번 데이터틑 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번데이터는 2번 컴퓨터, ...

총 데이터의 개수는 항상 a^b개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.

입력:

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1<=a<100, 1<=b<1,000,000)

출력:

각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 출력한다.

풀이 방법:

 a^b 꼴, 즉 제곱수 형태로 주어지기 때문에 일정한 규칙이 있게 된다. 계속 곱하다 보면 일의 자리가 반복됨을 알 수 있다.

1 -> 1 -> ...

2 -> 4 -> 8 -> 6 -> 2 -> ...

3 -> 9 -> 7-> 1 -> 3 ->...

4 -> 6 -> 4 -> ...

5 -> 5 -> ....

6 -> 6 -> ...

7 -> 9 -> 3 -> 1 -> 7 -> ....

8 -> 4 -> 2 -> 6 -> 8 -> ....

9 -> 1 -> 9 -> ....

10 -> 10 -> ... (원래는 0이겠지만 문제상에서는 10이다.)

따라서 a에 맞는 규칙 배열을 만들어 준 뒤에 b에 맞는 인덱스를 찾아 반환해주면 된다.

문제 링크:

https://www.acmicpc.net/problem/1009