조준장 개발자 생존기

문제 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..

문제 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..