오꾸오꾸(오늘도 꾸준히 오랫동안 꾸준히)

정렬 알고리즘 평균 시간 복잡도 공간 복잡도 특징 선택 정렬 O(N^2) O(N) 아이디어가 매우 간단 삽입 정렬 O(N^2) O(N) 데이터가 거의 정렬되어 있을 때는 가장 빠름 퀵 정렬 O(NlogN) O(N) 대부분의 경우에 가장 적합하며, 충분히 빠릅니다. 계수 정렬 O(N + K) O(N + K) 데이터의 크기가 한정되어 있는 경우에만 사용이 가능 하지만 매우 빠르게 동작 N, K = map(int, input().split()) # 5 3 a = list(map(int, input().split())) # 1 2 5 4 3 b = list(map(int, input().split())) # 5 5 6 6 5 for i in range(K): if a[i] < b[i]: a[i], b[i] = ..

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능 데이터의 개수가 N, 데이터(양수) 중 최댓값이 k일 때 최악의 경우에도 수행 시간 O(N + K)를 보장합니다. 데이터를 돌면서 그 값에 있는 인덱스의 count++해줍니다. # 모든 원소의 값이 0보다 크거나 같다고 가정 array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] # 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화) count = [0] * (max(array) + 1) for i in range(len(array)): count[array[i]] += 1 # 각 데이터에..

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나입니다. 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘입니다. 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정 그렇게 되면 pivot값의 위치가 중간으로 들어가게 되고 이제 pivot을 중심으로 왼쪽에 있는 값들을 퀵 정렬해주고 오른쪽에 있는 정렬을 퀵정렬 해줍니다. 퀵 정렬이 빠른 이유 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(NlogN)를 기대할 수 있습니다. 너비 X 높이 = N x logN = NlogN 퀵 정렬은 평균의 경우 O(NlogN)의 시간 복잡도를 가집니다. 하지..

삽입 정렬 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입합니다. 선택 정렬에 비해 구현 난이도가 높지만 일반적으로 더 효율적으로 동작 9를 7과 비교합니다. 7보다 더 크기 때문에 오른쪽에 위치에 놓습니다. 0을 9와 비교 9보다 작기 때문에 왼쪽으로 놓고 7과 비교해 작으니 왼쪽 5하고 비교하여 작기 때문에 왼쪽에 놓습니다. array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): for j in range(i, 0 , -1): # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법 if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동 array[j],array[j - 1] = array[j - 1], arra..

정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다. 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다. array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i + 1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] #스와프 print(array) 선택 정렬..

DFS는 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작 과정은 다음과 같다. 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다. 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다. 3. 더 이상의 2번의 과정을 수행할 수 없을 때까지 반복합니다. 스택 자료구조로 구현이 가능하다. def dfs(graph, v, visted): # 현재 노드를 방문 처리 visted[v] = True print(v, end =' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 f..

완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 파이썬에서 리스트 크기 파이썬에서의 고려 사항은 메모리의 제한이다. 대체로 테스트에서는 128~512MB로 메모리를 제한하는데 알고리즘 문제 중 수백만 개 이상의 데이터를 처리해야하는 문제가 출제되곤 한다. 데이터의 개수(리스트의 길이) 메모리 사용량 1,000 약 4KB 1,000,000 약 4MB 10,000,000 약 40MB 구현 문제에 접근하는 방법 일반적으로 알고리즘 문제에서의 2차원 공간은 행렬의 의미로 사용됩니다. 1. 상하 좌우 # N 입력받기 n = int(input()) x, y = 1, 1 plans = input().split() # L, R, U,..

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다. 그리디 해법은 그 정당성 분석이 중요합니다. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 5-7-9가 가장 큰 값을 가집니다. 하지만 그리드 알고리즘을 사용하면 5-10-4를 선택 됩니다. 문제 1이 될 때까지 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 합니다. 단, 두번째 연산은 N이 K로 나누어. 떨어질 때만 선택할 수 있습니다. - N에서 1을 뺍니다. - N을 K로 나눕니다. ​ 예를 들어 N이 17, K가 4라고 가정합니다. 이때 1번..

리스트의 인덱싱과 슬라이싱 a = [1,2,3,4,5,6 print(a[1:4]) 리스트 컴프리헨션 1. 리스트를 초기화하는 방법 중 하나 1. 대괄호 안에 조건문과 반복문을 적용하여 리스트를 초기화 할 수 있습니다. # 0부터 9까지의 수를 포함하는 리스트 array = [i for i in range(10)] print(array) n = 2 m = 3 array = [[0] * m for _ in range(n)] print(array) #[[0,0,0],[0,0,0]] 사전 자료형은 키(key)와 값(value)의 쌍을 데이터로 가지는 자료형 사전 자료형은 키와 값의 쌍을 데이터로 가지며, 원하는 '변경 불가능한(immutable) 자료형'을 키로 사용할 수 있습니다. 파이썬의 사전 자료형은 해시..