조준장 개발자 생존기

문제 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 알고리즘 - 암호를 해석할 수 있는지 없는지는 첫 번째 숫자가 0인지 아닌지에서 구별 가능하다. - 암호를 해석할 수 있다면 반복문을 통해 암호를 해석한다. - 암호는 2가지 경우로 해석할 수 있는지 확인한다. - 현재 탐색하고 있는 수가 해석 가능한지 확인, 현재 탐색하고 있는 수와 이전에 탐색한 수를 더한 수가 해석 가능한지 확인 - 2가지 경우를 탐색하고 마지막 수까지 해석 가능한 경우의 수를 출력한다. 코드 import sys word = list(map(int, s..

문제 1790번: 수 이어 쓰기 2 첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다. www.acmicpc.net 알고리즘 - 반복문을 통해 자릿수에 맞게 수를 빼준다. - 현재 수에는 자릿수에 맞게 뺀 수의 수를 더한다. - 자릿수를 이동하면서 1의 자리는 9개, 10의 자리는 18개.. 씩 개수를 빼준다. - 자릿수에 맞게 수를 빼줬다면 남은 자릿수의 수를 현재 수에 더해준다. - 현재 수가 n보다 크다면 -1을 출력하고 그게 아니라면 문자열로 변환 후 남은 자릿수의 값을 출력한다. 코드 import sys n, k = map(int, sys.stdin.readline().split()) ans ..

문제 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 알고리즘 - 시간 초과가 나오지 않게 하기 위해 재귀적으로 탐색한다. - 재귀적으로 탐색할 때 현재 수를 1번 곱해도 되는 거라면 현재 값을 c로 나눈 나머지를 리턴한다. - 곱해야 하는 수가 1보다 크다면 현재 수와 b//2로 나눈 값을 재귀적으로 탐색시킨다. - 탐색이 끝나고 나면 b가 짝수인지 홀수인지 확인한다. - 짝수라면 탐색이 끝난 후 리턴 받은 수를 2번 곱하고 c로 나눈 나머지 값을 리턴한다. - 홀수라면 탐색이 끝난 후 리턴 받은 수를 2번 곱하고 a를 한번 더 곱한 후 c로 나눈 나머지 값을 리턴한다. ..

문제 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 알고리즘 - 2차원 배열을 통해 각 곡마다 볼륨을 저장한다. - 반복문을 통해 각 곡을 통해 만들 수 있는 볼륨을 dp에 담는다. - 현재 곡에 볼륨이 담겨있다면 볼륨을 키우거나 줄인 값을 다음 곡에 현재 볼륨을 담는다. - 모든 곡을 확인했다면 마지막 곡에 최대 볼륨을 출력한다. 코드 import sys n, s, m = map(int, sys.stdin.readline().split()) v = list(map(in..

문제 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작 www.acmicpc.net 알고리즘 - 백트래킹을 통해 문제를 수행한다. - Counter 함수를 통해 문자열 안에 문자의 개수를 딕셔너리형으로 변환시킨다. - 반복문을 통해 단어를 확인한다. - 현재 단어와 이전 단어가 같거나 현재 단어의 개수가 0일 경우 다음 단어를 확인한다. - 위 2가지 경우가 아니라면 현재 단어의 개수를 감소시키고 재귀 함수를 돌린다. - 재귀 함수를 빠져나오게 되면 현재 단어의 개수를 다시 증가시킨다.(백 트래킹) - 이때, 문자열의 길이와 현재 비교하고 있는..

문제 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 알고리즘 - n번째 우리의 사자가 없는 경우와 왼쪽에 있을 경우, 오른쪽의 있을 경우를 나눠서 문제를 수행한다. - n번째 우리의 사자를 배치하는 경우의 수의 합을 출력한다. 코드 import sys n = int(sys.stdin.readline()) dp = [[0, 0, 0] for _ in range(n + 1)] dp[1][0], dp[1][1], dp[1][2] = 1, 1, 1 # n = 1일 때, 3가지 경우의 수 # 점화식 : n번째 우리의 사자가 없는 경우와 왼쪽에 있을 경우와 오른쪽의 있을 경우로 나눠서 수행 for i in range(2, n + 1): dp[i][0]..

문제 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 알고리즘 - 반복문을 통해 행렬 a와 행렬 b를 비교한다. - 반복은 3*3 기준으로 확인하기 위해 n-2, m-2로 횟수를 제한한다. - 행렬 a와 행렬 b가 다르면 뒤집는다. - 두 행렬의 모든 부분을 비교 후 두 행렬이 같은지 확인한다. - 두 행렬이 같다면 뒤집은 횟수를 출력하고 다르다면 -1을 출력한다. 코드 import sys n, m = map(int, sys.stdin.readline().split()) a = [list(map(int, sys.stdin...

문제 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 알고리즘 - 큰 사각형(배열)부터 작은 사각형(배열)으로 재귀 함수를 통해 탐색한다. - 탐색 중인 배열 중에 찾는 좌표가 없다면 좌표에 크기를 더한다. => 더 이상 탐색할 필요 없는 사각형(배열)이기 때문. - 찾는 좌표라면 res를 출력하고 종료한다. 코드 import sys def visited(n, r, c): global res # 찾는 좌표라면 res를 출력하고 종료 if r == R and c == C: print(int(res)) ..

문제 2870번: 수학숙제 종이에서 찾은 숫자의 개수를 M이라고 하면, 출력은 M줄로 이루어져야 한다. 각 줄에는 종이에서 찾은 숫자를 하나씩 출력해야 한다. 이때, 비내림차순으로 출력해야 한다. 비내림차순은 내림차 www.acmicpc.net 알고리즘 - 반복문을 통해 각 줄을 확인한다. - 반복문을 통해 줄의 한 단어씩 확인한다. - 단어가 숫자라면 cnt에 추가하고 숫자가 아닌데 cnt에 숫자가 있다면 cnt를 temp에 추가 후 cnt를 초기화시킨다. - 모든 단어를 확인 후에도 cnt에 숫자가 있다면 cnt를 temp에 추가한다. - 각 줄을 확인할 때마다 temp에 담겨있는 모든 수를 res에 추가한다. - 모든 줄을 확인 후에 res를 오름차순으로 정렬 후 한 숫자씩 출력한다. 코드 impo..

문제 2608번: 로마 숫자 첫째 줄과 둘째 줄에 하나씩 로마 숫자로 표현된 수가 주어진다. 입력된 각 수는 2000 보다 작거나 같고, 두 수의 합은 4000보다 작다. www.acmicpc.net 알고리즘 - 아라비아 숫자는 반복문을 통해 각 자릿수를 탐색한다. - 탐색하면서 자릿수가 2개 합쳤을 때 단어가 되는지 확인하고 단어가 되면 그 단어에 값을 더해준다. - 단어가 되지 않으면 하나의 단어의 값을 더해주었다. - 이때 탐색유무를 꼭 체크해주면서 문제를 수행해야 한다. - 로마 숫자를 구하는 것은 밑에 두 코드가 다르지만 결국 자릿수에 따라서 문자를 더해주는 것은 같다. 코드 import sys # 아라비아 숫자 구하기 def Arabia(word): answer = 0 visited = [Fa..