CodeDrive

문제:

2048 게임은 4x4 크기의 보드에서 혼자 즐기는 게임이다. 

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 디시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

이 문제에서 다루는 2048 게임은 보드의 크기가 NxN이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 쵣 5번 이동해서 만들 수 있는 가장 큰 불록의 값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 보드의 크기 N (1<=N<=20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력:

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

풀이방법:

최대 5번만 이동하면 되기 때문에 dfs를 사용해서 모든 경우를 탐색하고, 그 중 가장 최댓값을 찾아내도록 하면 된다.

반복문을 사용해서 상하좌우로 이동하게 만들었다.

문제링크:

www.acmicpc.net/problem/12100

문제:

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N (10<=N<=100,000)과 S (0<S<=100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력:

첫째 줄에 구호고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

풀이방법:

시작과 끝을 나타내는 두 포인터를 통해서 연속된 부분합을 구하도록 한다. 두 포인터들은 다음 두 규칙에 따라 움직인다.

1. 두 포인터 사이의 합이 S를 넘지 않는다면 end 포인터를 이동시켜서 연속된 수의 길이를 늘린다.

2. 두 포인터 사이의 합이 S를 넘었다면(이상이라면), 현재 길이가 최소인지 확인한다. 그리고 start 포인터를 늘려서 연속된 수의 길이를 줄인다.

3. 1,2의 행동을 end가 수열의 길이를 초과하거나, start가 end 포인터를 넘어갈 떄까지 반복한다.

위 규칙을 마치고 난 다음에 초기 answer 값이 변하지 않았다면 조건을 만족하는 부분합을 찾지 못한 것이기 때문에 0을 출력하고, 아니면 정답을 출력하면 된다.

<2022-02-05> 재채점으로 인한 수정

부분합이지만 하나의 값으로만 S를 넘은 case가 존재한다.

10 10

10 1 1 1 1 1 1 1 1 1

ans 1

문제링크:

www.acmicpc.net/problem/1806

문제:

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