이코테
그리디 1-3) 숫자 카드 게임
문제 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한장을 뽑는 게임 숫자가 쓰인 카드들이 N x M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. 입력 조건 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1이..
그리디 1-2) 큰 수의 법칙
실전 1. 큰수의 법칙 문제 해설 이 문제를 해결하려면 일단 입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하면 된다. # 큰수의 법칙 def maxNum(n, m, k, listNum): result = 0 listNum.sort() max1 = listNum[-1] max2 = listNum[-2] q = 1 while True: if m == 0: break maxN = max(listNum) for t in range(k): if m == 0: break print(max1) result += max1 m -= 1 print(max2) result += max2 m -= 1 return result print(maxNum(5,8,3,[2,4,5,4,6])) 이 문제는 반복되는 수열에 대해서 ..
그리디 1-1) 거스름돈
예제1) 거스름돈 문제 해설 이 문제의 핵심은 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 방법으로 해결할 수 있다. #코드 작성 def exch(money): change = [500, 100, 50, 10] result = [] for i in change: result.append(money // i) money = money % i return result exch(1260) 코드를 보면 화폐의 종류만큼 반복을 수행해야한다. 따라서 종류가 K개라고 할 때 위 소스코드의 시간복잡도는 O(K)이다. 이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야하는 금액의 크기와는 무관하다는 것을 알 수 있다.
1주차 - 그리디 이론
정의 ‘탐욕스러운’ 혹은 ‘욕심 많은’을 뜻하는 알고리즘으로 선택의 순간마다 바로 눈앞에 보이는 이익만을 좇는 알고리즘을 뜻합니다. 즉, 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법을 말합니다. 결정을 내리는 순간마다 가장 최선의 선택을 통해 전체적인 최적의 해결책을 찾아내고자 하는 노력에서 비롯되었습니다. 각 단계에서의 최선의 선택이 결국 전체적인 최적의 해결책을 제공해주는 경우가 많습니다. 동적 프로그래밍을 사용하게 되면 중복되는 하위 문제를 다루게 되는데 이것이 많은 연산량과 계산 복잡도가 커지게 한다는 한계점을 가지고 있습니다. 이러한 점에 착안하여 고안된 알고리즘입니다. (동적 프로그래밍을 대체하는 것이 아닌 서로 보완하는 개념입니다) 특징 대부분의 경우 계산 속도가 빠르므로 매우 실용적..
코딩테스트 스터디
🗓️ 일정 : 매주 화, 토 7월 16일부터 ~ ... 평일(오프라인) - 화 (오후 7시 - 9시 _ 2시간) 주말(온라인) - 토 (오전 10시 - 12시 _ 2시간) 📖 교재 이것이 취업을 위한 코딩테스트다 with 파이썬 - 나동빈 ✏️ 방법 매주 한 챕터씩 공부하고 문제풀이 진행 한챕터당 단원장이 내용을 정리해서 화요일날 발표 개념을 공부하고 해당 주제 기출문제 풀기 작성한 코드 노션에 올리기 👨💻발표순서 1번째 : 그리디 2번째 : 구현 3번째 : DFS/BFS 4번째 : 정렬 5번째 : 이진탐색 6번째 : 다이나믹 프로그래밍 7번째 : 최단거리 8번째 : 그래프 이론