파이썬 알고리즘 문제

조회수 2541회

https://programmers.co.kr/tryouts/850/intro 이곳 해당 주소로가면 문제를 볼 수 있는데요. 이런 문제에요. 이미지 저는 이 문제를 맨 앞에서부터 일치하는 가장 큰 패턴을 찾아서 그 패턴으로 문자를 짜르고, 다시 이같은 작업을 반복하여 모든 문자를 짤라내는 거에요. 이미지 이런 논리인데. 그런데 이렇게 짜버리면 문제가 발생하더라고요. 모든 문자를 아예 짜를 수 없는 경우가 있기도 하고. 이미지 이와같이 아예 최솟값이 아닐 경우도 발생하더라고요 ㅠㅠ. 도대체 이건 어떻게 풀어야 하는건지 감도 못잡겠습니다. 몇날 며칠 이것만 생각하다가 잠도 못이루고 있습니다. 답안도 못찾아보겠고 어떻게 풀어야 하나요 이건??? 도움을 주시면 정말로 감사하겠습니다.

2 답변

  • 이 문제는 꽤나 어려운문제에요...

    다이나믹프로그래밍(동적계획법)이라는걸 공부해 보시면 좋겠습니다.

    • 이 문제를 푸는게 그 공부이지요 ㅠㅠ. 그래도 한번 그 키워드로 검색 해 볼게요. 감사해요. dbwodlf3 2017.5.11 18:28
    • 그 개념은 이미 알구 있어요ㅠㅠ.. 그래서 어떻게 다이나믹 프로그래밍으로 한다는 것인가요?? 'ㅅ'.. dbwodlf3 2017.5.11 18:31
  • 문자열 t의 n번째 위치부터 마지막 위치까지 strs의 문자들을 이용해서 만들었을 때 필요한 최소 문자의 개수를 M(n)이라고 할 때, 만약 n번째 위치부터 n + k번째 위치까지의 substring이 strs에 포함된 문자열이면 M(n)은 1 + M(n + k + 1),(k는 0부터 4) 중 가장 작은 값을 취하면 됩니다. 만약 최솟값이 무한대라면 가능한 방법이 없다고 하면 됩니다.

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)