조준장 개발자 생존기

문제 9081번: 단어 맞추기 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알 www.acmicpc.net 코드 import sys def next_permutation(s): k = -1 # 반복문을 통해 문자열의 크기를 비교한다. # 모든 문자가 오름차순으로 정렬되어 있다면 현재 문자가 마지막 단어인 것이다. for i in range(len(s) - 1): if s[i] < s[i + 1]: k = i # 마지막 단어라면 Flase if k == -1: return False # 반복문을 통해 마지막 인덱스부터 0번째 인덱스까지 s[k]보다 큰 ..

문제 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 알고리즘 - 주석 확인! - dp 문제는 규칙을 찾는게 중요한데.. 이러한 문제의 규칙을 찾는 사람들은 정말 똑똑한 것 같다. 코드 import sys n = int(sys.stdin.readline()) dp = [0, 1] # 반복문을 통해 합이 n번째까지 제곱수들의 최소 개수를 구함. for i in range(2, n + 1): target = 1e9 # 반복문을 통해 최대 50000의 제곱을 확인 for j in ..

문제 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr 알고리즘 - 숫자와 문자열을 딕셔너리로 만들고 문제를 수행한다. - 반복문을 통해 숫자면 숫자를 문자열로 더한다. - 숫자가 아니라면 temp에 저장하고 저장된 문자열이 딕셔너리 키 값이라면 벨류 값을 더한다. - 모두 더한 값을 정수형으로 출력한다. 코드 def solution(s): answer = "" dic = {"zero" : "0", "one" : "1", "two" : "2", "three" : "3", "four" : "4", "f..

문제 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 알고리즘 - 아스키코드 순서에 따라 백 트래킹을 수행한다. - 백 트래킹을 통해 모든 수식을 만들었다면 수식 사이사이에 숫자를 넣어 본다. - 수식과 숫자를 합쳤다면 eval를 통해 수식이 0이 되는지 확인한다. - 공백이 있을 수 있으므로 replace를 통해 공백을 제거한다. - 아스키코드 순서에 따라 백 트래킹 했기 때문에 결과를 바로 출력하면 된다. 코드 import sys import copy # 아스키 코드 순서에 따라 백 트래킹 def back_tracking(v): # 수식 개수가 n -1 개면..

문제 5635번: 생일 어떤 반에 있는 학생들의 생일이 주어졌을 때, 가장 나이가 적은 사람과 가장 많은 사람을 구하는 프로그램을 작성하시오. www.acmicpc.net 알고리즘 - sort lamda를 통해 정렬하여 문제를 수행한다. - 정렬은 년/월/일 순으로 하며 오름차순과 내림차순은 자유롭게 하여 출력 양식의 맞게 출력한다. 코드 import sys n = int(sys.stdin.readline()) names = [list(map(str, sys.stdin.readline().split())) for _ in range(n)] names.sort(key=lambda x : (int(x[3]) , int(x[2]), int(x[1]))) # 년/월/일 기준으로 졍렬 # 갸장 나이가 적은 사람의..

문제 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 알고리즘 - 점화식을 통해 문제를 수행한다. - 점화식 : dp[i][j] = dp[i][j - 1] + dp[i - 1][j] n = 1 n = 2 n = 3 n = 4 n = 5 ... k = 1 1 1 1 1 1 ... k = 2 2 3 4 5 6 ... k = 3 3 6 10 15 21 ... 코드 import sys n, k = map(int, sys.stdin.readline().split()) dp = [[0] * 201 for _ in range(201)] # 점화식 : dp[i][j] = dp[i][j - 1] + dp[i - 1][j] # 초기 세팅 for x in..

문제 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 알고리즘 - 타일을 만들어 내면서 점화식을 생성한다. - 반복문을 통해 점화식을 수행한다. 점화식을 구하는 과정을 아래에 작성해보았다. dp[2] => 3 * 2인 경우 머리로 생각해내서 타일을 만들어 볼 수 있다. dp[3] => 3 * 3인 경우 만들 수 있는 타일이 없다. 이때 홀수는 만들 수 없는 것으로 판단했다. dp[4] => 3 * 4인경우 3 * 2를 2개 쓴다. (dp[2] * 2) 9가지 이후, 위 두 모양의 특수한 모양 2개를 추가한다. dp[6] => 3 * 6인 경우 1) 3 * 4짜리에 11개가 들어가고 3 * 2짜리에 3가지가 들어갈 수 있..

문제 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 알고리즘 - dfs 탐색을 통해 문제를 수행한다. - 반복문을 통해 현재 방향에서 왼쪽 방향씩을 확인한다. - 현재 방향 + 3을 4로 나눈 나머지가 왼쪽 방향이다. - 이동하려는 위치가 빈 곳이라면 탐색을 하고 현재 방향을 변경한다. - 4방향 모두 탐색했다면 후진 방향을 확인한다. - 현재 방향 + 2를 4로 나눈 나머지가 후진 방향이다. - 이동 위치가 벽이라면 리턴하고 벽이 아니라면 탐색한다. 코드 import sys def dfs(x, y, v):..

문제 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 알고리즘 - 반복문을 통해 집의 좌표와 치킨집의 좌표를 구한다. - 구한 치킨집을 combinations를 통해 m개를 선택 후 각 집마다 치킨집의 거리를 구한다. - 그때의 모든 경우의 수중 집과 치킨집의 거리의 최솟값을 구한 후 출력한다. 코드 import sys from itertools import combinations n, m = map(int, sys.stdin.readline().split()) graph = list(li..

문제 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 알고리즘 - 0층부터 256층까지 반복하여 블록을 확인한다. - 블록이 층수보다 더 크면 그때의 개수를 더하고 블록의 층수보다 더 작으면 그때의 개수를 더한다. - 블록을 뺀 것과 원래 있던 블록의 합과 블록을 더한 값을 비교한다. - 블록을 뺀 것과 원래 있던 블록의 합이 더 커야 층을 만들 수 있다. - 층을 만들 수 있다면 그때의 시간초를 구하고 최저 시간과 비교한다. - 0부터 256층까지 비교하므로 업데이트될수록 고층의 최저 시간이 된다. 코드 i..