주니어 개발자의 대나무숲

파라메트릭 서치 문제는 단독 문제로 나오기보다는 다른 알고리즘과 결합해서 출제되는 것 같습니다.파라메트릭 서치는 간단히 말하자면, (갓종만북의 표현을 빌려) 최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제로 바꾸어 푸는 것 이라고 할 수 있습니다. 지금은 이 표현이 와닿지 않을 수 있습니다. 간단한 그림을 통해 한 번 설명해보도록 하겠습니다. 다음과 같이 나이순으로 정렬된 사람들이 있습니다. 그리고 25살 이상이라면 소주를 좋아한다는 것이 증명되어 있다고 합니다. 그럼 이 중에서 소주를 좋아하는 나이가 가장 어린 사람은 누구일까요?? 물론 가장 간단한 방법은 앞에서부터 차례대로 "너 소주 좋아하니?"라고 물어보면서, 처음으로 "네!"라고 대답하는 사람을 찾는 ..

5. map 1) 정의인덱스로 int가 아닌 다른 자료형을 사용할 수 있는 배열(후에 사용법을 이해하기 편하도록 '배열'이라고 했지만, map의 내부적인 구조는 각 노드가 key와 value의 쌍으로 이루어진 '트리'입니다. 특히 검색, 삽입, 삭제 등의 속도를 빠르게 하기 위해 균형 이진 트리 중의 하나인 '레드 블랙 트리'로 구현되어 있습니다. 검색 속도가 특히 빠른데 이는 key를 기준으로 정렬된 상태이기 때문입니다.) 2) 용도연관 있는 두 값을 함께 묶어서 관리하되, 검색을 빠르게 하고 싶은 경우 (Ex. 만약 SNS상 사람들의 친구 관계를 그래프를 이용해 나타내고, 이 그래프에 여러가지 알고리즘들을 적용해 멋진 일들을 하고 싶다고 합시다. 일반적인 경우라면, 사람을 정점으로, 사람들 간의 친구..

PS를 배우기 전에 미리 알아두면 좋은 사항들이 있습니다.PS를 해본 사람들에겐 당연하지만, 처음 접하는 사람들에겐 전혀 당연하지 않은 사항들이라고 생각해 따로 글을 쓰게 되었습니다. 저 또한 처음엔 이런 점들을 잘 몰랐구요! PS를 처음 접하시는 분들에게 조금이라도 도움이 되길 바랍니다. 1. 전역변수 여태까지는 전역변수를 사용하면 코드 재사용시 프로그램의 안정성에 좋지 않다는 등의 이유로, 전역변수를 가급적이면 사용하지 않는 것이 좋다고 배워왔습니다. 하지만, PS를 할 때는 전역변수를 적극적으로 사용하는 것이 좋습니다. 예를 들어 보겠습니다. 어떤 배열(arr)이 있을 때, s번째 칸부터 e번째 칸까지의 합을 구하는 함수 sumOfArray가 있다고 해보겠습니다. 그러면, 함수 sumOfArray는..