binarysearch2 BOJ1777 순열복원 1777번 순열복원 순열의 길이 N과 inversion sequence가 주어지면 이를 복원하여 원본 순열을 찾는다. inversion sequence의 i번째 원소 = 원본 수열에서 i보다 뒤에 위치하고 i보다 작은 수의 개수 i보다 작은 수의 개수를 알고 있으니, 큰 수부터 원본 수열에서의 위치를 찾아주면 된다. 주어진 예시로 파악해보자 (inversion sequence = 반전 수열이라고 하자) N=8, 반전 수열 = 0 1 0 2 2 1 2 0 1. 반전 수열의 여덟 번째 원소 0이 의미하는 바는 원본 수열에서 8보다 뒤에 위치하고 8보다 작은 수는 0개라는 뜻 따라서 원본 수열에서 8은 가장 마지막 위치에 있는, 여덟 번째 원소이다. ⇒ 원본 수열 = _ _ _ _ _ _ _ 8 2. 이제 반.. 2022. 8. 18. 2021 카카오 채용연계형 인턴십 ① #3 표 편집 간단해 보이나 효율성을 통과하기 위해 배열 외의 자료구조를 선택해야 했음 set을 이용한 풀이도 가능하지만 fenwick tree로도 풀 수 있다해 풀어봤다. 은근히 이분탐색에서 헷갈렸던;; 어떤 L을 찾는지 명확히 해야 헷갈리지 않는다. 시험 볼 당시에는 set을 활용하려 했으나 iterator 활용을 잘 못해 실패했던 것 같다... fenwick tree와 이분탐색을 이용함. 더보기 #include #include #include using namespace std; int N; stack S; int fen[1000001]; void upd(int idx, bool add) { if (add) while (idx 2021. 8. 18. 이전 1 다음