선호:하다

파이썬에서는 이진 탐색을 쉽게 구현할 수 있도록 bisect 라이브러리를 제공한다. bisect 라이브러리는 정렬된 배열에서 특정한 원소를 찾아야 할 때 매우 효과적으로 사용된다. bisect 라이브러리에서는 bisect_left() 함수와 bisect_right() 함수가 가장 중요하게 사용되며, 이 두 함수는 모두 시간 복잡도 O(logN)에 동작한다. bisect_left(array, x): 정렬된 순서를 유지하면서 리스트 array에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는다. bisect_right(array, x): 정렬된 순서를 유지하면서 리스트 array에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는다. 예를 들어 정렬된 리스트 [1, 2, 5, 5, 7]이 있고 새롭게 5를 삽입하려..

순차 탐색(Sequential Search) 이진 탐색을 알아보기 전에, 가장 기본적인 탐색 방법으로 데이터를 차례대로 하나씩 확인하며 탐색하는 순차 탐색이 있다. 순차 탐색은 구현이 매우 쉽고 리스트에서 특정한 값의 원소의 개수를 세는 count() 메서드도 내부적으로 순차 탐색을 이용한다. 순차 탐색은 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인하는 것이 특징이다. 따라서 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 순차 탐색의 시간 복잡도는 O(N)이다. 이진 탐색(Binary Search) 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 무작위 일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 ..

파이썬의 collections 라이브러리는 유용한 자료구조를 제공하는 표준 라이브러리이다. collections 라이브러리의 기능 중에서 코딩 테스트에서 유용하게 사용되는 클래스인 deque와 Counter를 정리해보자. deque 파이썬에서는 deque를 사용해 큐를 구현한다. 별도로 제공되는 Queue 라이브러리가 있지만 일반적인 큐 자료구조를 구현하는 라이브러리가 아니기 때문에 주로 deque를 이용해 큐를 구현한다. 리스트 자료형과 deque를 비교하면 다음과 같다. 리스트 deque 가장 앞쪽에 원소 추가 O(N) O(1) 가장 뒤쪽에 원소 추가 O(1) O(1) 가장 앞쪽 원소 제거 O(N) O(1) 가장 뒤쪽 원소 제거 O(1) O(1) 리스트 자료형은 원소를 추가 또는 제거할 때 각각 ap..

https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net import sys from collections import Counter n = int(sys.stdin.readline()) data = [] for i in range(n): data.append(int(sys.stdin.readline())) data.sort() avg = sum(data) / len(data) # 산술 평균 mid = data[(n - 1) // 2] # 중앙값 most_nums =..

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net import sys import heapq n = int(input()) heap = [] for i in range(n): data = int(sys.stdin.readline()) heapq.heappush(heap, data) result = 0 while len(heap) != 1: one = heapq.heappop(heap) two = heapq.heappop(heap) ..

우선순위 큐(Priority Queue) 우선순위 큐는 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조이다. 데이터를 자료구조에 넣었다가 우선순위가 높은 순서로 처리하고 싶을 때 사용한다. 우선순위 큐는 리스트로 구현하거나 힙(Heap) 자료구조를 이용하여 구현할 수 있다. 먼저 힙을 통해 구현하는 방법을 알기 위해 힙 자료구조에 대해서 알아보자. 힙(Heap) - 힙이란 완전 이진 트리의 일종으로, 부모 노드의 값이 항상 자식 노드들의 값보다 크거나, 작아야 한다. - 루트 노드가 가장 큰 값을 가지면 최대 힙(Max Heap), 루트 노드가 가장 작은 값을 가지면 최소 힙(Min Heap)이라고 한다. - 힙에서는 항상 루트 노드를 제거한다. 힙 구성 함수 heapify() 힙에 원소가 들어오거..

복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도이다. 복잡도는 시간 복잡도와 공간 복잡도로 나눌 수 있다. 시간 복잡도(Time Complexity)는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미 공간 복잡도(Space Complexity)는 특정한 크기의 입력해 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미 같은 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다. 보통 시간 복잡도와 공간 복잡도는 일종의 거래 관계가 성립하여 메모리를 더 많이 사용하는 대신 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다. 이때 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가 종종 ..

https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net import sys n = int(sys.stdin.readline()) data = [] for i in range(n): temp = list(sys.stdin.readline().rstrip().split()) data.append((temp[0], int(temp[1]), int(temp[2]), int(temp[3]))) data.sort(key = lambda x:..

정렬이란, 섞여 있는 데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다. 정렬 알고리즘은 일반적으로 O(N^2)과 O(NlogN) 사이의 시간 복잡도를 가지며 특수한 경우 O(N)인 경우도 있다. 다양한 정렬 알고리즘에 대해서 정리해보자. (모든 예시는 오름차순 정렬을 기준으로 한다) 평균적으로 O(N^2)의 시간 복잡도를 갖는 정렬 알고리즘 1. 선택 정렬(Selection Sort) - 현재 정렬되지 않은 데이터 중에서 가장 작은 데이터를 선택하여 가장 왼쪽의 데이터와 바꾼다. - 맨 왼쪽 데이터를 제외한 데이터에 대해서 선택 정렬을 반복한다. (하나의 원소만 남을 때까지) array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): m..

https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net import sys from collections import deque n, k = map(int, input().split()) graph = [list(map(int, sys.stdin.readline().rstrip().split())) for i in range(n)] s, x_result, y_result = map(int, input().split()) ..