조준장 개발자 생존기

문제 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 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..

문제 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 알고리즘 - 백 트래킹을 통해 문제를 수행한다. - 암호를 만들었다면 암호에 모음과 자음의 개수를 체크한다. - 모음이 1개 이상, 자음이 2개 이상이라면 암호를 잘 만든 것으로 출력한다. - 암호는 반복문과 백 트래킹을 통해 만든다. 코드 import sys def back_tracking(cnt, idx): # 암호를 만들었을 때 if cnt == l: # 모음, 자음 체크 vo, co = 0, 0 for i in range(l): if answer[i] i..

문제 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 알고리즘 - 백 트래킹과 bfs 탐색을 한 번에 수행한다. - 벽을 3개 세울 때까지 백 트래킹 후 3개 세웠다면 바이러스 위치에서 bfs 탐색을 한다. - 탐색 후 안전한 위치를 카운트하여 최댓값을 출력한다. 코드 pypy3 통과 import sys from collections import deque import copy # 백 트래킹 def back_tracking(cnt): global answer # 벽을 3개 세웠다면 if cnt == 3: answer = m..