조준장 개발자 생존기

문제 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 알고리즘 - 문제의 조건에 맞게 switch문으로 문제를 수행한다. 코드 package implementation; import java.io.*; import java.util.HashSet; import java.util.Set; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System..

문제 1205번: 등수 구하기 첫째 줄에 N, 태수의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보 www.acmicpc.net 알고리즘 - 랭킹 리스트에 점수가 있는지 확인하고 점수가 없다면 무조건 1등이므로 1을 출력한다. - 랭킹 리스트에 점수가 있다면 랭킹 리스트에 새로운 점수를 넣고 새로운 점수의 등수를 확인한다. - 등수가 랭킹의 올라갈 수 있는 등수보다 크다면 -1을 출력한다. - 랭킹 리스트의 길이와 랭킹의 올라갈 수 있는 등수의 길이가 같고 마지막 등수가 새로운 점수의 등수와 같다면 즉, 새로운 점수가 마지막 점수와 동점이라면 -1을 출력..

문제 1063번: 킹 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 www.acmicpc.net 알고리즘 - 킹의 자표와 돌의 좌표를 아스키코드를 통해 x, y형태로 바꾼다. - 킹이 움직이는 명령을 딕셔너리로 받아서 좌표 형태로 바꾼다. - 반복문을 통해 명령을 입력받고 킹의 좌표와 돌의 좌표를 움직여준다. 코드 import sys k, s, n = map(str, sys.stdin.readline().split()) k = list(map(int, [ord(k[0]) - 64, k[1]])) s = list(map(int, [ord(s[0]) - 64, s[..

문제 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 알고리즘 - 일반적으로 소수를 구하는 방법으로 구하게 되면 시간 복잡도가 O(n^2)이고 에라토스테네스의 체를 통해 구하게 되면 시간 복잡도가 O(log n)이다. - 따라서 에라토스테네스의 체를 통해 소수를 구한다. - 구한 소수가 범위 내에 있다면 출력한다. 코드 import sys m, n = map(int, sys.stdin.readline().split()) dp = [False, False] + [True] * 1000001 primes = [] # 에라토스테네스의 체를 통해 ..

문제 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 알고리즘 - 반복문을 통해 모든 몸무게와 키를 비교한다. - 비교하는 몸무게와 키가 더 작다면 그보다 큰 값이 있는 것으로 등수를 카운트해준다. 코드 import sys n = int(sys.stdin.readline()) m = [list(map(int, sys.stdin.readline().split())) for _ in range(n)] answer = [] # 반복문을 통해 몸무게와 키를 확인 for x, y in m: cnt = 1 ..

문제 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] # 트리..