백준 Online Judge
-
[큐] 1966 프린터 큐백준 Online Judge 2022. 1. 19. 21:09
백준 문제 1966 난이도: 하 문제 유형: 큐, 구현, 그리디 enumerate 함수 설명 순서가 있는 자료형 (e.g. 리스트, 튜플, 문자열)을 입력 받아서 인덱스 값과 함께 보여준다. >>> for i, name in enumerate(['kim', 'han', 'park']): print(i, name) 0 kim 1 han 2 park 문제 풀이 코드 test_case = int(input()) for _ in range(test_case): n, m = list(map(int, input().split(' '))) queue = list(map(int, input().split(' '))) # 튜플 형식으로 넣는다. [2, 1, 4, 3] -> [(2, 0), (1, 1), (4, 2), (..
-
[백준] 2110 공유기 문제백준 Online Judge 2021. 9. 27. 17:29
1 문제 설명 백준 문제 난이도 : 중 문제 유형 : 이진 탐색 입력 : 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다. 출력 : 가장 입접한 두 공유기 사이의 최대 거리 2 문제풀이 아이디어 이진 탐색을 이용하여 O(N * logX)로 해결한다. (X = 집의 좌표) 20만 * log10억 = 약 600만 두 공유기 사이의 최대 간격을 이진 탐색으로 찾는다. 탐색 범위가 클 때는 logX를 요구한다고 가정한다. 이진 탐색 구현 방법 : 재귀적 or 반복적 3 이진 탐색 탐색 범위를 ..
-
[백준] 1543 - 문서 검색백준 Online Judge 2021. 9. 15. 17:59
1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 최대 길이가 2,500. 단어의 길이는 최대 50 시간 복잡도 o(nm)으로 해결 가능하다. document = input() word = input() index = 0 result = 0 while len(document) - index >= len(word): # 단어 확인 할 때, 인덱스에서 단어 길이 만큼 확인한다. if document[index:index + len(word)] == word: result += 1 index += len(word) els..
-
[1568] 새백준 Online Judge 2021. 9. 15. 17:31
문제 유형: 탐색 N이 최대 1,000,000,000이다. k가 반복적으로 증가하므로, 단순 구현하여도 쉽게 셀 수 있다. 예를 들어, 14일 때, 1마리 2마리 3마리 4마리 1마리 2마리 1마리이므로 총 7초 1568번: 새 N마리의 새가 나무에 앉아있고, 자연수를 배우기 원한다. 새들은 1부터 모든 자연수를 오름차순으로 노래한다. 어떤 숫자 K를 노래할 때, K마리의 새가 나무에서 하늘을 향해 날아간다. 만약, 현 www.acmicpc.net n = int(input()) result = 0 k = 1 while n != 0: if k>n: k = 1 n -= k k += 1 result += 1 print(result) 쉽게 표로 표현 하였다. k = 1 2 3 4 5 1 2 3 n = 14 13..
-
[백준] 1302 베스트셀러백준 Online Judge 2021. 9. 14. 21:40
1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 문제 해설 가장 많이 팔린 책의 제목을 출력한다. 문자열을 출력하는 문제와 동일. 등장 횟수를 계산할 때는 dictionary를 이용하면 효과적 입력 : 첫 번째 줄에 책의 개수. 두 번째부터 책의 제목. # 책의 개수를 입력 받는다. n = int(input()) # 책의 제목을 담을 딕셔너리 books. books = {} # 책의 제목을 담는다. for _ in range(n): book = input() # 딕셔너리에 존재 하지 않는 책이라면 개수..
-
[백준] 1236 성 지키기백준 Online Judge 2021. 9. 14. 21:14
1236번: 성 지키기 첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다 www.acmicpc.net 문제 설명 모든 행과 열에 한 명 이상의 경비원이 있어야 한다. 입력 : 첫 번째 줄에는 행과 열의 수 그 이후부터 '.'은 빈칸, 'X'는 경비원 출력 : 필요한 경비원 수 # 행과 열의 개수 입력 받는다 n, m = map(int, input().split()) array = [] # 경비관의 유/무 여부를 입력 받는다. for _ in range(n): array.append(input()) # row, column에 처음 기본 값으로 0을 채워..
-
[백준] 11004 k번째 수백준 Online Judge 2021. 8. 31. 17:14
문제 해설 n개의 수를 오름차순으로 정렬 한 뒤, k 번째 수를 찾아라. 시간 복잡도 o(NlogN)의 정렬 알고리즘을 이용한다. 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net n, k = map(int, input().split()) array = list(map(int, input().split())) array = sorted(array) print(array[k-1]) GitHub - DAWUNHAN/Algorithms-and-DataStructure: Algorithms and DataStructure with Python Algorithms and D..
-
[백준] 2751 수 정렬하기 2백준 Online Judge 2021. 8. 31. 17:08
GitHub - DAWUNHAN/Algorithms-and-DataStructure: Algorithms and DataStructure with Python Algorithms and DataStructure with Python. Contribute to DAWUNHAN/Algorithms-and-DataStructure development by creating an account on GitHub. github.com 문제 해설 n개의 숫자를 입력 받은 뒤, 순서대로 출력하라. 데이터 개수가 최대 1,000,000개 일 때, 시간 복잡도 o(NlogN)의 정렬 알고리즘을 이용해야 한다. 병합 정렬을 직접 구현하는 방법 def merge_sort(array): if len(array)