복습노트 복습노트

문제 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net n과 r을 입력받아 nCr 을 출력하면 되는 문제입니다. n과 r은 범위가 100까지 입니다. 단순히 계산하게 되면 오버플로우가 발생합니다. 따라서 string 형으로 계산을 해줘야 합니다. 조합을 구하는 방식은 '파스칼의 삼각형' 방식을 이용해 문제를 해결하였습니다. nCr = (n-1)C(r-1) + (n-1)C(r) 입니다. 먼저 위와 같은 방식으로 dp 형태로 nCr을 계산할 예정입니다. string arr[101][101] string combination(int n, int r) { if (n == r || r == 0) //nCn =1 , nC0 = 1 ret..

문제 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net n * m 의 공간은 한 칸당 1이상 1000이하의 수를 가집니다. 이 때 다음과 같은 공간의 합의 최대를 구하는 문제입니다. 위의 공간은 n * m의 공간에서 상하좌우로 대칭이 가능합니다. 처음에 이 문제를 접근할 때에는 n * m 배열에서 첫번째 인덱스 부터 시작해서 위의 도형을 차례대로 대칭하면서 최댓값을 구하려 했지만 시간이 너무 많이 들고 구현에 어려움이 있었습니다. 하지만 자세히 도형들을 살펴보면 ㅜ 모형을 제외한 나머지 도형들은 dfs 탐색으로 ..

문제 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 숫자 a, b를 입력받고 4가지 연산 D, S, L, R을 통해 a가 b로 되게하는 연산을 모두 구하는 문제입니다. D연산은 a에 2를 곱하고 10000으로 나눕니다. S연산은 a에 1을 뺀 연산입니다. 만약 음수가 되면 9999가 됩니다. L연산은 각자릿수를 왼쪽으로 이동시키는 연산입니다. 예를 들어 1234는 2341이 됩니다. R연산은 각자릿수를 오른쪽으로 이동시키는 연산입니다. 예를 들어 4321은 1432가 됩니다. 모든 경우의 수를 ..

문제 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 명령문을 입력 받습니다. 예를 들어 I 60 이면 벡터에 60을 삽입합니다. D -1 이면 벡터 값 중에 최솟값을 삭제합니다. D 1 이면 벡터 값 중에서 최댓값을 삭제합니다. k개의 명령문이 끝나고 남아있는 벡터의 최댓값과 최솟값을 출력하면 되는 문제입니다. 만약 벡터가 비어있으면 "EMPTY"를 출력하면 됩니다. 처음에 생각한 방안은 priority queue를 오름차순과 내림차순으로 두가지의 큐를 관리해 D 명령어를 처리하는 방식입니다. 하지만 이..

문제 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 배열을 입력 받고 명령문을 입력받습니다. 명령문중 R은 입력받은 배열을 뒤집는 것이고, D는 배열의 첫번째 원소를 삭제하는 것입니다. 모든 명령어가 끝났을 때 배열을 출력해주는 문제입니다. 단순히 알고리즘은 쉬웠습니다. 자료구조 덱 을 이용해 풀어보았지만 계속 '시간초과' 가 나왔습니다. 힌트를 얻어보니 배열을 뒤집는 것은 굳이 뒤집을 필요가 없는 것입니다. 매번 R 명령어를 볼떄 마다 뒤집어주면 시간초과가 나지만 배열의 앞뒤를 체크해주고 마지막에 출력할 때만 거꾸로 출력하든가, 맨 앞에서 부터 출력하든가 하면 ..

문제 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 현재 채널은 100번입니다. 여기서 n번의 채널로 이동하려 할떄 최소로 버튼을 누르는 횟수를 구하는 문제입니다. 여기서 m개의 고장난 번호가 주어지는 데 고장난 번호는 누를 수 없습니다. 만약 고장난 번호로 이동하려면 '+' 번호나 '-' 를 눌러 +1 또는 -1로 이동가능합니다. 예를 들어 n = 5457 이고 3개의 고장난 번호는 6, 7, 8 이라면 처음에 5455 총 4번의 버튼을 눌러 5455번 채널로 이동해 + 버튼을 2번 눌러 ..

문제 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net m과 n이 주어지고 x와 y가 주어지면 가 몇번째로 이루어지는지 구하는 문제입니다. 만약 가 안되면 -1을 출력하면 됩니다. 부터 시작하며 x' n을 넘어가면 다시 x'가 1로 되고 y도 마찬가지 입니다. 예를 들어 m과 n이 10, 12 라면 부터 시작해 까지 가고 은 x'가 m을 넘어가 되므로 다음에는 이 됩니다. 마찬가지로 가 되고 다음 순서는 이 되어야 하지만 y'가 n을 넘어가게 되므로 가 됩니다. 는 60번째 에서 마지막이 되고 끝이 납니다. 단순히..

문제 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 숫자와 연산자가 포함된 식이 주어지면 임의의 괄호를 쳐서 가장 작은수를 출력하면 됩니다. 예를 들어 55 - 50 + 40 이라는 식이 주어지면 55 -(50 + 40) = -35 이렇게 최소의 값을 출력하게 하면 됩니다. 처음에는 괄호를 처음부터 치면서 brute force문제 인지 알았지만 brute force로 구현이 어려워 힌트를 찾아봤습니다. 100 - 10 + 50 -10 + 100 다음과 같은 식을 최소로 만들려면 100 -(10 + 50..