그리디 검색 결과

해당 글 3건
리버스 가희와 프로세스 : 상황 도식화를 잘 시켜 봅시다.

가희배 코딩테스트 1회에서 나온 7번 문제는 가희와 프로세스 문제의 결과값이 주어졌을 때, 거꾸로 인풋 값을 만들어 보라는 문제였습니다. 항상 가능한 경우만 주었기 때문에 쉬울 거라고 생각했습니다. 그런데, 실제로 대회 때 문제를 푸신 분들은 그리 많지 않았고 골드 1로 평가되는 기염을 토하게 되었습니다. 사실 불가능한 경우까지 출력하라고 했는데, 진짜 그렇게 출제 했다면 100% 플레급으로 뛰었을 거라 생각합니다. 그러면 무엇이 이렇게 어렵게 만들었을까요? 문제에서 설명하는 알고리즘을 단순화 하는 것이 제일 어렵지 않았나 싶습니다. 게다가 실행 결과를 가지고 가능한 입력값을 만들라고 하니 당황할 수 밖에 없었을 겁니다. 사실 제가 맞닥트렸어도 매우 당황했을 겁니다. 일단, 가희와 프로세스의 나온 입력 ..
자료알고/알고리즘 2021. 11. 1. 04:31
그리디 알고리즘 : 매 순간 최적의 해를 선택한다.

greedy는, 욕심쟁이라는 뜻입니다. 이름에 걸맞게, 매 순간 제일 매력적인 해를 택하는 방법입니다. 그런데 그게 best한 답일까요? 답은 그럴 수도 있고 아닐 수도 있다는 것입니다. 오늘은 이러한 approach로 풀 수 있는 문제 중에서 쉬운 문제만 소개해 드리도록 하겠습니다. 작업 n개가 주어집니다. 이들을 끝내는 데 걸리는 시간이 있습니다. 각각 T(1), ... ,T(n)이라고 합시다. 우리는 제한시간 limit 내에 최대한 많은 작업을 끝내려고 합니다. 어떻게 하면 좋을까요? 직관적으로 생각했을 때, 선택하지 않은 작업들 중에서, 소요 시간이 제일 짧은 작업들을 매 순간마다 선택하면 될 거 같습니다. 그러면 T 배열을 정렬하면 될 겁니다. 예를 들어 T = [2, 5, 1, 3, 7] 이라..
자료알고/알고리즘 2019. 10. 26. 18:58