CodeDrive

문제:

크리보드는 kriii가 만든 신기한 키보드이다. 크리보드에는 버튼이 4개만 있으며, 하는 역할은 다음과 같다.

1. 화면에 A를 출력한다.
2. Ctrl-A: 화면을 전체 선택한다
3. Ctrl-C: 전체 선택한 내용을 버퍼에 복사한다
4. Ctrl-V: 버퍼가 비어있지 않은 경우에는 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여넣는다.

크리보드의 버튼을 총 N번 눌러서 화면에 출력된 A개수를 최대로하는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력:

크리보드의 버튼을 총 N번 눌러서 화면에 출력할 수 있는 A 개수의 최댓값을 출력한다.

풀이방법:

DP를 사용해서 해당문제를 풀도록 한다. 이 때, N이 6번까지는 ctrl+A,C,V를 사용하는 것보다 하나를 더 추가하는 것이 더 이득이기 때문에 하나씩 추가하도록 한다. 복사 붙여넣기를 하기 위해서는 최소 3개의 명령어를 사용해야 한다. 따라서 ACV, ACVV, ACVVV, ...와 같은 방법으로 붙여넣기를 진행할 수 있다. 하지만 붙여넣기는 최대 3번만 사용해도 최댓값을 구할 수 있기 때문에 ACV, ACVV, ACVVV 와 같은 3개 경우에 대해서 DP를 진행하도록 한다.

점화식은 dp[i] = max(dp[i-3-j]*(2*j), dp[i])와 같다.

문제링크:

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

문제:

영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다.

영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다.

아래 그림은 4×4 크기의 종이를 자른 한 가지 방법이다.

각 조각의 합은 493 + 7160 + 23 + 58 + 9 + 45 + 91 = 7879 이다.

종이를 적절히 잘라서 조각의 합을 최대로 하는 프로그램을 작성하시오.

입력:

첫째 줄에 종이 조각의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 4)

둘째 줄부터 종이 조각이 주어진다. 각 칸에 쓰여 있는 숫자는 0부터 9까지 중 하나이다.

출력:

영선이가 얻을 수 있는 점수의 최댓값을 출력한다.

풀이방법:

 비트마스킹을 사용하여 해당 문제를 풀었다. N*M의 크기의 직사각형을 0,1의 비트마스킹으로 표현한다. 이 때 0은 가로로 연결되는 경우를 의미하고, 1은 세로로 연결되는 경우를 의미하게 된다.

 주어진 케이스에 대해 가로와 각각 따로 계산을 수행하도록 한다. 가로는 idx가 0인 경우에 대해서만 이어붙이며 값을 누적시키도록 한다. 반대로 세로는 idx가 1인 경우에 대해서만 이어붙이고 값을 누적시킨다. 모든 케이스에 대해서 이 작업을 반복 수행하며 가장 큰 경우를 출력하도록 한다.

문제링크:

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

문제:

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력:

첫째 줄에 세 정수 A, B, C가 주어진다.

출력:

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

풀이방법:

A, B를 담을 수 있는 물통들을 기준으로 하여 visited 배열을 만들고, BFS를 수행하도록 한다. visited의 가능한 갯수는 A와 B에 담을 수 있는 경우의 수와 같다. 처음은 비어있기 때문에, (0,0)으로부터 시작하도록 한다. 매 C는 가지고 있는 A, B 물의 양을 통해 구하도록 한다. 가지고 있는 A, B, C 물의 양을 통해 이동할 수 있는 모든 경우에 대해 조사하도록 한다. (A-> B, A-> C, B->C, B-> A, C-> A, C-> B)와 같은 총 6가지 case가 존재한다. 가능한 모든 경우에 대해 BFS를 수행하며 A의 물의 양이 0인 경우에 C의 값을 저장하도록 한다.

문제링크:

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

문제:

풀이방법:

동물 이름 중 두 번 이상 쓰였다면 이름을 기준으로 grouping 했을 때, 그 갯수가 2개 이상일 것이다. 따라서 group by 와 HAVING 절을 사용하여 동명 동물들을 찾는다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/59041

문제:

풀이방법:

 이름이 있는 동물의 ID란 이름이 NULL이 아닌 동물과 같은 뜻이다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/59407

문제:

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 1,000,000보다 작거나 같다.

출력:

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

풀이방법:

 이전 1, 2, 3 더하기 문제에서는 재귀형태로 문제를 풀었지만 이번에는 숫자의 범위가 크기 때문에 시간초과가 발생할 것이다. 따라서 이번에는 dp 배열을 사용하여 문제를 풀도록 한다. 

 점화식은 간단한 편이다. N을 만들기 위해서 N-3의 경우에서 3을 N-2의 경우에서 2를 N-1일 대는 1을 각각 더해주면 되기 때문이다. 즉, dp[N] = dp[N-1] + dp[N-2] + dp[N-3]과 같다.

1000000까지 dp를 만든 뒤에 N 값을 출력하도록 한다.

문제링크:

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

문제:

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력:

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

풀이방법:

 처음에는 문제를 조금 이해하는 것이 어려웠다. 주어진 모든 사람의 관계가 조건과 같이 구성되어야 하는줄 알았는데, 일부 사람들만 관계를 유지하면 된다. 따라서 N명의 사람들의 관계를 트리 형태로 구성했을 때, 하나의 노드로부터 깊이가 4인 경우가 있는지 확인하면 된다.

 따라서 처음에는 주어진 관계들을 양방향 그래프로 정리를 한다. 그 다음에는 각 노드로부터 dfs를 수행했을 때, 깊이가 4인 경우가 있는지 확인한다. 깊이가 4인 경우가 한 개라도 있으면 되기 때문에 찾았다면 탐색을 중지하고 1을 출력하며, 모든 노드로부터 탐색했는데 없다면 0을 출력하도록 한다.

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

문제:

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

입력:

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력:

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

풀이방법:

 모든 케이스에 대해 수행하기에는 경우의 수가 너무 많기 때문에 그리디하게 이 문제를 해결하도록 한다. 각 알파벳에 대해 가중치를 구한 뒤에 가중치가 높은 순서대로 9부터 숫자를 할당하면 된다.

 가중치는 알파벳이 있는 위치, 갯수에 따라 다르게 설정한다. ABC와 같이 있을 때, 이를 숫자로 보면 A00, B0, C와 같다. 즉 자릿수가 클수록 더 높은 가중치를 가지게 된다. 따라서 word를 순회하면서 가중치를 순회하도록 한다. 이를 dict 형태로 저장하는데, 불필요한 키들을 줄이기 위해 defaultdict을 사용하여 깔끔하게 정리하도록 한다.

 최종적으로는 가중치에 따라 값을 부여하고 합을 누적시키도록 한다.

문제링크:

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

문제:

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수는 N-1보다 많을 수도 있다. 모든 수의 사이에는 연산자를 한 개 끼워넣어야 하며, 주어진 연산자를 모두 사용하지 않고 모든 수의 사이에 연산자를 끼워넣을 수도 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 3개, 뺄셈(-) 2개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 250가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 1+2÷3×4-5+6
• 1÷2×3-4+5+6
• 1+2+3+4-5-6
• 1+2+3-4-5×6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7
• 1+2+3+4-5-6 = -1
• 1+2+3-4-5×6 = -18

N개의 수와 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

출력:

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

풀이방법:

 처음에는 이 문제를 permutation을 사용해서 풀려고 했으나 시간초과나 메모리초과가 발생하게 되었다. 따라서 조금 더 효율적인 방법을 찾고자 고안한 방법은 백트래킹 방법이다.

 permutation은 매 candidate마다 값을 계산해야 한다. 하지만 1,1,3이라는 숫자가 있을 때, 1+1을 한번만 구한 뒤에 3에다가 추가적인 연산을 하는 것이 더 효율적이다. 따라서 dfs를 사용해서 백트래킹 방법을 사용하여 모든 케이스에 대해 연산을 수행하도록 한다. 

문제링크:

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

문제:

크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다.

• R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
• C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.

정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.

행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.

배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.

입력:

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)

둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

출력:

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

풀이방법:

 연산에 따라 행과 열에 각각 행동을 취해야 하는 문제다. 일반적으로 열에다가 특정 연산을 취하는 것은 어렵기 때문에 열에 있는 내용들을 50번줄과 같이 행으로 전환해서 수행하도록 한다.

 각 행을 dict을 사용해서 갯수를 count하고 (횟수, 숫자)를 기준으로 정렬하도록 한다. 각 행을 임시 배열에 저장한 뒤에 가장 긴 행을 기준으로 나머지 부분에 0을 채워넣도록 한다. 만약 열에 대해서 수행했다면 50번줄의 코드를 다시 실행하여 열로 바꿔주도록 한다. 이를 k를 찾거나 100초가 넘을때까지 계속 반복해서 수행한다.

문제링크:

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