kyaryunha   6년 전

흡ㅂ... 안녕하세요..!! 문제 좀ㅁ 추천 받으러 왔습니다..!


어쩌다 NYPC 본선에 나가게 되서

(제 실력에 어떻게 나가게 된건진 의문.. 1스테이지+전체점수에 올인한 사람이 적었던 걸까요..) 


쨋든 준비 중인 사람입니다..!

(( 사실 원래 실력이 좋지 않은지라 준비 해도 그리 상탈것 같진  않지만, 그래도 준비 과정에서 실력이 조금이라도 향상될꺼고, 그것이면 만족 ))


다름이 아니라 작년도 3번 문제가 정확한 해답?이 있다기 보단, 머신러닝에 쓰이는 기법을 이용해서 풀어야 한다고 들었거든요.

EX 유전자 알고리즘이라던가.... 뭐 다양한 해법이 있겠.. 

어떤 짱짱 잘하시는 분 블로그 보니 SA이라는 (전 생전 처음듣는..!) 것으로 풀으셨다던데 그런 어려운 것까지 공부하고 가기엔 남은 시간이 3~4일 뿐인지라...



음ㅁ.. 그래서 그런 머신러닝(??)이나 유전자 알고리즘이라던가 쨋든 그런쪽 문제를 풀어보며 연습해 보려고 하는데요..! 

((주변 사람 말로는 일단 익히기 쉬운건 유전자 알고리즘이라 하더라고요..(사실인진 모르겠지만)))


쨋든 혹시 문제 추천해 주실수 있나요..!?  


백준에 있는 문제 중에서 머신러닝 스러운? 문제가 잘 안보이더라고요 ㅠㅠㅜ... 

백준 문제 중 추천해 주셔도 좋고, 그냥ㅇ 말로 설명해 주셔도 감사합니다..!


doju   6년 전

Simulated Annealing(SA)과 유전 알고리즘 둘 다 최적해를 찾기 힘든 문제에서 적당한 시간 안에 적당히 좋은 해를 찾아내는 방법들이기 때문에, 이런 알고리즘을 사용하는 문제는 일반적인 프로그래밍 대회에서는 잘 출제되지 않습니다.


Simulated Annealing

현재 상태와 비슷한 상태를 하나 만들고, 새로 만든 게 더 좋거나 좀 나쁘더라도 나중에 더 좋은 결과를 낼 가능성이 있다고 생각되면 그 상태를 취하는 방법입니다.
출제 의도가 이건지는 모르겠지만, BOJ에 이 방법으로 풀 수 있는 문제가 하나 있습니다. https://www.acmicpc.net/proble...

http://koosaga.com/3
https://algospot.com/forum/read/1211/


유전 알고리즘

유전자(상태)를 많이 만들어 놓고, 그 중 우수한 유전자 몇 개를 뽑은 뒤 적당히 변형시켜서 다음 세대의 유전자들을 만들어 나가는 방법입니다.
보통 유전자를 정의하기 쉬운 Travelling salesman problem, Max-Cut Problem이 꾸준히 유전알고리즘 강의 과제로 나옵니다(..).

https://www.youtube.com/watch?v=Yr_nRnqeDp0
http://www.aistudy.com/biology/genetic/operator_moon.htm


둘 다 개념 자체는 어렵지 않지만, 상태와 평가 함수를 어떻게 정의하느냐에 따라 결과의 품질이 갈릴 수 있습니다. 이런 문제가 대회에 나온다면 자신의 센스와 Dice God을 믿으세요.

kyaryunha   6년 전

@doju

헉ㄱ  코드포스 오렌지 색깔님이 답변 달아주셨.. (신기)(존경합니다..!)

넥슨프챌ㄹ에 올해에도 SA 가 나온단 보장은 없지만 그래도 공부 모드..! 그나저나 정올에도 SA가 나왔었다니 왠지 신기하군요..!

Dice God.. 뭔가 SA 짱어려운데 노력해서 할 수 있게 되면 주사위놀이처럼 재밌을 것 같군요..! 

Doju님 유용하고 좋은 답변 감사합니다 ㅠㅠ 열심히 읽어볼게요..! :)

댓글을 작성하려면 로그인해야 합니다.