CodeDrive

문제:

찬솔이는 블로그를 시작한 지 벌써 N일이 지났다.

요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.

찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.

찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자.

입력:

첫째 줄에 블로그를 시작하고 지난 일수 N와 X가 공백으로 구분되어 주어진다.

둘째 줄에는 블로그 시작 1일차부터 N일차까지 하루 방문자 수가 공백으로 구분되어 주어진다.

출력:

첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다.

만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다.

풀이방법:

X만큼의 구간을 슬라이딩 하면서 최댓값을 갱신하고, 최댓값이랑 같은 경우에는 기간을 증가시켜준다.

문제링크:

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

문제:

풀이방법:

우선 한쪽으로 케이크의 모든 토핑을 모아두고, 하나씩 반대로 옮기면서 갯수가 같아지는 지점을 체크하도록 한다.

 이 과정을 편하게 하기 위해 dict 자료형을 선택했고, collections의 defaultdict을 사용했다. defaultdict은 dict의 key 초기화 과정이 필요하지 않다는 장점이 존재한다.

 따라서 하나씩 토핑을 제거하고, 제거한 토핑은 반대 dict의 넘겨준다. 만약 value가 0이 된다면 key를 제거한다. 이렇게 했을 때, 두 dict의 key의 길이가 같다면 공평하게 자르는 방법이라고 생각한다.

문제링크:

https://school.programmers.co.kr/learn/courses/30/lessons/132265

문제:

IQ Test의 문제 중에는 공통된 패턴을 찾는 문제가 있다. 수열이 주어졌을 때, 다음 수를 찾는 문제이다.

예를 들어, 1, 2, 3, 4, 5가 주어졌다. 다음 수는 무엇인가? 당연히 답은 6이다. 약간 더 어려운 문제를 보면, 3, 6, 12, 24, 48이 주어졌을 때, 다음 수는 무엇인가? 역시 답은 96이다.

이제 제일 어려운 문제를 보자.

1, 4, 13, 40이 주어졌을 때, 다음 수는 무엇일까? 답은 121이다. 그 이유는 항상 다음 수는 앞 수*3+1이기 때문이다.

은진이는 위의 3문제를 모두 풀지 못했으므로, 자동으로 풀어주는 프로그램을 작성하기로 했다. 항상 모든 답은 구하는 규칙은 앞 수*a + b이다. 그리고, a와 b는 정수이다.

수 N개가 주어졌을 때, 규칙에 맞는 다음 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 N개의 수가 주어진다. 이 수는 모두 절댓값이 100보다 작거나 같은 정수이다.

출력:

다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다.

풀이방법:

문제에서 찾아야 하는 a와 b를 찾는 것은 연립방정식을 사용한다면 쉽게 찾을 수 있다. 하지만 A, B와 같이 특이 케이스들이 다수 존재하기 때문에 이를 위한 노력이 필요하다. 다음과 같은 케이스들이 존재할 수 있다.

1. N이 1인 경우

N이 1인 경우에는 a와 b를 알 수 없기 때문에 다음에 여러 수가 존재할 수 있다. -> A

2. N이 2인 경우

N이 2인 경우에도 a와 b를 알 수 없기 때문에 여러 수가 존재할 수 있다.(A) 하지만 첫 두 수가 같다면 a=1, b=0인 특수한 케이스에 해당하기에 마지막 수를 출력한다.

3. N이 3 이상인 경우

 N이 3 이상이면 연립방정식을 통해 a와 b를 구할 수 있게 된다. 따라서 첫 세 수를 사용하여 a와 b를 구하도록 한다. 이 때, a와 b를 정수라는 조건이 있기 때문에 소수가 구해지게 된다면 B를 출력하도록 한다.

 a와 b를 정상적으로 구해도 첫 세 수를 통해 구한 값이기 때문에 이 규칙이 주어진 배열 끝까지 동작하는지 확인하는 작업이 필요하다. 규칙이 정상적으로 작동한다면 규칙을 사용하여 다음 수를 출력하고, 그렇지 않다면 B를 출력한다.

문제링크:

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

문제:

대한민국을 비롯한 대부분의 나라에서는 터널 내에서의 차선 변경을 법률로 금하고 있다. 조금만 관찰력이 있는 학생이라면 터널 내부에서는 차선이 파선이 아닌 실선으로 되어 있다는 것을 알고 있을 것이다. 이는 차선을 변경할 수 없음을 말하는 것이고, 따라서 터널 내부에서의 추월은 불가능하다.

소문난 명콤비 경찰 대근이와 영식이가 추월하는 차량을 잡기 위해 한 터널에 투입되었다. 대근이는 터널의 입구에, 영식이는 터널의 출구에 각각 잠복하고, 대근이는 차가 터널에 들어가는 순서대로, 영식이는 차가 터널에서 나오는 순서대로 각각 차량 번호를 적어 두었다.

N개의 차량이 지나간 후, 대근이와 영식이는 자신들이 적어 둔 차량 번호의 목록을 보고, 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차들이 몇 대 있다는 것을 알게 되었다. 대근이와 영식이를 도와 이를 구하는 프로그램을 작성해 보자.

입력:

입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이가 적은 차량 번호 목록이 주어진다. 각 차량 번호는 6글자 이상 8글자 이하의 문자열로, 영어 대문자('A'-'Z')와 숫자('0'-'9')로만 이루어져 있다.

같은 차량 번호가 두 번 이상 주어지는 경우는 없다.

출력:

첫째 줄에 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차가 몇 대인지 출력한다.

풀이방법:

먼저 들어간 차량부터 1이라고 라벨링을 할 때, 추월한 차량의 뒤 차량들 중에는 본인 차의 숫자보다 작은 숫자가 반드시 존재하게 된다. 따라서 이러한 경우를 추월한 차량이라고 생각하고 갯수를 세도록 한다.

문제링크:

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

문제:

풀이방법:

y를 만드는 것이 목적이므로 y 길이를 가지고 있는 DP 배열을 만들어서 연산을 수행하도록 한다.

DP에 연산을 하면서 연산 횟수를 채워나가면 되는데, 최소 연산 횟수를 구해야 하므로 min 연산을 추가로 하도록 한다. 즉, 특정 숫자 x에 접근할 수 있는 방법은 여러가지가 있을텐데 그 중 가장 작은 횟수만 선택하는 것이다.

문제링크:

https://school.programmers.co.kr/learn/courses/30/lessons/154538

문제:

인터넷 방송 KOI(Korea Open Internet)의 음악 프로그램 PD인 남일이는 자기가 맡은 프로그램 '뮤직 KOI'에서 가수의 출연 순서를 정하는 일을 매우 골치 아파한다. 순서를 정하기 위해서는 많은 조건을 따져야 한다.

그래서 오늘 출연 예정인 여섯 팀의 가수에 대해서 남일이가 보조 PD 세 명에게 각자 담당한 가수의 출연 순서를 정해오게 하였다. 보조 PD들이 가져온 것은 아래와 같다.

• 1 4 3
• 6 2 5 4
• 2 3

첫 번째 보조 PD는 1번 가수가 먼저, 다음에 4번 가수, 다음에 3번 가수가 출연하기로 순서를 정했다. 두 번째 보조 PD는 6번, 2번, 5번, 4번 순으로 자기 담당 가수들의 순서를 정했다. 한 가수를 여러 보조 PD가 담당할 수도 있다. 마지막으로, 세 번째 보조 PD는 2번 먼저, 다음에 3번으로 정했다.

남일이가 할 일은 이 순서들을 모아서 전체 가수의 순서를 정하는 것이다. 남일이는 잠시 생각을 하더니 6 2 1 5 4 3으로 순서를 정했다. 이렇게 가수 순서를 정하면 세 보조 PD가 정해온 순서를 모두 만족한다. 물론, 1 6 2 5 4 3으로 전체 순서를 정해도 괜찮다.

경우에 따라서 남일이가 모두를 만족하는 순서를 정하는 것이 불가능할 수도 있다. 예를 들어, 세 번째 보조 PD가 순서를 2 3 대신에 3 2로 정해오면 남일이가 전체 순서를 정하는 것이 불가능하다. 이번에 남일이는 우리 나라의 월드컵 4강 진출 기념 음악제의 PD를 맡게 되었는데, 출연 가수가 아주 많다. 이제 여러분이 해야 할 일은 보조 PD들이 가져 온 순서들을 보고 남일이가 가수 출연 순서를 정할 수 있도록 도와 주는 일이다.

보조 PD들이 만든 순서들이 입력으로 주어질 때, 전체 가수의 순서를 정하는 프로그램을 작성하시오.

입력:

첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 가수의 수가 나오고, 그 뒤로는 그 가수들의 순서가 나온다. N은 1이상 1,000이하의 정수이고, M은 1이상 100이하의 정수이다.

출력:

출력은 N 개의 줄로 이뤄지며, 한 줄에 하나의 번호를 출력한 다. 이들은 남일이가 정한 가수들의 출연 순서를 나타낸다. 답이 여럿일 경우에는 아무거나 하나를 출력 한다. 만약 남일이가 순서를 정하는 것이 불가능할 경우에는 첫째 줄에 0을 출력한다.

풀이방법:

 순서가 정해져있는 작업을 차례로 수행해야 할 때 순서를 결정해주는 문제이므로 '위상 정렬'을 사용해야 한다. 위상 정렬에 대한 설명은 다음 페이지에 설명이 잘 되어 있기에 링크를 달아두도록 한다.

https://m.blog.naver.com/ndb796/221236874984

 문제의 설명에서 '세 번째 보조 PD가 순서를 2 3 대신에 3 2로 정해오면 남일이가 전체 순서를 정하는 것이 불가능하다.' 라는 것이 있는데, 이는 위상 정렬을 수행할 때 사이클이 생기는 경우에 해당한다. 이러한 경우에 위상정렬을 하면서 순서를 정할 때, N명이 모두 순서가 정해지지 않게 된다.

 따라서 위상정렬을 하고 난 뒤에 길이가 N이 아니라면 -1을 출력하도록 한다.

문제링크:

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

문제:

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다.

출력:

첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

풀이방법:

X인 부분을 그리디하게 채워나가도록 한다. X가 4개이상이라면 AAAA로 채우고, 4개 미만이라면 BB로 채우도록 한다. 이 때, X가 남은 경우 혹은 X가 부족한 경우가 덮을 수 없는 케이스라고 판단한다.

문제링크:

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

문제:

NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.

시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.

시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과 열의 위치를 의미하며, 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당한다.

예를 들어 다음과 같이 3x3 크기의 시험관이 있다고 하자. 서로 다른 1번, 2번, 3번 바이러스가 각각 (1,1), (1,3), (3,1)에 위치해 있다. 이 때 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류를 계산해보자.

1초가 지난 후에 시험관의 상태는 다음과 같다.

2초가 지난 후에 시험관의 상태는 다음과 같다.

결과적으로 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류는 3번 바이러스다. 따라서 3을 출력하면 정답이다.

입력:

첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분되어 주어진다. 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어진다. 또한 모든 바이러스의 번호는 K이하의 자연수로만 주어진다. N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)

출력:

S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력한다. 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.

풀이방법:

 바이러스 번호가 낮은 것부터 2차원 배열에 확산시키는 문제로 너비 우선 탐색에 해당한다. 처음에는 시간을 고려하지 않고, 너비 우선 탐색만 생각하고 문제를 풀려고 했으나 계속해서 시간초과가 발생하게 되었다.

 처음 생각했던 방법은 중복으로 탐색하는 경우도 많았으며, 이미 다 채워져 있었는데 시간(S)이 남았다는 이유로 계속 2차원 배열 탐색을 계속했기 때문에 시간초과가 발생했던 것으로 보인다. 

 그래서 deque에 바이러스 종류, 시간, 좌표등을 모두 저장하고 이를 기준으로 바이러스를 증식시키는 것으로 수정하게 되었다. 초기 시험관을 받고 바이러스 정보를 모두 deque에 넣고 정렬하면 낮은 종류의 바이러스부터 먼저 증식시킬 수 있다.

문제링크:

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

문제:

풀이방법:

처음에 문제를 이해하는 것이 가장 어려웠던 것 같다. 다음과 같은 흐름으로 문제를 이해하면 도움이 될 것 같다.

• 택배 상자는 무조건 [1,2,3,4, ... ] 와 같은 순서로 주어진다.
  • 택배 기사님의 순서와는 무관하다.
• 문제의 설명을 보면 Stack을 사용해야 한다. 이 때, 컨테이너 벨트(main), 보조 컨테이너 벨트(sub) 모두 stack으로 이루어진 배열이다.
  • 단, 컨테이너 벨트에는 [1,2,3,4, ...]가 이미 적재되어 있다.
• main에서 sub로 이동하는 것은 가능하지만, sub에서 main으로 이동하는 것은 불가능하다.

결국 2개의 stack 배열을 사용해서 택배 기사님의 순서를 맞추는 문제라고 생각하면 된다.

 main에서 sub로만 이동하는 것이 가능하기 때문에 main 혹은 sub의 out 상자가 첫 택배 기사님의 순서에 맞게 세팅을 해둔다. 택배 기사님이 원하는 택배 상자를 적재 하고 main이나 sub에 또 원하는 상자가 있다면 연속해서 적재하며 만약 그렇지 않다면 main에서 sub로 이동시키며 조건을 만족하는지 계속해서 확인한다.

 이 과정을 main의 모든 택배 상자가 비었으며, 더 이상 적재하지 못할 때까지 반복한다.

문제링크:

https://school.programmers.co.kr/learn/courses/30/lessons/131704

문제:

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.

어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. i는 0부터 시작한다.

출력:

첫째 줄에 줄을 선 순서대로 키를 출력한다.

풀이방법:

 이 문제는 그리디하게 채워나가는 것을 목표로 한다. 우선 N과 같은 길이의 0으로 채워진 배열(answers)을 생성한 후 다음과 같은 조건으로 채워나간다.

1. 현재 answers 인덱스에 이미 사람이 채워져 있는가?
2. 만약 비어있다면, 내가 들어갈 차례인가?
   1. 비어있던(answers가 0) 횟수가 내 순서와 같은가?

 즉, answers가 0인 경우에 자기보다 큰 사람이 들어갈 자리라고 생각하며, 이 자리를 미리 고려하면서 빈 자리에 들어가는 것을 선택한다.

문제링크:

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