CodeDrive

문제:

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 불어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표가 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

입력:

첫째 줄에 N(1<=N<=100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0,1,2,3,4,5,6,7,8,9 중의 하나가 된다.

출력:

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

풀이방법:

 가로의 길이가 세 개로 고정되어 있기 때문에 그림의 세 조건에서 파란 동그라미에 해당하는 부분들에서 값을 가져와서 최댓값과 최솟값을 계산하면 된다.

 하지만 이 문제에는 메모리 제한이 걸려 있었는데, N이 최대 100,000까지 존재하기 때문에 초기에 이 배열을 모두 초기화하고 더해나가면 메모리 초과가 발생하게 된다. 따라서 처음부터 N만큼의 배열을 초기화하지 않고, 한 줄씩 입력 받으며 최댓값과 최솟값을 바꾸어 나가도록 한다.

0번째 인덱스에서는 이전 행의 0번째와 1번째 값에만 영향을 받으며,

1번째 인덱스는 이전 행 전체에서,

2번째 인덱스는 이전 행의 1번째와 2번째 값에만 영향을 받는다.

max와 min을 사용해 각 칸을 tuple 형식으로 업데이트 했다. (max값, min값) 그리고 마지막에서는 max와 min의 key 옵션을 활용해서 전체 최대 점수와 최소 점수를 구하도록 했다.

문제링크:

www.acmicpc.net/problem/2096

문제:

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다. N=3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1,2,3
• 1,3,2
• 2,1,3
• 2,3,1
• 3,1,2
• 3,2,1

입력:

첫째 줄에 N(1<=N<=10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력:

첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.

풀이방법:

C++에서는 next_permutation을 사용하면 쉽게 풀 수 있지만 python에는 이 알고리즘을 구현해서 풀면 된다.

next_permutation은 다음과 같은 알고리즘을 통해서 구한다.

1 4 3 2를 예시로 알고리즘을 알아본다.

1. 뒤에서부터 순열을 비교하며, 뒷 값이 앞 값보다 큰 경우까지 반복한다. (3,2), (4,3)은 해당하지 않고, (1,4)가 해당된다. 
   1. 이 때, 1의 인덱스를 x라고 칭한다.
   2. 4의 인덱스는 y라고 한다.
2. 다시 뒤에서부터 값을 비교하며 인덱스 x보다 큰 값이 있으면 그 값과 swap한다.
   1. 1과 2를 비교했고, 2가 크기 때문에 이 둘을 swap한다.
3. y에 해당하는 인덱스부터 sort를 한 뒤에 이어 붙인다.
   1. 4 3 1을 sort해서 1 3 4가 된다.
   2. 이어 붙이기 때문에 2 1 3 4가 된다.

문제링크:

www.acmicpc.net/problem/10972

문제:

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력:

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력:

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

풀이방법:

LCS(Longest Common Subsequence)는 여러 개의 수열 모두의 부분수열이 되는 수열들 중 가장 긴 것을 찾는 문제다. 만약 이 문제를 가능한 모든 경우를 비교해본다면 엄청 큰 시간복잡도를 가지게 될 것이다. 따라서 이를 DP를 사용해서 시간복잡도를 줄이도록 한다.

문자열 ACAYKP와 CAPCAK를 테이블로 추적하며 LCS 함수의 정의를 알아본다. 

1. 우선 부분수열이 비어있는 경우도 존재할 수 있기 때문에 각 문자열에 0번째 인덱스를 추가한다. (0ACAYKP, 0CAPCAK)

그 후 문자열들의 크기(len(string1) x len(string2))만큼의 0행렬을 초기화한다.

2. 세로축의 문자열이 C라고 고정하고, 가로축의 문자열을 하나씩 증가하면서 부분수열을 찾는다.

(C와 A 중 LCS 값, C와 AC 중 LCS 값, C와 ACA 중 LCS 값, ....)

그러면 표는 아래와 같이 값이 구해지게 될 것이다.

이제 세로축의 문자열을 하나씩 늘리고, LCS 함수의 규칙에 따라 진행을 하면 다음과 같이 표들을 얻을 수 있다.

• LCS(CA,ACAYKP)

• LCS(CAP,ACAYKP)

위 표들은 다음 2가지 케이스에 대해서 업데이트 되는 것을 알 수 있다.

1. 두 부분 수열들이 같은 원소로 끝나는 경우
   1. LCS(CAP,ACAYKP)중 CAP과 ACAYKP를 비교할 때가 이 경우의 예시다. 이 때 맨 마지막 P가 일치한다. 이러한 경우에는 두 부분수열에서 P를 제거한다. 그러면 연산해야 하는 LCS는 다음 두 부분수열이다. (CA, ACAYK)
   2. 이 부분수열의 LCS는 CA임을 이전 행들에서 알 수 있다.
   3. 삭제했던 부분수열 P를 다시 붙이면 CAP이 되고, 이것이 CAP과 ACAYKP의 LCS다.
   4. 이를 LCS의 길이를 구하는 표에서 보면 왼쪽 위 값에 1을 더한것과 같다.
      1. if str1[i]==str2[j], then LCS[i][j]=LCS[i][j]+1와 같다.
2. 두 부분 수열들이 같은 원소로 끝나지 않는 경우
   1. LCS(CAP,ACAYKP)중 CAP과 ACA를 비교하는 경우다. 이 때는 각 부분수열들의 맨 끝 문자를 제거한 뒤에 둘 중 큰 LCS를 택하면 된다.
   2. 즉, max(LCS(CA,ACA), LCS(CAP,AC))와 같다.
      1. 따라서 LCS(CA,ACA)는 CA이므로 LCS(CAP,ACA)는 CA가 된다.

따라서 이 규칙들에 따라서 끝까지 진행하면 다음과 같다.

따라서 LCS의 길이만 구하고 싶다면 4가 답이 된다.

만약 subsequence 문자열을 알고 싶다면 각 행을 역추적하면서 가장 큰 숫자가 시작 된 곳을 체크한다.(값이 일치하면서 +1 된 곳이기 때문이다.)

따라서 ACAK가 LCS임을 알 수 있다.

문제링크:

www.acmicpc.net/problem/9251

문제:

크기가 N인 수열 A=A1,A2,...,AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3,5,2,7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력:

첫째 줄에 수열 A의 크기 N (1<=N<=1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1,A2,...,AN(1<=Ai<=1,000,000)이 주어진다.

출력:

총 N개의 수 NGE(1), NGE(2),... ,NGE(N)을 공백으로 구분해 출력한다.

풀이방법:

for를 두 번 사용해서 문제를 풀 수 있지만 O(n^2) 시간복잡도로 인해서 시간초과가 발생한다. 따라서 효율적인 방법인 스택을 사용해야 한다.

이와 비슷한 문제들은 수열의 값들을 저장하면서 진행을 하지만, 이 문제는 독특하게 인덱스를 저장하면서 진행한다.

조건에 맞는 오큰수가 없다면 -1을 넣어주어야 하므로, 애초에 크기가 len(A)이고, 값이 -1인 answer 배열을 만들어 준다.

이후에는 배열을 한번 순회할 때, idx의 마지막(top)에 해당하는 값과 반복문의 인덱스값과 비교하고, 이 때, 반복문의 인덱스값이 크다면 idx의 top에 해당하는 값을 인덱스로 해서 answer의 값(answer[idx.pop()])을 반복문의 인덱스(i) 값(A[i])으로 바꿔주도록 한다. 그리고 이는 while로 반복된다.

while이 끝나면 지금 반복문 인덱스를 idx에 넣어준다.

www.acmicpc.net/problem/17298

문제:

윤영이는 3의 배수 마니아이다. 그는 모든 자연수를 3개의 3의 배수의 자연수로 분해하는 것을 취미로 가지고 있다. 문득 그는 자신에게 주어진 수를 3개의 3의 배수로 분리하는 경우의 수가 몇 개인지 궁금해졌다. 하지만 윤영이는 마지막 학기이기 때문에 이런 계산을 하기에는 너무 게을러졌다. 그래서 당신에게 이 계산을 부탁했다.

즉, 임의의 3의 배수 자연수 n이 주어졌을 때, 해당 수를 3의 배수의 자연수 3개로 분리하는 방법의 개수를 출력해라. 단, 분해한 수의 순서가 다르면 다른 방법으로 간주한다. 예를 들어 12 = 3+6+3과 12=3+3+6은 다른 방법이다.

입력:

임의의 3의 배수 자연수 n이 주어진다. (3<=n<=3000)

출력:

자연수 n을 분해하는 방법의 개수를 출력하라.

풀이방법:

고등학교 수학이 생각나는 문제다. 이 문제를 변수로 나타내면 x+y+z = n (x,y,z,n은 3의 배수) 와 같고, 이는 조합 문제와 동일하다.

1. 간결하게 표현하기 위해 모든 수가 3의 배수이므로 3으로 나눠준다. (x'+y'+z' = n//3, x',y',z'>=0)

2. 3의 배수의 자연수로 분해를 해야 하기 때문에 좌변에 3을 빼줌으로써 해결한다. (x''+y''+z'' = n//3-3, x''+y''+z''>=1), 이는 nHr을 계산하는 문제와 같아진다.(3Hn//3-3)

따라서 이를 계산하면 답을 구할 수 있다.

문제링크:

www.acmicpc.net/problem/16561

문제:

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력:

첫째 줄에 수의 개수 N(1<=N<=10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력:

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

풀이방법:

숫자가 10,000까지만 있다는 점에서 count를 하는 방식으로 정렬을 한다. 10,000 크기의 배열은 만든 뒤에 들어오는 숫자대로 해당하는 인덱스의 값을 늘려줬다. 이를 마친 뒤에 앞 인덱스부터 출력했다.

문제링크:

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

문제:

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1<=N<=1,000, 0<=M<=Nx(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1<=u,v<=N, u!=v) 같은 간선은 한 번만 주어진다.

출력:

첫째 줄에 연결 요소의 개수를 출력한다.

풀이방법:

인접리스트와 dfs를 사용해서 이 문제를 사용했다. N, M을 입력받은 뒤에 인접리스트 U를 초기화하고, visited 배열을 초기화 했다. 방문하지 않은 정점에 대해서만 dfs를 수행해서 연결 요소의 개수를 구했다. 

문제링크:

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

문제:

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력:

첫째 줄에 n(1<=n<=1,000,000), m(1<=m<=100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과 b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

출력:

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no를 출력해도 된다.)

풀이방법:

 단순해 보이지만 정답 비율이 낮았기에 효율적으로 풀어야 하는 것이 중요할 것 같았다. 그리고 알아보니 이 문제는 Union-Find를 사용해서 풀어야 하는 문제였다.

 우선 parents 초기화 함으로써 해당 인덱스의 값이 각 집합을 이루고 있다고 가정했다. union은 합치는 명령을, find는 해당 집합에서 parent를 찾도록 하는 연산으로 정의했다.

이 문제는 다음과 같은 기준으로 해결된다.

1. 초기에는 각 집합이 하나의 값으로 집합을 이루고 있고, 이를 각각 parent라고 정의한다.

2. union 연산이 0 a b와 같이 들어온다면 b의 parent를 a의 parent에 연결한다.(혹은 가리킨다.)

3. find는 parents에서 인덱스를 조회했을 때, 입력 값과 같다면 parent이기 때문에 이를 바로 return해주고(이는 처음 parents의 정의이다.), 그렇지 않다면 find를 재귀적으로 사용해서 입력의 값의 parent를 찾도록 한다.

4. check는 1 a b와 같이 들어왔을 때, a와 b를 각각 find 연산을 사용해서 parent가 같은지 확인한다. (같으면 True, 다르면 Faslse)

문제링크:

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

문제:

인체에 치명적인 바이러스르 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 NxM인 직사각형으로 나타낼 수 있으며, 직사각형은 1x1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3<=N,M<=8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력:

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

풀이방법:

벽을 3개 세우는 방법을 한 눈에 찾는 것은 어렵기 때문에 가능한 모든 경우의 수에 대해 벽을 세워보면서 안전 영역 크기가 최대인 경우를 찾아야 한다. 

input을 모두 받은 뒤에 지도를 한번 탐색해서 0인 점인 빈 칸과, 2인 바이러스가 담겨 있는 배열을 만든다. 그리고 itertools의 combinations를 사용해서 지도에서 빈 칸을 3개를 고르는 모든 경우의 수를 구하고, 0인 점의 배열의 길이를 safeArea라고 정의한다.(안전 영역 계산을 빠르게 하기 위함이다.)

combinations의 각 경우에 대해서 bfs(spreadVirus)를 수행한다. 처음 바이러스가 담겨 있는 배열을 queue로 생각하며 이를 하나씩 빼면서 상하좌우로 이동하는 것으로 생각하며, 바이러스가 이동했다면 이를 다시 배열에 담아서 이 배열의 크기가 0이 될 때까지 반복하도록 했다. 그리고 이 때마다 spreadCount를 하나씩 증가하면서 처음 0인 칸에서 얼마나 바이러스가 펴졌는지 체크하도록 한다.

그리고 최종적으로는 safeArea-spreadCount-3으로 안전영역의 크기를 구한다.(-3은 0에다가 벽을 3개 세웠기 때문이다.)

이렇게 모든 경우의 수에 대해 탐색을 하면서 maxVal을 업데이트해 최댓값을 구하도록 한다.

문제링크:

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

문제:

도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.

지금 도영이의 앞에는 재료가 N개 있다. 도영이의 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.

시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이의 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.

재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.

입력:

첫째 줄에 재료의 개수 N(1<=N<=10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다.

출력:

첫째 줄에 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력한다.

풀이방법:

각 재료에 따라서 넣고 빼고 하는 작업을 재귀로 구현을 했다. mix라는 함수를 재귀적으로 호출하고, sour와 bitter의 배열의 크기를 줄여나가면서 재귀를 진행한다. 이 배열의 길이가 0이 될 때까지 반복하며, 결과값을 global 변수인 answer에 모두 담고, min 값을 출력한다.

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