이쁜왕자 만쉐~~

cdpark 님이 정리해 놓은 글을 발췌합니다. NP : 답을 알려 주면, 그 답이 맞는지를 주어진 시간안에 검산해 볼 수 있는 문제 NP-hard : 답을 알려 주더라도, 그 답이 맞는지를 주어진 시간안에 검산할 수 없는 문제 TSP 문제를 다음과 같이 만들면, 이는 NP 입니다.. "50개의 도시를 1000km 이내로 다 돌 수 있느냐?" 만약 누군가가 "A-B-C-D.... 순서로 돌면 가능하다." 라고 알려 줬을 때, 짧은 시간안에 이를 확인해 볼 수 있습니다. 즉, 맞는 답을 알려 주면, 검산을 통한 확인이 가능하지요. 하지만, TSP 문제를 다음과 같이 만들면, 이는 NP-hard 가 됩니다.. "50개의 도시를 다 도는 가장 짧은 길은 몇 km 이냐?" 만약 누군가가 "A-B-C-D... 순..

Beam dectector 라는 문제를 풀다가 제일 마지막으로 하게된 일은, 아래와 같은 등식이 성립함을 증명하는 것이었다. 결국 코코싸싸 라는 오래된 기억을 끄집어 낸 덕분에 등식이 성립한다는 것을 보일 수 있었다. 정석이란게 쓸데가 있긴 있구나 라는 생각이 들게한 일이었다. 그렇다면,, 이런 수식은 왜 나왔냐 하면,, 문제를 풀면서 한사람은 이라는 이변수 함수식을 사용하였고, 나는 라는 식을 사용하였다. a = theta/2 , L = b 라고 바꿔서 쓰면,, 결국 뒤에 항만 서로 달라지게 된다. 그리고, 이 둘이 서로 같은 식이라는 것을 보이면서, 둘 다 맞는 식이라고 결론지은 것이다. 이는 deam detector 라는 문제의 답으로 제시된 bow and arrow 라는 형태의 답에 대한 최소값을..