Computer Science

개요 얼마 전 백준에서 집합 자료형을 구현하는 문제를 보았습니다. 직접 구현하라고 하면 가물가물하면서 `std::set` 같은 컨테이너를 쓰는 것이 양심에 찔려서, 자료구조 공부도 다시 시작했습니다. 오늘은 가장 먼저 이진 탐색 트리(Binary Search Tree)를 살펴봅니다. 이진 탐색 트리란 정의와 성질 이진 탐색 트리는 이진 트리면서, 다음과 같은 재귀적인 성질을 가진 트리입니다. 이진 탐색 트리의 성질 노드를 기준으로 왼쪽 트리에 있는 노드들은 더 작은 키(key)를 가진다. 오른쪽 트리에 있는 노드들은 더 큰 키를 가진다. 성질에서 알 수 있듯, 이진 탐색 트리는 키-값(key-value)의 데이터를 저장하는 자료구조입니다. 이 글에서는 편의상 키와 값은 모두 정수이며, 두 값이 같다고 가..

문제 개요 백준 12015번 문제입니다. LIS(Longest Increasing Sequence)의 길이를 $O(n\log n)$ 시간에 구해야 하는 문제로, 동적 계획법을 사용한 $O(n^2)$ 풀이와는 다른 방법이 필요합니다. 이진 탐색을 사용하여, LIS가 될 수 있는 후보군을 계속 갱신하는 방식의 풀이를 소개합니다. 문제 분석 새로운 원소 조회 동적 계획법 풀이와 같이 앞에서부터 원소를 하나씩 조회합니다. 지금까지 조회한 원소가 2와 5라고 합시다. LIS는 `2, 5` 일 것입니다. 이제 다음 원소가 3이라고 합시다. 가능한 LIS는 `2, 3` 과 `2, 5` 의 두 가지입니다. 그런데 마지막 원소가 작은 편이 뒤에 나올 원소들을 LIS에 넣기에 더욱 유리하므로, `2, 3` 을 선택하기로 ..