Binary Search 배열에서 원하는 값의 위치를 O(log N) 만에 찾는 방법 ⇔ 순차탐색 O(N) 배열 내 원소가 정렬된 경우에만 사용 가능 정렬되지 않은 배열의 경우, 찾고자 하는 숫자의 개수가 적다면 순차탐색이 빠를 수 있음 아래는 찾고자 하는 값이 없는 경우 -1을, 있는 경우에는 해당 위치를 반환해주는 Binary Search 코드이다. up/down 게임과 유사한 방식으로 원하는 값의 위치를 찾아가는 것을 볼 수 있다. int binary_search(int target){ int low=1, mid, high=n; while(low

Next Permutation next permutation ! 말 그 대로 다음 순열을 찾는 방법이다. = 현재 순열의 상태에서 크기순으로(사전 순) 다음에 올 수 있는 순열을 생성 구현에 들어가기 전에 기억 할 것 첫 순열 = 오름차순 마지막 순열 = 내림차순 → 모든 수가 내림차순으로 정렬되어 있다면, 순열을 모두 만들어 낸 것이고, 따라서 종료 조건이다! 그렇다면, Next Permutation을 어떻게 구현할까? 1. 뒤에서부터 역방향으로 탐색하면서 교환위치( i-1 , 오름차순이 깨지는 부분)을 찾는다. 💡 오름차순이 깨지는 부분이 교환 위치인 이유 자 예를 들어 ` int a = {1, 4, 9, 8, 3, 2,1}; ` 배열이 있다고 하자. a[2] ~ a[6] 은 모두 내림차순으로 정렬되..

Union-Find Disjoint set (서로 중복되지 않는 부분 집합들로 나눠진 원소 정보를 저장/조작하는 자료구조)을 표현할 때 사용하는 알고리즘으로, 두 node가 같은 집합에 속하는지 판별할 때 유용하게 사용할 수 있다! 구현 1. 초기화 다음과 같이 모든 값이 자기 자신을 가리키도록 초기화해준다! 모든 값이 자기 집합의 대표값?이 되는 것이다. 처음에는 각 집합의 원소가 하나니까 어찌보면 당연한 일이다. int root[1000001]; for(int i=1; i>n>>m; for(int i=0; ioper>>a>>b; if(oper == 0) union_(a, b); else if(find_(a)==find_(b)) cout