아이테킨의 끄적끄적

점수가 큰 과제를 뒤에서부터 채워나가는 방법으로 과제를 해결하도록 계획을 세워야 한다. (처음엔 점수가 큰 과제부터 한다거나 마감일이 빠른 과제부터 끝내는 방법을 생각해보았지만 답은 아니었다.) 마감일 | 점수 4 | 60 4 | 40 1 | 20 2 | 50 3 | 30 4 | 10 6 | 5 이렇게 과제와 마감일이 주어져있을 때 가장 점수가 높은 과제부터 마감일부터 뒤로 계획을 세워준다. 60점 과제는 4일째 50점 과제는 2일째 40점 과제는 4일째에 이미 60점짜리를 해야하므로 3일째 30점 과제는 3일째, 2일째 이미 다른 과제가 있으므로 1일째 20점,10점 과제는 남은 기간이 없으므로 패스 5점 과제는 6일째 이런 식으로 이런 알고리즘을 구현하는 데엔 heap 자료구조를 사용하는 것이 유용하..

이번 블로그는 파이썬을 이용해서 힙 자료구조를 이용하는 방법을 정리해보고자 한다. 일단 힙(heap)은 우선순위 큐를 만들때 이용하면 좋다. [자료구조] 먼저 알아야한 자료구조들에 대해서 간단하게 정리해보자! - 스택(LIFO : Last In First Out) : 자료가 들어오는 순서대로 위로 쌓인다고 생각하면 됨 - 큐(FIFO : First In First Out) : 자료가 들어오는 순서대로 영화관 줄 처럼 줄을 서 있는다고 생각하면 됨. - 우선순위 큐(Priority Queue) : 들어온 순서에 상관없이 우선순위에 따라 데이터가 처리되는 자료구조. : 힙(heap)자료구조로 구현할 수 있다. 우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능하다. 이중에서 힙(heap)으로 구현하는 것이..

우선순위 큐의 힙 자료구조를 이용하면 문제를 풀 수 있다. 처음에 이 문제를 풀 때 '힙(heap)'이라는 자료구조를 생각해내지 못해서 한참을 헤맸다. 이 문제를 풀때 가장 중요한 아이디어는 힙(heap)이라는 생각이다. 알고리즘은 이러하다. 0) 총 비교한 횟수(answer)를 0으로 둔다. 1) 현재의카드 묶음(card_deck) 중 가장 작은 2개의 카드 묶음을 꺼낸다. 2) 두 개를 더한 값 = 현재 단계에서 비교한 횟수 3) 두 개를 더한 값을 총 비교한 횟수(answer)에 더해준다. 4) 두 개를 더한 값을 다시 카드 더미(card_deck) 안에 넣는다. 5) 1 ~ 4 과정을 힙에 하나의 덱만 남을 때 까지 반복한다. (참고. https://claude-u.tistory.com/341) ..