원

비트연산자 활용법 아래에 기록하는 비트연산자 활용법은 모두 암기해야 한다. 비트 연산 코드 idx번째 비트 끄기 S &= -(1

▶ 누적합(prefix sum) 알고리즘 누적합은 말 그대로 구간의 value를 누적합 형태로 구현하여 시간복잡도 측면에서 이득을 취하고자 하는 알고리즘이다. 일반적으로 사용되는 배열에 값을 저장하고 지정된 인덱스부터 하나씩 더해가는 방식은 최악의 경우 O(n^2)의 시간복잡도가 필요하기 때문에 입력 범위가 클 때 사용할 수 없다. 하지만 Prefix Sum방식의 누적합을 사용하면 입력과 동시에 누적합을 저장하고 필요한 구간의 값만 취하면 되기 때문에 O(n)으로 해결할 수 있다. 누적합은 문제에서 수열이 주어지고 어떤 구간의 합을 구해야할 때 쓰인다. 예를 들어 크기가 10인 배열에서 2번 index부터 8번 index 구간의 합을 구한다고 가정하면, 입력 후에 for문으로 다시 값을 구하는 것이 아닌..

문자열 관련 문제를 풀 때 C++의 경우 또는 을 사용 및 응용하여 대부분의 문제를 해결할 수 있다. 하지만 트라이 자료구조 또한 필수로 알아야한다. 트라이는 문자열을 효율적으로 처리하기 위한 트리 자료구조이다. 특히 "접두사"와 같은 단어가 문제에 등장하면 트라이를 우선 떠올려도 괜찮을 듯 하다. 트라이란, 트라이(Trie) : 문자열을 효율적으로 처리하기 위한 트리 자료구조 단어 S를 삽입/탐색/삭제할 때 모두 O(|S|) (|S|는 문자열 S의 길이) 문자열을 그냥 배열에 저장하는 것보다 최대 4 x 글자의 종류배 만큼 더 사용 (예를 들어 각 단어가 알파벳 대문자로만 구성되어 있을 경우(글자의 종류 = 26) 따라서 104배) 이론적인 시간복잡도와는 별개로 실제로는 트라이가 해시, 이진 검색 트리..

다익스트라(Dijkstra) 알고리즘은 동적 계획법을 활용한 대표적인 최단 경로 탐색 알고리즘(Shortest Path)이다. 흔히 인공위성 GPS 소프트웨어 등에서 가장 많이 사용된다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 다만 이 때 음의 간선을 포함할 수 없다. 다익스트라 알고리즘이 동적 계획법과 관련되어 있는 이유는 최단 거리는 여러 개의 최단 거리로 이루어져있기 때문이다. 작은 문제가 큰 문제의 부분 집합에 속해있다고 볼 수 있다. 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다. 간단한 예제 문제 풀이로 이해해본다. https://www.acmicpc.net/probl..

Disjoint Set Disjoint Set이란, 서로 중복되지 않는 부분 집합(서로소 집합)들로 나누어진 것을 의미한다. 집합을 구현하는 방법은 벡터, 배열, 연결리스트 등을 이용할 수 있으나 가장 효율적인 트리 구조를 이용하여 표현한다. Union Find Disjoint Set을 표현할 때 사용하는 알고리즘이 Union Find 알고리즘이다. ◎ Union(x, y) -> x가 속한 집합과 y과 속한 집합을 합치는 연산을 수행한다 ◎ Find(x) → x가 속한 집합의 대푯값을 반환하는 연산을 수행한다. x가 어떤 집합에 속해 있는지 찾아주는 연산으로 트리를 이용해서 구현하는 방법이 대부분이므로 대푯값은 루트 노트 번호를 의미한다 알고리즘의 진행상황을 처음부터 그림으로 한 번 살펴보자면 ① 초기 ..