wcsjinb   2년 전

일단 풀이법을 찾아보기 전에 생각나는 풀이법인 투포인터로 풀어봤습니다. 제가 문제를 잘못이해한것인지... 왜 틀렸는지 잘 모르겠습니다. 반례가 문제가 아니라 제 풀이법 자체가 틀린것인지 궁금합니다.

adxx   2년 전

투 포인터만으로는 모든 부분수열을 구할 수 없을 것 같습니다

Green55   2년 전

작성자님이 구하신건 substring이고, 문제에서 요구하는 것은 부분수열(subsequence)입니다.

https://ko.wikipedia.org/wiki/...

wcsjinb   2년 전

Green55

말씀하신부분이 이해가 되지않습니다 ㅠ

예제에서 -7 -3 -2 5 8 이 있으면

{-7} ```{-7,  -3} {-7, -3, -2} ````{-3, -2, 5}```{-2, 5, 8} ``` {8}  이런 모든 것들을 구하는 것이 아닌가요?

첨부해주신 위키에서는 정렬을 해야한다고 되어있는거 같은데, 제가 검색해본 부분수열은 위의 예시로 든게 부분수열로 나오더라구요..

Green55   2년 전

부분수열이란 원래 수열에서 순서를 유지하면서, 원하는 만큼 원소를 삭제해서 얻을 수 있는 수열입니다.

[-7 -3 -2 5 8]에서 -3과 5를 삭제한 [-7, -2, 8] 역시 부분수열입니다.

wcsjinb   2년 전

Green55 

앗 그렇군요! 생각하지 못한부분인데 감사합니다~! 

그러면 {-7 8} {-3 5} 이런 부분도 모두 부분수열이 될 수 있는 것인가요?

Green55   2년 전

wcsjinb   2년 전

Green55 

아.. 문제를 잘못이해하고 있었다니 ㅠㅠ 감사합니다 그린님!!

wcsjinb   2년 전

adxx

답변 감사합니다!!! 

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