GREEDY2 그리디 그리디 알고리즘 - 문제를 단순 무식하게, 탐욕적으로 푸는 알고리즘이다. - 탐욕적으로 해결한다는 것은 곧 현재 상황에서 지금 당장 좋은 것만 고른다는 것을 의미한다. - 문제 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지 파악해야 함 - 보통 '가장 큰 or 작은' 과 같은 기준이 제시되므로, 정렬 알고리즘과 함께 출제되는 경우가 많다. 그리디 알고리즘의 정당성 - 그리디 알고리즘으로 문제의 해법을 찾았을 때는, 반드시 그 해법이 정당한지 검토해야 한다. - 그리디 알고리즘을 이용했을 때 최적 해를 구할 수 없는 가능성도 적지 않으므로 유의해야 한다. 다음 그림을 보자. 루트 노드부터 시작하여 거쳐가는 노드 값의 합을 최대로 만들고 싶을 때? 단순히 매 상황에서 가장 큰 값을 고른다면.. 2021. 9. 30. Baby-gin Game Baby gin game - 0 ~ 9 사이의 숫자 카드에서 임의의 카드 여섯 장을 뽑았을 때, 3장의 카드가 연속적인 번호를 갖는 경우를 run 이라고 하고, 3장의 카드가 동일한 번호를 갖는 경우를 triplet 이라고 한다. 이 때, 6장의 카드가 run과 triplet 으로만 구성된 경우를 baby-gin 이라고 한다. - 6자리의 숫자를 입력 받아 baby-gin 여부를 판단하는 코드를 작성해보자 # greedy 로 접근 cards = [6, 6, 6, 6, 8, 9] # counts 배열 만들기 counts = [0] * 12 # run 을 확인하기 위한 조건에서 IndexError 를 방지하기 위해 리스트의 우측에 0값 2개를 패딩 for card in cards: counts[card] +.. 2021. 8. 10. 이전 1 다음
