터너리서치 썸네일형 리스트형 TopCoder SRM 426 고수들이 하나둘씩 SRM을 시작하게 된 것인지 우리나라에 옐로우 레이팅을 가지신 분들이 늘어나고 있다. 오늘 SRM에는 우리나라에서 DIV1에 25명이 참가했다. 이번 문제들은 디스크립션을 이해하기가 참 난해했던 것 같다. 영어는 해석을 다 했으나 무슨말이지 잘 이해가 안되서 문제를 완전히 이해하는데 20분정도가 걸렸다. 문제를 이해하고 나니 쉬운 문제였는데 안타깝게도 점수는 이미 바닥을 향해 가고 있었다. 250문제는 간단한 시뮬레이션과 소팅을 결합해서 해결할 수 있는 문제였고 500은 터너리서치로 풀 수 있는 문제였다. 1000은 그래프이론을 적용해야 할 것 같은데 역시 잘 모르겠다. 신 petr가 상당히 부진한 모습을 보이며 62등을 했다 250 - Shuffling Machine 카드를 셔플링 하.. 더보기 Ternary Search Ternary Search(터너리 서치)는 함수의 최대나 최소점을 찾는 알고리즘으로 바이너리서치와 그 동작방법이 비슷하다. 터너리 서치로 최대점을 찾을 수 있는 함수는 최대점을 기준으로 왼쪽은 단조증가 오른쪽은 단조감소 해야한다. 마찬가지로 최소점을 찾을 수 있는 함수는 최소점을 기준으로 왼쪽은 단조감소 오른쪽은 단조증가 해야한다. 다시말해 지역 곡소점이나 극대점이 반드시 하나 존재해야 하고 이 점이 전역 최대나 최소점이 되어야 한다. 최대점을 찾아보자 a < b 인 두 점 a, b 가 있고 함수 f(x)의 최대점이 a와 b사이에 있다고 했을 때 a < a' < b' < b 인 a'과 b'을 잡을 수 있다. 이때 f(a') < f(b') 이라면 [a, a'] 구간은 단조증가하고 이 구간에 f(b') 보다.. 더보기 이전 1 다음
