강의로 돌아가기
jar100

안녕하세요 문제 카태고리가 다른거같습니다. 혹시한번 확인해 주실 수 있나여-?

저는 탐욕법(Greedy ) 알고리즘은 현재 상태에서 최적을 선택하는걸로 알고 있는데요

그래서 현재의 최적을 선택하기 때문에 최적해가 맞을 수 도 있지만 다를 수도 있다고 알고 있습니다.

탐욕법으로 이 문제를 접근하게 된다면

현재상태의 최적을 선택하니 가장 가까운 알파뱃을 변경시키고 거기서 또 가장가까운 알파뱃을 변경시키는 방향으로 나가는게 맞다 생각합니다.

그렇게 되면 여기서 최적해인 최소이동거리는 다르게 나올 것이라 생각됩니다.

예를 들자면 ABABAAAAAAABA 가 입력으로 주어 진다면

  1. index 0 번째에서 시작하니 현재 AAAAAAAAAAAAA 와 입력값과 다른 문자를 찾습니다.

  2. index 1 의 B, index 3 인, B index 11인 B 중 거리를 비교 해

  3. 거리가 1 로 가장 가까운 index 1인 B를 변경하게 된다고 생각 합니다.

  4. 그후 같을 때 까지 다시 반복

이런식으로 문제를 접근하게되면 우위우우위우우우우우위 가 되고 11이 됩니다. 하지만 최적해는 좌좌위우우우위우우위 10이됩니다.

이와같이 탐욕법으로 풀면 반례들이 많이 나올거 같은데 어떻게 생각하시나요

제가 생각한게 맞는지 확인부탁드려용

2 개의 답변
Demi

안녕하세요. 본 문제는 탐욕법 카테고리에 속한 문제가 맞습니다.
질문하신것과는 다른 방식의 탐욕법 풀이가 가능합니다.

  • 전복오리백숙
    그 다른 탐욕법 풀이가 뭔지는 모르겠지만 질문자분이 말씀하신 'ABABAAAAAAABA' 케이스에서 10이 나오는 코드가 정답이라는 건가요? 근데 지금 채점을 보면 11이 나오는 코드가 정답으로 채점이 되는데 그럼 채점이 잘못된거 아닌가요? 전복오리백숙 2019.04.15 13:38
김동욱

저도 greeedy에 적합한 문제가 아닌것 같네요.
애초에 optimal substructure를 갖지 않아 그리디하게 풀면 오답이 나오고 (U턴이 필요한 케이스),
더욱이 substructure를 분리해 풀어내지 않아도 단순히 O(N) 시간에 풀립니다.
수학문제로 볼 수 있을 듯합니다.

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.