마스터 정리 https://jcdgods.tistory.com/380 [알고리즘] 시간 복잡도 계산 / 마스터 정리 시간 복잡도 계산, Master's theorem / 마스터 정리 1. 시간 복잡도 시간 복잡도란? 특정한 프로그램의 실제 동작 시간이 아닌, 입력 데이터의 크기 n에 대하여 기본적 연산의 횟수를 측정하는 것을 의 jcdgods.tistory.com 이분 탐색 https://www.acmicpc.net/blog/view/109 이분 탐색(Binary Search) 헷갈리지 않게 구현하기 개요 이분 탐색은 off-by-one error가 발생하기 쉬워서 늘 헷갈립니다. 이분 탐색 문제를 풀다보면 탈출 조건으로 lo

집합의 표현 집합을 표현하는 여러가지 방법 중에 비트를 이용하는 방법이 있다. 만약 64비트 정수를 쓴다면 원소의 개수가 64개보다 작은 집합을 나타낼 수 있다. 집합을 아래와 같이 비트로 표현할 수 있다. {1, 2, 3, 4, 5} -> 11111 {2, 3, 4, 5} -> 11110 {1, 3, 5} -> 10101 i 번째 비트만 1로 바꾸기 - or 연산 set = set | (1 0010 i 번째 비트만 0로 바꾸기 - and 연산 set = set & ~(1 1111 & 1101 -> 1101 i 번째 비트만 뒤집기 - xor 연산 set = set ^ (1 1101 i 번째 비트가 1인지 0인지 확인 set & 1 0100 -> 결과값 != 0 -> i번째 비트가 1 i번째 비트만 0으로..

수의 범위가 매우 큰 상황에서 수의 값에 무관하게 좌표들 사이의 대소만 알면 될 때, 좌표 압축을 이용하면 수의 범위를 줄일 수 있다. 1. 좌표 압축을 할 배열을 임시의 배열에 중복이 없고 정렬된 상태로 만들어 놓는다. 2. 압축할 배열의 각 수들이 임시의 배열에 몇 번째 인덱스에 해당하는 수인지 찾으면 된다. 임시의 배열은 정렬된 상태이기 때문에 이분 탐색을 이용하여 O(logN)에 찾을 수 있다. C++에서 좌표 압축을 구현할 때에는 주로 std::sort, std::unique 함수로 1번을 수행하고, std::lower_bound 함수를 이용하여 2번을 수행한다. 가지고 있는 모든 수의 값을 저장한 임시의 배열을 정렬한 후 unique 함수를 이용하여 중복되는 수를 모두 제거하고, lower_b..