선호:하다

문제를 풀 때 마다 검색하는 것 같아서 한 번 정리한다. 벡터 정렬하기 오름차순 정렬 #include using namespace std; vector v; int main(){ v.push_back(3); v.push_back(1); v.push_back(6); v.push_back(1); v.push_back(2); v.push_back(5); v.push_back(4); v.push_back(2); sort(v.begin(), v.end()); for(int i : v) cout

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() 힙에 원소가 들어오거..

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..