Algorithm

[문제] https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net [풀이] "아홉 난쟁이의 키는 모두 다르지만 그중 일곱 난쟁이의 크기의 합은 100이 된다" 는 것은 sum(난쟁이 리스트) - (난쟁이1 + 난쟁이2) == 100과 같다. 두 난쟁이를 구하기 위해 전체 탐색을 해야 한다. [코드] import sys men = [int(sys.stdin.readline()) for _ in range(9)] flag = False for i in range(9..

[문제] https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net [풀이] 문제의 핵심은 현재 수업의 종료 시간이 다음 수업의 종료 시간보다 늦을 경우 회의실 하나를 더 배정해야 한다. 먼저 수업의 시작과 끝 시간을 queue에 넣고 이를 정렬하면 시작 시간이 가장 빠른 수업이 가장 앞에 오게 되기 때문에 첫 수업의 종료시간을 새로운 큐인 room에 넣는다. 두 번째 수업부터 첫 번째 회의와 비교를 하는데 두 번째 수업의 시작시간 < 첫 수업의 종료시간 일 경우 강의실을 새로 배정해야 하고 그렇지 않..

[문제] https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net [풀이] 처음에는 간단하게 sort 함수를 이용해 풀었는데 이는 O(nlogn)으로 우선순위 큐를 이용하면 O(logn)으로 시간복잡도를 줄일 수 있다. 우선순위 큐 사용시, 값을 바꿀 카드 2개를 우선순위 큐에 삽입만 하면 되기 때문에 매번 정렬해야하는 sort 보다 훨씬 효율적인 것이다. 따라서 cards 리스트를 만든 후 heapq 내장 모듈 사..

[문제] https://www.acmicpc.net/problem/9009 9009번: 피보나치 입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T 가 주어진다. 각 테스트 데이터에는 하나의 정수 n www.acmicpc.net [풀이] 우선 피보나치 리스트를 만들어 올바른 값을 미리 넣어준다. 문제에 n의 최댓값이 1,000,000,000이라고 했기 때문에 44번 째 피보나치 수열까지만 구하면 된다. 만들 수 있는 숫자 중 최소 개수로 n을 만들기 위해서는 n 이하의 수 중 가장 n과 가까운 수를 써야 한다. 문제에 나온 예시처럼 100을 만들기 위해서는 (3 + 8 + 89) 도 가능하지만 (3 + 8 + 34 ..

[문제] https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net [풀이] 우선.. for문을 두 번 쓰면 런타임 에러가 난다. 당연함. 100,000명을 2차 반복문으로 돌리면.. 따라서 반복문 한번에 비교를 끝내야한다. 그러기 위해 우선 첫 번째 점수를 기준으로 정렬을 한 후에 rank_asc 변수에 담는다. rank_asc 변수의 첫 번째 원소는 서류 심사가 가장 높은 사람이 오기 때문에 이 사람의 면접 결과가 몇 점이든 무조..

[문제] https://www.acmicpc.net/problem/1817 1817번: 짐 챙기는 숌 첫째 줄에 책의 개수 N과 박스에 넣을 수 있는 최대 무게 M이 주어진다. N은 0보다 크거나 같고 50보다 작거나 같은 정수이고, M은 1,000보다 작거나 같은 자연수이다. N이 0보다 큰 경우 둘째 줄에 책 www.acmicpc.net [풀이] 이 문제의 핵심은 책을 차례대로 박스에 넣을 수 있다는 것이다. 때문에 차례대로 반복문을 돌며 박스에 책을 넣었을 때 박스에 들어간 무게가 M을 넘는다면 박스 무게를 초기화 하여 현재 책의 무게를 담고 cnt를 1 증가시킨다. [코드] import sys N, M = map(int, sys.stdin.readline().split()) if N > 0: bo..

[문제] https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net [풀이] 입력받은 문자열을 한 글자씩 리스트에 넣는다. 첫 번째 문자가 0이면 zero_count를 1 더해주고, 1이면 one_count를 1 더해준다. zero_count: 0을 1로 바꿔야 하는 횟수 one_count: 1을 0으로 바꿔야 하는 횟수 반복문으로 문자열의 (i - 1) 인덱스와 (i) 인덱스의 값이 일치하는지 확인한다. 일치하지 않을 경우 (i) 인덱스의 값이 0이면 ..

[문제] https://www.acmicpc.net/problem/10162 10162번: 전자레인지 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 www.acmicpc.net [풀이] 그리디 문제! 최종 결과는 신경쓰지 않고 일단 현재 가장 이익이 될 것을 선택한다. 여기서 현재 가장 이익이 될 것 = 거스름돈이 제일 작을 것 시간이 긴 버튼을 누르는 게 이익이 되기 때문에 5분부터 차례대로 답을 찾아간다. [코드] import sys T = int(sys.stdin.readline()) A, B, C = 300, 60, 10 if T % C != 0..

[문제] https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net [풀이] 지역의 높이 정보를 set 으로 모아 어떤 높이의 건물이 있는지 비가 얼마나 오는 지 모르기 때문에 0부터 건물 최고 높이까지 비를 내리게 한다. 건물의 높이는 지역의 높이 정보를 set 으로 모아 확인한다. 건물 높이보가 현재 내리는 비 높이보다 크고 아직 그 건물을 방문한 적이 없으면 count 를 하나 올리고 bfs 함수로 들어간다. 현재 기준이 되는 건물의 상하좌우 에 있는 건물..