조준장 개발자 생존기

문제 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] # 반복문을..

문제 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 알고리즘 - 0 - 1 bfs 탐색을 통해 문제를 수행한다. - 동생의 위치에 도달했다면 리턴하고 도달하지 못했다면 이동한다. - 이동은 3가지 방법을 반복문을 통해 수행한다. - 이동하는 곳이 범위 내에 있고 이동하지 않은 곳이라면 이동한다. - 순간이동이라면 이전에 초로 갱신하고 appendleft()로 탐색한다. - 순간이동이 아니라면 이전에 초에 +1 해주고 append()로 탐색한다. - 위 탐색과정이 다른 것이 0..

문제 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 알고리즘 - 0번째 idx를 기준으로 오름차순 정렬을 한다. - 정렬된 전깃줄에 가장 길게 증가하는 부분 수열을 찾는다. - 이중 반복문을 통해 n번의 수까지 증가하는 길이를 구한다. - 길이를 구할 때 i번의 수와 그전에 수들을 비교한다. - 0번째 idx를 기준으로 오름차순 정렬을 했기 때문에 1번째 idx를 기준으로 수들을 비교한다. - 이때 가장 길게 증가하는 부분 수열이 겹치지 않는 전깃줄이므로 전체에서 빼준 값을 출력한다. 코드 import sys n ..