포시코딩

계수 정렬 특정 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용 가능하다. 다른 정렬 알고리즘처럼 비교 후 위치를 변경하는 방식이 아니다. * 파이썬의 sort()나 sorted() 정렬 라이브러리는 퀵 정렬보다도 더 효과적이므로 별도의 요구 없이 단순 정렬하는 상황이라면 정렬 라이브러리를 쓰는게 더 좋다. 다만, 데이터의 범위가 한정되어 있으며 빠르게 동작해야 할 때 계수 정렬을 사용하는걸 추천 구현 arr = [4, 2, 3, 1]이 있을 때 arr에서 제일 큰 숫자 + 1 만큼의 길이를 가진 리스트를 하나 준비한다. (이유는 아래에서 설명) count = [0] * (max(arr)+1) arr을 돌며 값 ..

투 포인터 알고리즘 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘 연속된 40개의 숫자 중 2, 3, 4, 5, 6, 7을 지목해야 할 때 번호로 하나씩 부르기보다 '2부터 7까지'라고 부르는 방법 위 방법처럼 리스트에 담긴 데이터에 순차적으로 접근해야 할 때 '시작점'과 '끝점' 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. 예시 문제 문제 1. 특정한 합을 가지는 부분 연속 수열 찾기 예를 들어 arr = [1, 2, 3, 2, 5]의 리스트와 M = 5의 값이 주어졌을 때 부분 연속 수열 중 M의 값을 가지는 수열의 개수를 구하라 [1, 2, 3, 2, 5]에서 합이 5인 부분 연속 수열의 조합은 [2, 3], [3, 2], [5]와 같다. Pseudo..

개요 지금껏 시간복잡도에 대해선 무엇인지, 어떻게 구하는지에 대해서만 알았지 구체적으로 어떤 상황에 쓰이는지는 적절한 상황이 없었는데 코딩테스트를 준비하며 시간 제한, 메모리 제한 등과 함께 같이 제시된 조건들을 기준으로 시간복잡도를 생각해 어떤 알고리즘을 사용할 수 있을지 유추하기도 한다는 정보를 알게 되었다. 시간복잡도 O(1) 상수 시간(Constant time) O(log N) 로그 시간(Log time) O(N) 선형 시간 O(N log N) 로그 선형 시간 O(N^2) 이차 시간 O(N^3) 삼차 시간 O(2^n) 지수 시간 위는 자주 사용되는 시간복잡도로, 위쪽일수록 빠르다. 컴퓨터 과학에서 특정 알고리즘의 시간복잡도가 O(N^k)일 때, 이를 '다항 시간에 동작하는 알고리즘' 이라고 말한다..

크루스칼 알고리즘(Kruskal's algorithm) 탐욕 알고리즘을 기반으로 한다. 모든 정점을 독립적인 집합으로 만든다. 모든 간선을 비용(가중치)을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다. 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다. (사이클이 생기지 않도록) 간단히 말해서, 모든 정점을 리스트로 만든 후 비용이 적은 간선부터 하나씩 연결하되 사이클이 생기지 않게 하면 된다. 언제까지? 모든 노드들이 연결될 때까지 과정 아래와 같은 그래프가 있다고 가정할 때, 크루스칼 알고리즘으로 최소 신장 트리를 구하는 과정에 대해 알아보자 1. 가장 가중치가 작은 간선은 5의 가중치를 가진 A-D, C-E가 있다. 뭘 먼저 선택하든 상관없지만 우선 A..

신장 트리(Spanning Tree) Spanning Tree 또는 신장 트리. Spanning Tree가 더 많이 사용된다. 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프를 의미 신장 트리의 조건 본래의 그래프의 모든 노드를 포함 모든 노드가 서로 연결 트리의 속성을 만족(사이클이 존재하지 않음) 최소 신장 트리(MST) Minimum Spanning Tree, MST라고 불린다. 가능한 신장 트리(Spanning Tree)중에서, 사용된 간선들의 가중치 합이 최소인 Spanning Tree를 지칭한다. 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재한다. 대표적인 최소 신장 트리 알고리즘은 아래와 같다. 크루스칼 알고리즘(Kruskal's algorithm)..

추가사항 input() -> sys.stdin.readline() print() -> sys.stdout.write() 백준 문제의 입력값을 받거나 출력할 때 input(), print() 대신 sys를 import해서 쓰는게 훨씬 효율이 좋다. 개요 첫째 줄에 수의 개수 N이 주어지고 둘째 줄부터 N개의 줄에는 수가 주어질 때 위의 문장으로 시작하는 문제를 본 적이 있을 것이다. 백준을 접한지 얼마 안된 나는 이 입력값 받는거부터가 멘붕이었는데 그 방법에 대해 알아보자 첫 입력을 N으로 지정하는 것까진 똑같다. 그 후의 입력값들을 어떻게 다룰거냐에 따라 코드가 달라지긴 하는데 나는 리스트에 넣어볼거임 먼저 빈 리스트를 준비한다. arr = [] 이후 for문을 N번 돌며 input()을 받아 arr에 ..

백트래킹이란? 백트래킹 또는 퇴각검색이라고 불린다. 기법의 한 종류 제약 조건 만족 문제(Constraint Satisfaction Problem)에서 해를 찾기 위한 전략 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack하고, 바로 다른 후보군으로 넘어가며 결국 최적의 해를 찾는 방법 실제 구현 시, 고려할 수 있는 모든 경우의 수(후보군)를 상태 공간 트리(State Space Tree)를 통해 표현한다. 각 후보군을 DFS 방식으로 확인 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 곳으로 바로 넘어가서 다시 탐색 Promising: 해당 루트가 조건에 맞는지 검사하는 기법 Pruning..

최단 경로 문제란? 두 노드를 잇는 가장 짧은 경로를 찾는 문제 가중치 그래프(Weighted Graph)에서 간선(Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적 문제 종류 단일 출발 및 단일 도착 그래프 내의 특정 노드 u에서 출발, 또 다른 특정 노드 v에 도착하는 가장 짧은 경로를 찾는 문제 단일 출발 그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제 출발점이 A라고 한다면 A가 아닌 각각 다른 노드들 간의 최단 경로를 찾는걸 의미 다익스트라 알고리즘이 여기에 해당됨 전체 쌍(all-pair) 그래프 내의 모든 노드 쌍(u, v)에 대한 최단 경로를 찾는 문제 다익스트라 알고리즘 첫 정점을 기준으로 연결되어 있는 정점들을 추가해가며 최단..

자료구조 손코딩 배열 큐 스택 링크드리스트 해쉬 트리 힙 그래프 기본 알고리즘 정렬 버블 삽입 선택 퀵 병합 계수 이진 탐색 최대공약수 공식 소수 판별 + 에라토스테네스의 체 BFS, DFS 구현 코드 순열, 조합 구현 코드 최단 경로(다익스트라) 알고리즘 머리에 박아넣자

에라토스테네스의 체란? 2부터 주어진 숫자까지의 소수들을 찾는 방법으로 고대 그리스 수학자 에라토스테네스가 발견하였다. 원리는 2부터 주어진 숫자까지 모든 구간의 수를 나열한 후 2부터 시작해 발견되는 소수의 배수를 지워나가는 방식으로 소수를 찾는다. 자세한 방법은 위키백과에 나와있다. - [링크] 코드 1. 자신을 포함 안시키는 경우 def prime_list(n): # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주) sieve = [True] * n # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사 m = int(n ** 0.5) for i in range(2, m + 1): if sieve[i] == True: # i가 소수인 경우 for j in ran..