chkwon91   1년 전

먼저 크기 순으로 쭉 나열하고

맨 뒤에서부터 바로 앞에 있는 그림과 크기 차이가 S미만이면

비용으로 비교해 뒤의 그림의 비용이 더 크면 앞의 그림과 바꾸도록 했습니다..

그리고 처음 그림부터 그림과 크기 차이가 S이상 나는 것들을 쭉 더했는데요

(그림 차이가 S 이상 나면 그 그림의 비용을 더하고 더한 그림을 기준으로 다음 그림을 탐사.. 말이 어렵네요ㅠ)

알고리즘 상으로 어떤 문제가 있는지 모르겠습니다 ㅠㅠ

코드의 일부분만 올릴게용

appa   1년 전

전 높이순으로 정렬하고 동적계획법으로 풀었습니다.

chkwon91   1년 전

저는 높이순으로 정렬한 다음

뒤에 것과 바로 앞의 것의 높이 차이가 조건보다 작다면 두개의 위치를 바꿀지 말지를 cost로 비교해서 했어요

그리고 0번부터 바로 전의 높이와 비교해서 쭉 더해가는 방식으로 했는데

혹시 이 알고리즘에서 문제가 있는지 알고싶네요;;

appa   1년 전

그리디에서 해가 성립되는지 판단하는 기준이 크게 2가지로 볼 수 있는데, 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)입니다. 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것입니다.

사용하신 알고리즘은 최적 부분 구조 조건에 어긋난다는 느낌이 강하게 드는데, 그 이유는 첫번째 for loop에서 인접한 것만의 높이 차이가 S보다 작다면 가중치를 기준으로 순서를 바꿈으로써 순서가 바뀐 녀석이 더 작은 부분 문제에서의 최적해가 될 수 있음에도 불구하고 위상이 바뀌는 데에 있습니다. 아래에 위치한 while문에서는 앞에서부터 보면서 S보다 크면 앞에 있는 것을 사용한다고 단정짓는데 이로 인해 뒤에서 선택해야할 애를 못 선택하는 반례를 생각해(다시 역으로 앞의 for loop를 처리했을 때에도 같은 위상이도록 끼워맞춰주다보면) 볼 수 있겠습니다. 그리고 비용이 같은 경우도 고려는 안 하신 것 같네요.

5 6

5 8

1 2

6 4

7 8

9 7

답은 (1, 2)와 (7, 8)을 고른 10입니다. 하지만 위 방법대로라면 (5, 8)만을 고르고 8을 출력하겠군요.

5 7

4 5

2 5

5 7

10 3

6 1

답은 (2, 5)와 (10, 3)을 고른 8입니다. 하지만 위 방법대로라면 (5, 7)만을 고르고 7을 출력하겠군요.

수고하세요.

chkwon91   1년 전

고맙습니다 다시한번 생각해볼게요!

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