알고리즘 (3) 썸네일형 리스트형 카카오, 라인 코딩테스트 주말동안 카카오와 라인 코딩테스트를 보았다. 혼자 여유롭게 문제를 푸는 느낌과는 다르게 압박감이 상당했다. 카카오는 7문제 5시간 라인은 6문제 3시간 이였는데, 카카오는 나름 난이도가 있는 문제다 보니 문제선택을 잘했어야 했는데, 1번과 2번을 풀고 5번이 풀만해보여서 도전을 해서 3시간반을 투자하고 못 풀어서 2시간쯤 지났을때부터는 이미 멘탈이 흔들려서 너무 힘들었다. 다른 쉬운문제도 충분히 있었는데 효율성에 쫄아서 보지 않았던 것이 함정... 라인은 앞에서부터 문제가 잘 풀려서 4번까지 1시간반만에 전부 해결해서 올솔을 노려볼만 했다. 그런데 역시 5번에서 시간이 조금씩 끌려 잡고있다가 남은 한시간반을 모두 투자했지만 실패... 딱 제출 하면서 틀린걸 깨달아서 진짜 1분만 이라는 아쉬움이 남았다. .. 백준 8986. 전봇대 기본적인 삼분탐색 문제, 처음엔 단순 이분법 parametric search로 푸는 문제인줄 알고 한참을 고민했다. 삼분탐색으로 풀 생각을 하고 삼분탐색에 대해 살짝 맛을 봤더니 삼분탐색도 이분탐색으로 하는 방법이 있길래 풀어보았다. 삼분탐색에 대한 정리는 https://mingnine9999.tistory.com/34에 해두었다. https://www.acmicpc.net/problem/8986 8986번: 전봇대 입력의 첫 줄은 전봇대의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 두 번째 줄에는 전봇대의 위치를 나타내는 N개의 서로 다른 x-좌표 xi(i = 0, ..., N-1)가 빈칸을 사이에 두고 오름차순으로 주어진다. xi는 www.acmicpc.net 전봇대들을 모두 같은 거리만큼 .. 삼분탐색..!!(Ternary search) 보통 이분탐색(binary search)에 대해서는 기본적으로 알고있는 경우가 대부분이다. 하지만 삼분탐색(ternary search)라면 어떨까?! 이분탐색은 정렬되어 있는 수열 속에서 원하는 값을 찾을 때 사용 할 수 있는 탐색 기법이다. 즉, 단조 증가 또는 단조 감소 수열에서 내가 원하는 값이 있는지 없는지를 판단하는 경우에 쓰인다. 삼분탐색은 조금 다른데 오목하거나 볼록한 수열에서 극값을 찾는 탐색이다. 하지만 오목 볼록이 여러번 반복되거나 평평한 (같은 값이 반복되는) 수열에서는 값을 찾을 수 없다. 예를들어, 그래프를 그렸을 때 밑에 그림처럼 나오는 수열에 적용 가능하다. 정석적인 삼분탐색의 방법은 극대값을 찾는다 했을 때, 양쪽끝을 기준으로 1/3지점과 2/3지점을 비교하여 둘 중 더 작거.. 이전 1 다음
