조준장 개발자 생존기

문제 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 3차원 그래프를 통해 문제를 수행하는 것이라 까다로울 수 있지만 집중해서 풀면 다른 bfs 탐색 문제와 다를 게 없다. 코드 import sys from collections import deque # bfs 탐색 def bfs(): queue = deque([[sz, sy, sx]]) dx = [1, -1, 0, 0, 0, 0] dy = [0, 0, -1, 1, 0, 0] dz = [0, 0, 0, 0, 1..

문제 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 알고리즘 - 반복문을 통해 두 개의 문자열을 확인한다. - 두 개의 문자열중에 문자가 같다면 dp에 +1로 저장한다. - 저장된 dp값과 answer 값을 비교하여 더 큰 값을 answer에 저장한다. 코드 import sys s1 = list(map(str, sys.stdin.readline().strip())) s2 = list(map(str, sys.stdin.readline().strip())) dp = [[0] * (len(s2) + 1..

문제 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 알고리즘 정리! 1. 반복문을 통해서 코인을 확인 2. 1원부터 m원까지 돈(j) - 코인(i) => 0보다 크다면 코인으로 만들 수 있는 돈 3. dp[j] += dp[j - i] 4. 위 식의 j - i의 경우 이전에 dp의 저장된 j-i번 째의 수를 가져와 사용하는 것을 의미 5. 즉, j - i를 사용했을 때의 경우의 수에 i를 더한 것 i == 1일 때 1원 : 1 2원 : 11 3원 : 111 4원 : 1111 5원 : 11111..

문제 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 알고리즘 - dfs 탐색을 통해 문제를 수행한다. - 반복문을 통해 각 친구들의 친구 관계를 확인한다. - 친구 관계는 백 트래킹을 통해 확인하고 친구 관계를 확인할 때마다 깊이를 +1 해준다. - 친구 관계의 깊이가 4라면 문제에서 원하는 친구 관계이므로 1을 출력하고 시스템을 종료한다. - 문제에서 원하는 친구 관계가 아니면 0을 출력한다. 코드 import sys # dfs 탐색 def dfs(v, depth): # 친구 관계가 존재한다면 1출력 후 종료 if depth == 4: print(1) exit() # 반복문을 통해 친구 관계 확인 for j in..

문제 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 알고리즘 - 반복문과 조합을 통해 감소하는 수를 확인한다. - 최대 감소하는 수는 9876543210이기 때문에 1부터 11까지 반복하여 0부터 9의 자리에 수를 조합한다. - 조합한 수는 내림차순으로 정렬하고 int형으로 바꾼다. - 바꾼 수는 answer에 추가하고 answer는 오름차순으로 정렬하여 순서를 매겨준다. - 감소하는 수가 있을 때와 없을 때를 나누어 출력한다. 코드 import sys from itertools import ..

문제 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 알고리즘 - 벡터의 외적을 통해 시계 방향인지 아닌지를 판별한다. 코드 import sys p = [list(map(int, sys.stdin.readline().split())) for _ in range(3)] v1 = [p[1][0] - p[0][0], p[1][1] - p[0][1]] # p1 -> p0 v2 = [p[2][0] - p[1][0], p[2][1] - p[1][1]] #..

문제 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 알고리즘 - dp를 통해 문제를 수행한다. - 우선 처음에 가로로 갈 수 있는 모든 빈 곳을 1로 초기화한다. - 다음으로 반복문을 통해 가로/세로/대각선으로 갈 수 있는 곳에 위치에 dp를 더해준다. - 3가지 방향으로 파이프가 이동해 온 경우의 수의 합을 출력한다. 코드 import sys n = int(sys.stdin.readline()) graph = [list(map(int, sys.stdin.readline().split..

문제 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 모든 육지 지점에서 다른 육지 지점까지의 거리를 bfs를 통해 체크한다. - 체크된 거리 중 제일 먼 거리 -1을 출력한다. - -1을 해주는 이유는 처음 지점에서 1로 방문 체크를 했기 때문이다. - 방문 체크를 하는 이유는 중복으로 처음 지점을 지나는 것을 방지하기 위해서이다. 코드 # pypy3 통과.. python3 시간초과.. import sys from collections import deque..

문제 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 알고리즘 - 반복문을 통해 각 줄을 확인한다. - 반복문을 통해 각 칸의 들어갈 수 있는 최대/최소 값을 구한다. - 최대/최소 값은 매 반복이 끝날 때마다 max_dp/min_dp에 초기화시켜준다. 코드 import sys n = int(sys.stdin.readline()) max_dp = [0 for _ in range(3)] min_dp = [0 for _ in range(3)] max_tmp = [0 for _ in range(3)] min_tmp = [0 fo..

문제 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. 코드 import sys from collections import deque # bfs 탐색 def bfs(): visited = [1e9] * 1000001 queue = deque([s]) visited[s] = 0 while queue: target = queue.popleft() # 스타트 링크에 도착했으면 버튼을 누른 횟수 출력 if target == g: return visited[target] # 반복문을..