조준장 개발자 생존기

문제 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 알고리즘 - 반복문을 통해 숫자 카드를 확인한다. - 이분 탐색을 통해 상근이의 카드 중에 현재 카드가 있는지 확인한다. - 상근이가 뽑은 카드가 현재 숫자 카드라면 1을 출력하고 반복을 멈춘다. - 상근이가 뽑은 카드가 현재 숫자 카드보다 크다면 더 작은 카드를 뽑기 위해 카드의 범위를 내린다. - 반대로 현재 숫자 카드가 크다면 더 큰 카드를 뽑기 위해 카드의 범위를 올린다. - 이분 탐색 후에도 상근이의 카드 중에서 현재 ..

문제 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 알고리즘 - 이분 탐색을 통해 문제를 수행한다. - 반복문을 통해 랜선을 잘랐을 때 남은 랜선의 개수를 구한다. - 자르고 남은 랜선의 개수가 필요한 랜선의 개수보다 크다면 더 이상 랜선을 자를 필요 없기에 반복을 멈춘다. - 필요한 랜선보다 현재 자른 랜선의 개수가 크거나 같다면 랜선을 자를 길이를 늘려준다. - 반대로 필요한 랜선보다 현재 자른 랜선의 개수가 작다면 랜선의 길이를 줄여준다. - 필요한 랜선의 개수를 만들 수 ..

문제 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 알고리즘 - 이분 탐색을 통해 문제를 수행한다. - 반복문을 통해 절단기로 나무를 자른 후 가져갈 수 있는 나무의 높이를 구한다. - 가져갈 수 있는 나무의 높이가 가져가려 하는 나무의 높이보다 크면 더 이상 가져갈 수 있는 나무의 높이를 구하지 않아도 되므로 반복을 멈춰준다. - 가져갈 수 있는 나무의 높이가 가져가야 하는 나무의 높이보다 크거나 같으면 절단기의 높이를 올려준다. - 반대로 가져가야 하는 나무의 높이..

문제 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 알고리즘 - 이분 탐색을 통해 문제를 수행한다. - 기본적인 이분 탐색 문제로 가운데 수와 찾아야 하는 수가 똑같은지 확인한다. - 이분 탐색이 끝나고도 똑같은 수가 없다면 찾아야 하는 수가 없는 것이다. 코드 import sys n = int(sys.stdin.readline()) n_list = list(map(int, sys.stdin.readline().split())) m = int(sys.stdin..

문제 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 아기 상어가 먹을 수 있는 물고기가 없을 때까지 반복한다. - 아기 상어가 현재 이동할 수 있는 모든 곳을 탐색하고 이동한 곳에 아기 상어보다 크기가 작은 물고기가 있다면 힙에 추가한다. - 문제를 보면 위, 왼쪽 물고기부터 먹어야 하는 우선순위가 있다. 따라서 heapq 우선순위 큐를 통해 물고기를 먹는다. - 아기 상어의 크기와 먹은 물고기의 양이 같다면 아기 상어의 크기를 1 키운다. - 위 ..

문제 1323번: 숫자 연결하기 첫째 줄에 N과 K가 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. K는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 알고리즘 - 나머지 연산을 하고 나머지가 0인지 확인한다. - 나머지가 0이면 연산 횟수를 출력한다. - 0이 아니라면 str으로 같은 수를 더하는 연산을 한다. - set() 자료형에 나누어야 하는 수를 추가하고 나누어야 하는 수가 set() 집합에 포함되어 있으면 무한 루트 이므로 -1을 출력한다. 코드 import sys n, k = map(str, sys.stdin.readline().split()) cnt = 0 # 연산 횟수 temp = n # 같은 수를 더하는 연산을 해줄 변수 paper = s..

문제 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 알고리즘 - 딕셔너리 자료형을 통해 문제를 수행한다. - 반복문으로 사이트의 주소와 비밀번호를 입력받아 딕셔너리에 담는다. - 반복문으로 찾고자 하는 비밀번호의 주소를 딕셔너리에 넣어 비밀번호를 출력한다. 코드 import sys n, m = map(int, sys.stdin.readline().split()) site = dict() # 딕셔너리형 # 반복문을 통해 사이트의 주소와 비밀번호를 입력받아 딕셔너리에 담는다. for..

문제 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 알고리즘 - 맨 뒤에 있는 막대기를 제일 높은 막대기로 초기화한다. - 반복문을 통해 막대기의 높이를 확인한다. - 제일 높은 막대기보다 현재 막대기의 높이가 크면 제일 높은 막대기를 현재 막대기로 초기화해준다. - 제일 높은 막대기가 바뀔때마다 카운트한다.(처음에 맨 뒤에 있는 막대기를 제일 높은 막대기를 초기화했기 때문에 카운트를 1로 초기화) 코드 import sys n = int(sys.stdin.readline()) stack = [int(sys.stdi..

문제 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 알고리즘 - set() 자료형을 통해 진실을 아는 사람과 파티에 참여하는 사람을 입력받는다. - 파티의 수만큼 반복하여 파티에서 진실을 아는 사람이 포함되어 있는 파티를 찾는다. 파티의 수만큼 반복하는 이유는 모든 파티를 확인 후 진실을 아는 사람이 더 생길 경우 모든 파티를 한번 더 확인해줘야 하기 때문이다. 따라서 최대 파티의 수만큼 반복하여 진실을 아는 사람을 찾아야 한다. - 반복문을 통해 각 파티의 참여한 사람을 확인하고 파티의 참여한 사람 중 진실을 아는 ..

문제 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 알고리즘 - 리스트 안에 미리 제일 작은 수를 넣어놓는다. - 비교할 수도 제일 작은 수로 초기화시킨다. - 각 행의 열의 크기를 비교하면서 타겟보다 큰 수라면 큰 수를 heap 리스트에 추가한다. - 다음으로 heap 리스트에 제일 작은 수를 팝하고 그 수를 타겟으로 바꾼다. - n번째로 큰 값을 구하는 것으로 n번째보다 큰 수이면 리스트에 제일 작은 수를 팝한 후 큰 수를 heap 리스트에 넣는 방법을 문제를 수행했다. 코드 import heapq import..