Algorithm/Binary Search Tree

[백준 19700번] 수업 (C++)

https://www.acmicpc.net/problem/19700 19700번: 수업 키가 188cm, 154cm인 학생들을 한 팀으로, 키가 180cm, 161cm인 학생들을 한 팀으로, 키가 172cm인 학생을 혼자 팀으로 묶으면 총 3개의 팀을 구성할 수 있다. 더 적은 갯수의 팀으로 학생들을 묶을 수 있 www.acmicpc.net 수업 문제는 그리디와 이진검색트리를 이용하여 해결할 수 있습니다. 학생의 키가 중복되지 않기 때문에, 키가 큰 사람부터 그룹에 넣어주면, 먼저 그룹이 할당된 수강생들의 키는 현재 그룹을 할당하려는 수강생보다 키가 큽니다. 따라서, i번째 학생은 그룹의 크기가 Ki보다 작은 그룹 중 하나에 할당시켜주면 됩니다. 하지만, 그룹의 수를 최소로 만들어 주어야하기 때문에, K..

[백준 23326번] 홍대 투어리스트 (C++)

https://www.acmicpc.net/problem/23326 23326번: 홍익 투어리스트 도현이는 홍익 투어리스트가 되어 홍익대학교를 견학하려고 한다. 홍익대학교는 $N$개의 구역이 원형으로 배치된 모습이다. $1$번 구역에서 시계 방향으로 각각 $2$번, ... , $N$번 구역이 존재하고, www.acmicpc.net 홍익 투어리스트 문제는 이진 검색 트리를 이용하여 해결할 수 있습니다. 명소의 위치만 이진 검색 트리에 저장해주면 됩니다. 1번 연산 : 이진 검색 트리에 존재한다면, 제거하고, 존재하지 않는다면, 명소로 추가, 시간 복잡도 : O(logN) 2번 연산 : 도현이의 위치만 이동, 시간 복잡도 : O(1) 3번 연산 : lower_bound()를 이용하여, 가장 가까운 명소의 위..

[백준 21939번] 문제 추천 시스템 Version 1 (C++)

https://www.acmicpc.net/problem/21939 21939번: 문제 추천 시스템 Version 1 tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령 www.acmicpc.net 문제 추천 시스템은 이진 검색 트리를 이용하여 해결할 수 있습니다. 이진 검색 트리를 이용하면, 최대/최소값 구하기, 삽입, 삭제을 모두 O(logN)에 수행할 수 있습니다. 또한, 이진 검색 트리에 {l, p}를 삽입하면, 먼저, 난이도를 기준으로 정렬하고, 난이도가 같을 땐 문제 번호로 정렬하므로, 마지막 원소가 난이도가 가장 높으면서, 번호가 가장 큰 번호입니다..

[백준 1202번] 보석 도둑 (C++)

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 보석 도둑 문제는 이진검색트리를 이용하여 해결할 수 있습니다. 훔칠 수 있는 보석의 가격을 구해야하는데, 가방에는 최대 한 개의 보석만 넣을 수 있습니다. 가방에 넣을 수 있는 보석 중 가장 가치가 큰 것을 선택하면 됩니다. 그럼 어느 가방에 먼저 넣어야할까요? 아래 예에서, 가방에 담을 수 있는 최대 무게가 가장 무거운 가방부터 넣어보..