조준장 개발자 생존기

문제 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..

문제 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr 알고리즘 - 조직 구성원과 추천인을 딕셔너리형으로 만든다. - 조직 구성원과 구성원들의 이익금을 딕셔너리형으로 만든다. - 반복문을 통해 판매원을 확인한다. - 확인 중인 판매원의 판매 금액을 가지고 반복문을 통해 그 판매원의 추천인을 확인한다. - 현재 판매 금액이 10원보다 적다면 현재 조직 구성원에게 돈을 다 주고 반복을 멈춘다. - 현재 판매 금액이 10원보다 크다면 판매금액에 10%를 제외하고 현재 조직 구성원에게 돈을 준다. - 현재 조직 ..

문제 9536번: 여우는 어떻게 울지? 각 테스트케이스마다 여우의 울음소리를 한 줄씩, 녹음된 순서대로 출력한다. 여우의 울음소리가 녹음되어 있음이 보장된다. (알려진 것과는 달리, 여우는 모스 부호로 의사소통하지 않는다.) www.acmicpc.net 알고리즘 - 테스트 케이스만큼 반복한다. - 반복문을 통해 동물들의 울음소리를 확인하고 동물들의 울음소리가 아닌 질문이 주어진다면 반복을 멈춰준다. - 동물들의 울음소리라면 녹음된 음성에서 동물들의 울음소리를 반복문을 통해 제거한다. 코드 import sys t = int(sys.stdin.readline()) # 테스트 케이스만큼 반복 for _ in range(t): sound = list(map(str, sys.stdin.readline().spli..