조준장 개발자 생존기

문제 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 알고리즘 - 함수와 반복문을 통해 셀프 넘버가 아닌 수를 찾는다. - 찾은 후 1부터 10001번 반복하여 셀프 넘버가 아닌 수와 비교하여 셀프 넘버인 수를 출력한다. 코드 # 셀프 넘버가 아닌 수를 찾는 함수 def solution(n): n = n + sum(map(int, str(n))) return n answer = [] # 반복문을 통해 셀프 넘버가 아닌 수를 찾는다. for i in range(..

문제 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 알고리즘 - 다익스트라를 통해 문제를 수행한다 - 1부터 n까지의 다익스트라와 v1부터 n까지의 다익스트라와 v2부터 n까지의 다익스트라를 구한다. - 1-v1-v2-n과 1-v2-v1-n 으로 이동하는 경우중 최단 거리를 구한다. - 최단 거리가 존재한다면 출력하고 존재하지 않는다면 -1을 출력한다. 코드 import sys import heapq # 다익스트라 def solution(start): visite..

문제 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 반복문을 통해 빙산과 접촉되어 있는 바닷물을 확인한다. - 접촉되어 있는 빙산은 카운트하고 매번 탐색이 끝날 때마다 빙산을 깎아준다. - 빙산이 2개 이상으로 분리되거나 분리가 안된다면 반복을 멈춰준다. - 그때 몇 년 걸렸는지 출력한다. 코드 import sys from collections import deque # bfs 탐색 def bfs(a, b): dx = [1, -1, 0, 0] dy ..

문제 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 알고리즘 - 투 포인터를 통해 문제를 수행한다. - 시작 위치와 마지막 위치를 저장하고 그 위치 사이에 수열의 합을 s와 비교하며 반복문을 수행한다. - 수열의 합이 s보다 크거나 같다면 그때의 길이를 최소 길이와 비교하고 현재 수열의 시작 위치 값을 빼주고 현재 수열의 시작 위치를 한 계단 앞으로 이동시킨다. - 수열의 합이 s보다 크거나 같지 않다면 수열을 만들 수 있는지 확인해준다. - 이때, 맨 끝 위치가 n과 같다면 더 이상 수열의 ..

문제 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 알고리즘 - 유니온-파인드를 통해 문제를 수행한다. - 간선들의 가중치를 기준으로 정렬하여 최소 스패닝 트리의 가중치를 구한다.(비용) - 반복문을 통해 두 간선들의 두 정점을 유니온-파인드를 통해 확인한다. - 두 정점의 부모 노드가 같지 않다면 스패닝 트리인 것이다. - 부모 노드가 같지 않은 두 정점을 작은 루트 노드를 기준으로 합친다. 코드 import sys # 부모 노드 찾기 def find(p): if p == parent[p]: return p parent[p] = find(parent[p]) return parent[p] # 트리..

문제 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 알고리즘 - 백 트래킹을 통해 문제를 수행한다. - 한 팀의 구성이 완료될 때까지 재귀 함수를 수행한다. - 수행 과정에서 백 트래킹이 이루어진다. - 한 팀의 구성이 완료되었다면 두 팀의 능력치를 구한다. - 구하는 과정에서는 탐색한 팀과 탐색하지 않은 팀으로 나눌 수 있다. - 각 팀의 능력치를 구했다면 두 능력치의 최소 값을 구한다. 코드 import sys def solution(idx, depth): global answer # 한 팀의 구성이이 완료 경우 if dept..

문제 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 코드 import sys # 주사위 굴리기 def solution(v): # 동 if v == 1: dice[1], dice[3], dice[4], dice[6] = dice[3], dice[6], dice[1], dice[4] # 서 elif v == 2: dice[1], dice[3], dice[4], dice[6] = dice[4], dice[1], dice[6], dice[3] # 북 ..

문제 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 알고리즘 - 유니온-파인드를 통해 문제를 수행한다. - 간선들의 가중치를 기준으로 정렬하여 최소 스패닝 트리의 가중치를 구한다. - 반복문을 통해 두 간선들의 두 정점을 유니온-파인드를 통해 확인한다. - 두 정점의 부모 노드가 같지 않다면 스패닝 트리인 것이다. - 부모 노드가 같지 않은 두 정점을 작은 루트 노드를 기준으로 합친다. 코드 import sys # 최소 스패닝 트리 # 유니온 파인드 # 부모 노..

문제 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 알고리즘 - 처음에 dfs를 통해 문제를 해결하려 했지만 문제 이름과 같이 플로이드 문제였다. - 반복문을 통해 경로를 확인하고 한 번에 가는 경우와 중간에 거쳐서 가는 경우를 비교/계산한다. 코드 import sys n = int(sys.stdin.readline()) m = int(sys.stdin.readline()) graph = [[1e9 for _ in range(n + 1)] for _ in range(n + 1)] # 자기 자신으로 오는 경우는..

문제 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 알고리즘 - dfs 탐색과 백 트래킹을 통해 문제를 수행한다. - 스도쿠의 규칙을 잘 안다면 쉽게 풀 수 있는 문제이다. 코드 import sys # x 세로줄의 n이 있는지 확인 def checkRow(x, n): for i in range(9): if n == graph[x][i]: return False return True # y 가로줄의 n이 있는지 확인 def checkCol(y, n): for i in range(9): if n == graph..