7개의 댓글이 있습니다.
-
-
Being -
지금 책이 없어서 그러는데 수직 거리(맨하탄 거리)의 합을 최소화하는 문제가 맞나요? 저런 문제들은 이런 식으로 생각하시면 편합니다.
- 음의 무한대 지점에서부터 한 칸씩 오른쪽으로 옮겨 온다고 생각해 봅시다.
- 맨 처음에는 모든 점이 전부 오른쪽에 있으니, 한 칸 옮겨 오면 거리가 무조건 감소할 것입니다.
- 이런 식으로 옮겨 오다 보면 가장 왼쪽의 점 위치까지 문제 없이 도달할 겁니다. 이 때부터는 거리가 감소하는 점 N-1개, 증가하는 점 1개가 있을 것입니다. N-1이 1보다 크거나 같으면, 여전히 오른쪽으로 옮기는 게 유리하겠지요.
- 이런 식으로 계속하다 보면 다른 점을 마주칠 것이고, 이 때부터는 증가하는 점 2개, 감소하는 점 N-2개가 될 것입니다.
- 언젠가는 증가한 점 개수가 감소하는 점 개수보다 많거나 같아질 것이고, 이때부터는 오른쪽으로 갈수록 거리가 증가함이 확실합니다.
- 따라서 거리의 합을 최소화하는 것은 양쪽으로 점을 비슷하게 분할하는 중간값 지점임을 알 수 있습니다.
11년 전 link
-
-
-
SungYeolWoo -
사진 찍어서 올려봤는데.. 이래도 되는지는 모르겠군요..ㅠㅠ먼저 친절한 댓글 너무 감사드립니다 : )
근데 처음 댓글을 보고 제가 아직 이해가 안되는 부분은..
왜? 음의 무한대 지점에서부터 한 칸씩 오른쪽으로 가는건지 모르겠습니다..제가 문제 자체를 이해 못한것 같군요.. 지금도 계속 읽고있네요..ㅠㅠ 신기하네요.. 어떻게 그렇게 접근이 가능한지...
11년 전 link
-
-
-
SungYeolWoo -
이렇게 응원해주시니 감사하네요! 열심히 질문하겠습니다^^
11년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
SungYeolWoo
우선 이러한 책을 알게되고 받아보게 되어서 먼저 감사하다는 느낌을 받았습니다^^
무엇보다~ 프로그래머가 되고자 하는 학생으로서 사실 이러한 알고리즘에 대한 문제해결은 속히 말하는 천재들...이나 할 것이라고 생각하고만 살았던 것이 사실입니다~
하지만 막상 이제 취업이 다가오고 하니, 이러한 요구사항이 필요한 기업들이 있다는 것을 알고나니 현실로 다가오더군요~
그래서 엄청 늦었다고 생각이 되지만, 용기내서 시작하려고 합니다!
아마 이제 질문을 자주 올리려고 노력하겠습니다! 그리고 생각보다 엄청 초딩(?)틱한 질문들이 올라오더라도 어디서부터 준비해야하는지에 대해서 가차없이 조언해주신다면 언제든지 받아들이고 열심히 하겠습니다.
또 제가 수학을 등하시 한지가 좀 오래되었습니다. 근데 수학적 개념은 필요하겠다 생각이 들어서, 중학교 수학책을 들여다 보고 있긴 한데.. 사실 시간이 많은 사람이 아니다보니.. 이렇게 하는 것이 프로그래밍을 하는데 있어서 도움이 되는지도 막연합니다.
(모든 부분이 필요한게 아니라면 어느 부분이 필요한지도 알면 좋겠습니다.. 통계라든지, 이산수학이라든지.. 어느부분을 배우면 좋다 뭐 이런식을 바라는건지도 모르겠네요^^)
아 그리고 실제적으로 질문을 드리고자 했던 부분들은 다음과 같습니다.
지금 2.3장 문제 해결 전략에서 격자 위에서 기존에 있던 점까지의 거리의 합을 최소화하는 위치 찾기 문제를 예시로 해주는 부분이 있습니다.
근데 저는 사실 왜 그림 2.1에서 X부분이 답이 되는지 봐도 모르겠습니다..ㅠㅠ 기본지식이 없는 상태에서 보려니.. 한글이지만 정말 무슨소리인지 아직 모르겠더군요.. 무엇을 참고하는 것이 좋으련지요?
11년 전