세그먼트 트리란?세그먼트 트리는 구간의 합, 구간의 최솟값, 구간의 최댓값등을 빠르게 구할 때 사용합니다. 구간내의 다양한 값들을 구할 수 있고, 업데이트 되더라도 몇개의 숫자만 업데이트 하면 되기 때문에 유용하게 사용할 수 있습니다. 배열을 이진 트리처럼 분할하여 트리 형태로 표현각 노드는 특정 구간을 나타내고, 그 구간의 정보를 저장 트리 만들기어떠한 데이터들이 주어지고 그 데이터의 구간 합을 구하는 문제라면 누적합을 사용하지만 중간 중간 값이 업데이트 되거나, 합계가 아닌 최대값, 최소값등을 구해야 한다면 세그먼트 트리를 사용하면 됩니다. 이렇게 숫자들이 있습니다. 이 숫자들의 구간 합을 구하기 위해서 2개씩 합계를 구하겠습니다. 지금은 짝수개이기 때문에 2개씩 합계를 구할 수 있지만 홀수개인 ..

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번을 반복한다. 다익스트라 ..