durano   3년 전

안녕하세요. 며칠전부터 백준이라는 좋은 사이트를 알게되어 하루에 꽤 많은시간을 문제푸는데에 사용하고있는 초보입니다.

제가 이렇게 따로 글을 올리는이유는.. 문제 해결방안에 대한 고민때문입니다.

사이트를 알게된 요 며칠동안 20~30 문제 가량을 풀어봤는데,  물론 그중에는 쉽게 풀었던 문제도 있었지만, 정말많은 시간을 투자해서 겨우겨우 풀거나, 아예 접근조차 하지 못한 문제들도 있었습니다.

제가 고민하고있는 것은  '정말많은 시간을 투자해서 겨우겨우 푼 문제' 에 대한 것입니다.

일단 지금까지 저는 문제풀때 약간의 실마리라도 보이면 어떻게든 문제를 해결하려고 그 문제를 몇시간이고 고민하다가 결국 풀어오긴 했습니다. 했습니다만.. 제출을 하고 맞다는것을 확인하면 제가 풀었던 방식 이외에 어떤방식이 있는지 확인하기 위하여 다른사람이 작성한 코드를 보는데, 풀었다는 기쁨도 잠시 허탈해지는 기분이 들 때가 많습니다. 이걸 이렇게 짧고 효율적으로 푸는것이 가능하구나.. 하고요. 또 그럴때마다 제 자신이 초라해보이기도 합니다..ㅠㅠ

1. 잘 풀리지 않는 문제를 두고 최대 몇시간까지 고민해봐야 할까요?

2. 어떤 문제를 푸는데에 있어서 가장 효율적인 방법이 있지 않습니까? 고수분들은 문제를 딱 봤을 때 ' 아, 이건 이러이러한 방식으로 풀면 쉽게 풀리겠구나.' 이렇게 효율적인 방법을 바로바로 떠올리시나요? 아니면 이것도 해보고 저것도 해보다가 좋은 방식을 찾으시나요?

3. 제 문제는 문제를 풀 때 내가 지금 접근하고있는 이 방식이 효율적이다, 효율적이지 않다라는것을 모른다는 것입니다. 그래서 일단 어떻게든시작하고 보는데, 이게 좋지않은 습관일까요?

4. 푸는 문제가 늘어날수록 더욱 잘 느껴지는것은, 이쪽분야에는 정말 천재인 사람들이 많다는 것입니다.ㅠㅠ 과연 제가 문제를 계속 푼다고해서 그분들을 따라가는것이 가능할까요? 문제를 풀면 풀수록 왜 이렇게 부정적인 생각이 드는건지 모르겠습니다..

두서없이 쓰긴 했는데, 제가 가지고있는 고민이 뭔지 대충 감이 오시리라 믿습니다.. 또한, 앞으로 공부하는데 있어서 조언이나 쓰디쓴 팩트폭력 날려주시면 감사하겠습니다 ㅠㅠ..

chogahui05   3년 전

나머지는 집 가서 답변해 드릴게요. 좀.. 길게 답변해야 할 거 같은데 시간이 허락치 않네요.

여기서는 걍 요약본만..


1. 보통 1시간 정도로 잡습니다만. 전 아예 4-5개월 뒤에 다시 풀어버립니다.

2. 많이 풀면 바로 보이겠죠..??

3. 일단 처음에는 많이 삽질해 보는 게 좋다고 생각해요.

4. 부정적인 생각이라. 사실 저도 못 푸는 거 엄청나게 많아요.

조금 어려운 문제들을 하나 하나씩 풀어보면 못 푸는 문제가 하나씩 줄어들겠죠..

chogahui05   3년 전

이건 어디까지나 제 개인적인 생각이니까. 그냥 참고만 해 주시면 좋을 거 같아요.


1번. 문제가 안 풀릴 때는 어느 정도까지 고민해 봐야 할까요? 제너럴한 문제는 1시간 정도.

그런데. 여기서 약간 벗어난 경우가 있어요.

예를 들어서.. 사람들이 많이 푸셨지만 사실 어려운 편에 속하는 이분 탐색의 놀이공원이라던지..

아니면 굉장한 학생 등이 있겠지요. 아무튼 조금만 생각해 보면 풀릴 수 있을 거 같은데.. 이런 것들 있잖아요.

하루나 이틀 정도 고민을 해 보세요.

그래도 안 풀리신다면 물어보세요. 한 두개 정도는 그렇게 공부하셔도 괜찮습니다.

몇 개월 뒤에는 그 문제에 대해서 도움 안 받고 다시 한 번 풀어보시고요.


그런데 이런 경우가 있어요. 몇 가지를 예로 들어볼게요.


어? 이 알고리즘으로는 풀릴 거 같은데 안 풀리네?

예를 들어서. 제가 최근에 리벤지 한 것 중에서 2370번 시장 선거 포스터가 있겠군요.

사실 Lazy 세그먼트를 배우면 정말 쉽게 풀 수 있는 문제였는데.

제가 그걸 안 배우기도 했고. 그걸 안 쓰고 풀고 싶었습니다.


계속 고민해 보시는 거죠. 선분의 특성을 어떻게 잘 이용하면 Lazy를 안 쓰고도 풀지?

그러면 선분의 특성이 무엇일까? 대충 이런 식으로요.

그러시다 보면 문제를 다는 풀지 못하시더라도 약간.. 그러니까 0.00001%라도 푸시게 되겠죠.

그게 모이고 모이다 보면.. 번뜩 해법이 떠오르실 때가 있을 겁니다. 그 때 푸시면 되어요.

푸시고 나서. 다른 사람 코드를 볼 수 있어요. 한 번 보세요.

지나치게 어렵게 풀었다 싶다. 그러면 보시는 것도 분명히 도움은 될 거 같아요. 그러면서 배우셔야 할 것을 찾는 거죠.

그러니까 제 상황을 예로 들면 저는 Lazy 기법을 적용한 세그 트리를 배워야겠네요..

전 선분의 특성을 이용해서 너무 어렵게 풀었으니까..


많이 벗어나 보이는 경우가 문제일 수 있습니다.

예를 들어서.. 1112번 진법 변환이라던지. 이런 건 사실 딱히.. 뭐라고 설명을 하기도 그렇고. ^^;;

아직은 상당히 극단적인 예인 거 같은데.

더 제너럴한 예를 들면. 습격자 초라기. 이 친구가 원형 dp에요.

분명 처음 하신다면 많이 벗어나 보이실 겁니다.

그런 경우에는 비슷한 유형의 문제들을 찾아서 먼저 풀어보시는 게 도움이 될 수도 있어요.

예를 들어서 초라기와 비슷한 건 색상환 정도 되겠네요..

질문 게시판에. 지금 이런 문제 못 풀겠는데요.. 혹시 비슷한 유형의 문제가 있나요?

라고 물어보신다면 누군가는 상당히 친절하게 답변해 주실 겁니다.

chogahui05   3년 전

2번하고 3번은 비슷한 답변이 나올 거 같으니까 몰아서 답변 드릴게요.

고수 분들은 많이 푸셨으니까 바로 보이시겠죠. 아마도..?

그건 많이 풀어보시면서 만들어 졌다고 생각합니다.


한 문제에 대해서 여러 가지 방식으로 접근해 보시는 건 분명히 도움은 됩니다.

제가 그러고 있거든요.

물론. 이게 효율적이다. 라고는 이야기 하지는 못하겠지만요.


잘못된 방법으로 접근을 해 보시면서. 어? 이건 왜 안 될까? 곰곰히 생각해 보시는 것도

좋은 공부에요. 그건 확실해요. 다음에는 같은 문제에 대해서 그렇게 접근을 안 할 수 있으니까요.


혹은 이런 경우도 있을 수가 있어요.

당장 이 알고리즘이 생각이 안 나는데 차선책은 없나? 혹은 이걸로는 안 될 거 같은데..

그러면 다른 풀이를 생각해 내야 하잖아요. 어떻게 하실 건가요?

그런 건 그냥 안 만들어져요.. 사실..


한 문제에 대해서 이렇게도 생각해 보고 저렇게도 접근해 보면서 만들어 지는 거죠.

그런고로.. 처음에는 그냥..

효율적이다. 효율적이지 않다. 그런 거 따지시지 마시고. 일단 해 보세요. 안 되면

왜 안 되는지 생각해 보시고. 정 모르겠다 싶으시면 물어보세요..

durano   3년 전

감사합니다.. 삽질하는것에 대한 두려움이 조금씩 생겨나고 있었는데 말씀보고 좀 안정이 되네요.ㅠㅠ 사실 뭐 문제푼지 얼마나 됐다고 이런 걱정을 갖는거부터가 어불성설이겠죠?.. 수없이 많은 삽질을 통해 발전할수 있는것인데 너무 처음부터 잘하고만 싶은 욕심이 앞섰나봅니다.  감사합니다!!

godmoon00   2년 전

저도 항상 궁금했던 내용인데 친절한 답변 감사드립니다

chogahui05   2년 전

사실 삽질을 했다는 거 자체가.. 시간 낭비인 건 아닙니다.

일례로 3830번 교수님은 기다리지 않는다에서 약 30분 가량 헤멨는데요. 헤메 보시는 것도 분명 도움이 됩니다.

그건 100%까지는 아니더라도 그.래도 이렇게 접근해서 삽질한 경험이 있는 거 같아. 이렇게 짜면 안 되겠네?

이런 기억이라도 남거든요.


3830번.. 왜 헤멨는지 분석을 해 보니

유니온 파인드에 대해서 정확하게 모르고 있었더라고요. find 함수가 경로 압축까지 한다는 사실을 제대로 간과했습니다.

사실 kks님 블로그 같은 데 (꽤 보시는 걸로 알고 있습니다.) 에서 유니온 파인드에 대한 글을 보고. 


아! find 함수가 경로 압축까지 하니까.. 이걸 이용해서..

응용 문제를 만났을 때 1~2분만에 merge 함수에서 특정 값을 이렇게 이렇게 업뎃하면 되겠네? 인정하는 부분?

이렇게 나오는 경우는 굉장히 드물 거에요. 보고 한 번만에 이해가 가고. 실수 안 할 정도로 완벽하게 짜면.. 

정말 이상적인 상황인데.. 항상 이상적인 상황만 생기는 건 아닌 거 같아요.


알고리즘을 배웠습니다. 그러면 완벽하게 이해를 하고 넘어가야 하는데..

사실 그러기가 쉽지 않아요. 완벽하게 이해를 하지 못한 건 어떻게 알 수 있을까요?

그런 건 해당 알고리즘을 필요로 하는, 어려운 문제를 풀어보면 나와요. 어디서 내가 잘못 이해하고 있는지.

그걸 발견했으면 오답 노트 같은 데에다가 적는 거죠.. 앞으로는 그런 실수 하지 말아야 겠다.

이건 갠적인 생각이니 그냥 참고만 해 주세요.


ps. 복도 뚫기에서 참교육 당하는 것만 남았네요.

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