자료구조 | 알고리즘

P vs NP 문제 : 컴퓨터가 답이 되는 몇 가지 경우는 빠르게 찾을 수 있지만, 최적의 답을 빠르게 찾을 수는 없는 모든 경우에 대한 문제 - P (Deterministic Polynomial time, 결정론적 다항 시간)다항식 시간복잡도를 가진 알고리즘으로 해결되는 문제 집합 (O(n), O(n²))P 클래스는 입력 크기에 대해 다항 시간 안에 결정론적 순차 기계에서 해결할 수 있는 모든 결정 문제들을 포함 - NP (Non-deterministic Polynomial time, 비결정론적 다항 시간)비결정적 다항식 시간 알고리즘으로 해결되는 문제 집합 (O(n!), O(2^n))NP 알고리즘은 주어진 해에 대해 'Yes'를 확인해야 하므로 결정 문제로 변형NP 클래스는 긍정적인 해답을 주어진 정..

비트마스크란? 이진수를 사용하는 컴퓨터의 연산 방식을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법이진수 0 또는 1을 사용하므로 하나의 비트가 표현할 수 있는 경우는 두 가지이다. 비트마스크의 장점1. 수행 시간이 빠르다. 비트마스크 연산은 비트 단위로 이루어져 대부분 O(1) 시간 복잡도로 처리된다. 비트마스크를 사용하면 비트의 개수만큼 원소를 다룰 수 있어, 연산 횟수가 적을 때는 속도 차이가 크지 않지만, 연산이 많아질수록 성능 차이가 확연히 커진다.  2.코드가 짧다. 비트 연산자를 사용해 다양한 집합 연산을 한 줄로 작성할 수 있어, 반복문이나 조건문을 사용하는 코드보다 훨씬 간결하게 표현할 수 있다. 3. 메모리 사용량이 적다. 비트가 10개면 각 비트가 두 가지 상태를 가질 수 있어서,..

우선순위 큐 - 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 - 데이터를 우선순위에 따라 처리하고 싶을 때 사용 자료구조 추출되는 데이터 스택(Stack) 가장 나중에 삽입된 데이터 큐(Queue) 가장 먼저 삽입된 데이터 우선순위 큐(Priority Queue) 가장 우선순위가 높은 데이터 우선순위 큐를 구현하는 법 1) 리스트를 이용하여 구현 2) 힙을 이용하여 구현 데이터의 개수가 N개일 때, 구현 방식에 따라서 시간 복잡도를 비교 우선순위 큐 구현방식 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙 O(log N) O(log N) 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일 (힙 정렬) - 시간 복잡도 O(NlogN) 힙의 특징 - 완전 이진 트리 자료구조..

리스트 컴프리헨션 - 리스트를 초기화하는 방법 중 하나 - 대괄호 안에 조건문과 반복문을 넣는 방식으로 리스트를 초기화할 수 있음 [ 0부터 19까지의 수 중 홀수만 포함하는 리스트 만들기 ] arr = [i for i in range(20) if i % 2==1] print(arr) #[1, 3, 5, 7, 9, 11, 13, 15, 17, 19] 리스트 컴프리헨션은 2차원 리스트를 초기화할 때 효과적으로 사용 n=3 m=4 arr = [[0] * m for _ in range(n)] print(arr) #[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] 특정 크기의 2차원 리스트를 초기화할 때에는 반드시 리스트 컴프리헨션을 이용해야 함 다음과 같이 2차원 리스트를 초기화한다..

서로소 집합 알고리즘 - 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 - 서로소: 공통 원소가 없는 두 집합 - union, find 2개의 연산으로 조작 가능 union 연산 (합집합) : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 find 연산 : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 서로소 집합 자료구조를 구현할 때는 트리 자료구조를 이용해 집합을 표현 서로소 집합 계산 알고리즘 1) A와 B 노드가 연결되어 있을 때 a) A와 B의 루트노드 a, b 를 각각 찾는다. b) a를 b의 부모 노드로 설정한다. (b가 a를 가리키도록 한다) // 일반적으로 더 번호가 작은 원소가 부모 노드가 되도록 구현 2) 모든 union 연산을 처리할 때까..

플로이드 워셜 알고리즘 모든지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용하는 알고리즘 - 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행 - 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요 X - 노드의 개수가 N개일 때 N번의 단계를 수행, 단계마다 O(N²) 연산을 통해 '현재 노드를 거쳐가는' 모든 경로를 고려 - 플로이드 워셜 알고리즘의 총 시간 복잡도는 O(N³) - 각 단계마다 특정한 노드 𝑘를 거쳐 가는 경우를 확인한다 𝑎에서 𝑏로 가는 최단 거리보다 𝑎에서 𝑘를 거쳐 𝑏로 가는 거리가 더 짧은지 검사 점화식 다익스트라 알고리즘과의 차이점 다익스트라 알고리즘에서는 출발 노드가 1개이므로 다른 모든 노드까지의 최단 거리를 저장하기 위해 1차..

최단 경로 알고리즘 : 가장 짧은 경로를 찾는 알고리즘 자주 사용되는 최단 경로 알고리즘 : 다익스트라 최단 경로, 플로이드 워셜 알고리즘 다익스트라 최단 경로 알고리즘 - 그래프의 특정 노드에서 출발해 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 - '음의 간선'이 없을 때 정상적으로 동작한다. - 기본적으로 그리디 알고리즘으로 분류된다. → 매번 '가장 비용이 적은 노드'를 선택해 임의의 과정을 반복하기 때문이다. 다익스트라 알고리즘 원리 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 위 과정에서 3번과 4번을 반복한다. 다익스트라 ..

다이나믹 프로그래밍 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 - 대표적인 예: 피보나치 수열 피보나치 수열은 다음과 같은 형태의 수열이다. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 점화식: 인접한 항들 사이의 관계식 피보나치 수열의 점화식 프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현할 수 있다. 𝑛번째 피보나치 수를 f(𝑛)라고 할 때 4번째 피보나치 수 f(4)를 구하는 과정은 다음과 같다 피보나치 함수 소스코드 # 피보나치 함수(Fibonacci Function)을 재귀함수로 구현 def fibo(x): if x == 1 or x == 2: return 1 return fibo(x - 1) + fibo(..