Algorithm

저장하고자 하는 개수 크기로 할당가능한 공간복잡도 O(n) 인 fenwick tree 가 있다. BIT(Binary Indexed Tree) 라고도 한다.

배열 A, B, C, D 에서 각 1개씩 골라 4개의 합이 0 이 되는 경우의 수를 구하는 문제이다. 배열의 최대 크기는 4,000 이고 배열에 들어있는 정수의 절대값은 최대 2^28

N X M 행렬에서 최대 k개의 벽을 부수며 (N, M) 지점으로 갈 수 있는 최소 비용을 구하는 문제이다. 단, 한칸 이동시 낮과 밤이 바뀌며, 낮에만 벽을 부술 수 있다. 2가지

Queue 는 FIFO (first in first out) 로 들어온 순서로 정렬된다. 이와 달리 Priority Queue 는 우선 순위가 높은 순서대로 정렬된다. root node 의 우선 순위가 제일 높기 때문에 설정한 우선 순위에 따라 원하는 값을 O(1) 시

각 정점이 자기 자신과 모든 인접한 정점을 지배한다고 할 때 그래프의 모든 정점을 지배하는 정점의 부분집합을 dominating set 이라고 한다.

Alice 와 Bob 은 초기 값과 n 개의 수로 덧셈과 XOR 연산하여 target 값을 누가 만들 수 있는지 구하는 문제이다. 위와 같이 n 개의 수에 대한 모든 경우를 탐색하여 찾고자 하는 target 값과 같은지 판별할 수 있다.

경우의 수가 많아 bruteforce 로 탐색이 불가능할 때 반으로 쪼개 경우의 수를 최대한 줄이는 meet in the middle 알고리즘을 적용하면 된다.

첫 번째 꽃집에서는 장미 A개를 B원에 팔고, 두 번째 꽃집에서는 장미 C개를 D원에 팔 때 2개의 꽃집에서 N개의 장미를 사기위한 최소 금액을 구하는 문제이다. 묶음으로 판매하기 때문에

주어진 소수들 중에서 몇 개를 곱해 얻게 되는 수들 중 오름차순으로 N 번째 수를 찾는 문제이다. 곱하는 소수들을 선택할 때에는 같은 수를 선택해도 되며, N 번째 수를 세는 과정에 주어진