선호:하다

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

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

복잡도(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()) ..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net import sys n, m = map(int, input().split()) graph = [list(map(int, sys.stdin.readline().rstrip().split())) for i in range(n)] temp = [[0] * m for i in range(n)] cnt = 0 result = 0 dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] def virus(x,..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net import sys n = int(input()) graph = [list(map(int, sys.stdin.readline().rstrip())) for i in range(n)] visited = [[False] * n for i in range(n)] num = 1 result = [] cnt = 0 def dfs(x,y): global cnt if 0

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net from collections import deque import sys n, m, k, x = map(int,input().split()) graph = [[] for i in range(n + 1)] distance = [-1] * (n + 1) check = False def bfs(x): queue = deque([x..