글 작성 제목과 내용을 간결하게 정리해 주세요. 제목 내용 <h2>개념</h2><ul><li>그리디, 탐욕법, 욕심쟁이 알고리즘</li><li>현재 상황에서 지금 당장 좋은 것만 고르는 방법으로 문제를 해결<ul><li>단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘</li><li>매 순간 가장 좋아보이는 것을 선택하며, 나중에 미칠 영향에 대해서는 고려하지 않음</li></ul></li></ul><h3>그리디 알고리즘들</h3><ul><li>활동 선택 문제 (activity-selection problem)<ul><li>여러개의 경쟁 활동이 주어졌을 때 겹치지 않고 시간을 선택해 스캐줄을 짜는 문제</li></ul></li><li>최소 신장 트리 (minimun-spanning-tree)<ul><li>그리디 방법의 고전적인 예</li><li>신장 트리 : 그래프 내의 모든 정점을 포함하는 트리</li><li>최소 신장 트리 : 간선의 가중치를 고려해 최소 비용의 신장 트리를 선택한 것</li></ul></li><li>다익스트라 (Dijkstra)<ul><li>한 개의 시작점으로 부터 가장 빠른 경로를 구하는 알고리즘</li></ul></li><li>집합 감싸기 (set-covering)<ul><li>전체 집합 U와 그 부분 집합 Si들을 원소로 갖는 집합 F가 있을 때, F의 원소인 Si들을 합집합하여 전체 집합 U와 같아지는 집합 Si들의 최소 갯수를 찾는 문제</li></ul></li><li>휴리스틱 (heuristics)<ul><li>불충분한 시간이나 정보로 인하여 합리적 판단을 할 수 없거나, 체계적이면서 합리적인 판단을 굳지 필요로 하지 않은 상황에서 사람들이 빠르게 사용할 수 있게 보다 용이하게 구성된 간편 추론법</li><li>모두 최적해가 될 가능성이 없는 답들을 탐색하는 것을 방지하는 방법</li></ul></li><li>매트로이드 (matroid)<ul><li>그리디 알고리즘이 최적해를 가려낼 수 있는 경우인지를 판별할 수 있게 해주는 수학적 공간</li><li>어떤 문제의 공간이 매트로이드 구조이면, 이 문제의 그리디 알고리즘이 최적해를 도출해 낼 수 있음</li><li>단, 최적해를 갖는 모든 그리디 알고리즘이 매트로이드 구조를 띄는 것음 아님</li></ul></li><li>허프만 코드 (huffman code)<ul><li>문자열 데이터를 효율적으로 압축하는데 사용되는 그리디 알고리즘</li><li>압축하고고자 하는 문자열에서 자주 등장하는 문자는 짧은 비트로 표현하고 거의 등장하지 않는 문자는 긴 비트로 표현 (가변 길이 코드)</li><li>트리 형태로 빈도수에 따라 자주 등장하는 문자는 짧은 탐색으로 찾을 수 있게 처리</li></ul></li></ul><h3>그리디 알고리즘을 만드는 단계</h3><ol><li>하나의 선택을 할 경우 풀어야 할 부분 문제도 하나만 남도록 최적화 문제를 변경한다.</li><li>그리디한 선택이 언제나 안전하도록 원래 문제의 최적해들 중에서 그리디한 선택을 하는 것이 반드시 존재함을 증명한다.</li><li>그리디한 선택을 했을 때, 그리디한 선택과 남아 있는 부분 문제에 대한 최적해와 결합하면 원래 문제에 대한 최적해를 얻음을 보여 최적 부분 구조를 가진다는 것을 보인다.</li></ol><h3>그리디한 선택 특성</h3><p>선택을 할 때, 부분 문제들의 결과를 고려하지 않고, 현재 고려중인 문제에서 최적으로 보이는 선택을 취함</p><p>→ 동적 계획법에서는 단계마다 선택을 할 때, 부분 문제의 해에 의존함</p><p>→ 상향식 접근으로, 작은 부분 문제에서 큰 문제로 풀어나가는 방법을 취함 (메모이제이션을 통한 하향식 접근)</p><p>하향식 방법으로 진행</p><ul><li>주어진 문제를 더 작은 문제로 만드는 선택을 함</li></ul><h3>최적 부분 구조 (optimal substructure)</h3><p>어떤 문제에 대한 최적해가 그 문제의 부분 문제에 대한 최적해를 포함한 형태</p><h3>그리디와 동적 계획법(DP)</h3><p>그리디와 동적 계획법은 모두 최적 부분 구조를 이용하므로 다음 두가지의 문제가 발생할 수 있음</p><ul><li>그리디 해법으로 충분히 풀릴 수 있는 문제를 동적 계획법으로 해결하려 하는 문제</li><li>동적 계획법으로 풀어야 할 문제를 그리디로 잘못 적용하는 문제</li></ul><p>→ 그리디 방법으로 풀 수 없는 많은 중복되는 부분 문제를 갖는 경우 동적 계획법을 이용해 풀어야 함</p><h2>코딩테스트에서의 그리디</h2><ul><li>코딩테스트 수준에서는 다른 알고리즘과 비교해 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형</li><li>보통 그리디 유형 문제는 창의력을 통해 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구</li><li>그리디는 매우 다양한 문제 유형이 있어 단순 암기로 항상 잘 풀 수 있는 유형이 아님</li><li>많은 유형을 접해보고 해결할 수 있는 아이디어를 빠르게 떠오를 수 있게 하는 것이 중요</li><li>좋은 것을 선택할 기준으로 정렬과 함께 짝을 이뤄 출제되는 경우가 많음</li><li>바로 문제 유형을 파악할 수 없는 문제라면 그리디 알고리즘을 의심해 보고, 그리디로도 해결법이 나오지 않는다면 다이나믹 프로그래밍이나 그래프를 이용해야 할 수 있음.</li></ul><h2>문제</h2><h3><strong>거스름돈</strong></h3><p>음식점 카운터에서 손님에게 N원을 거슬러 줘야할 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 거스름돈으로 사용할 동전은 500원, 100원, 50원, 10원이 무한히 존재하며, 거스름돈 N은 항상 10의 배수다.</p><p><strong>문제 해설</strong></p><p>가장 큰 화폐 단위부터 가능한 갯수를 채워 거슬러 준다.</p><ul><li>시간 복잡도<ul><li>O(k) : k는 화폐의 종류</li></ul></li></ul><p><strong>코드</strong></p><pre><code class="language-python">coins = [500, 100, 50, 10] N = int(input()) cnt = 0 for i in coins: cnt += N // i N %= i print(cnt) </code></pre><p><aside> 💡 화폐단위가 서로 배수 관계에 있으므로 탐욕적으로 접근했을 때 가능한 것이다. 그렇지 않다면 하위 화폐를 다수 쓰는게 더 적은 개수를 사용할 수도 있을 것이다. 이렇게 아이디어를 떠올리고 그것이 정당한지 검토할 수 있어야 답을 도출 할 수 있다</p><p></aside></p><h3><strong>큰수의 법까지</strong></h3><p>주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙 단, 배열의 특정 인덱스에 해당하는 수가 연속해서 k번 초과해서 더할 수 없음</p><p><strong>문제 해설</strong></p><p>가장 큰 수와 두번 째로 큰 수만을 더하면 되는 문제</p><p>가장 큰 수를 K번 더하고 두번 째 큰 수를 1번 더함을 반복해 M번을 더함</p><p>→ (큰 수) * k + (작은 수) 가 M // (k+1) 번 반복됨을 이용해 더 효율적으로 계산이 가능함</p><p><strong>코드</strong></p><pre><code class="language-python">import sys input = sys.stdin.readline n, m, k = map(int, input().split()) # 입력받은 수를 내림차순 정렬한 리스트 생성 li = sorted(list(map(int, input().split())), reverse=True) # 규칙적으로 반복되는 횟수만큼 곱해주고, 나머지는 가장 큰 수의 횟수로 계산 print((li[0] * k + li[1]) * (m // (k + 1)) + (li[0] * (m % (k + 1)))) </code></pre><h3><strong>숫자카드게임</strong></h3><p>행열이 N*M인 숫자 카드 중에서 행에서 가장 낮은 숫자 중에 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임</p><p><strong>문제 해설</strong></p><p>각 행마다 가장 작은 수를 찾고 그 중에서 가장 큰 수를 찾으면 되는 간단한 게임</p><p>min(), max() 함수를 이용하면 간단하게 구할 수 있음</p><p><strong>코드</strong></p><pre><code class="language-python">import sys input = sys.stdin.readline n, m = map(int, input().split()) # n:행 / mㅣ열 minList = [] # 행에서 가장 작은 수를 담는 리스트 for i in range(n): row = list(map(int, input().split())) # 행 입력 minList.append(min(row)) # 행에서 가장 작은 수 담기 print(max(minList)) # 가장 작은 수들 중 가장 큰 수 출력 </code></pre><h3><strong>1이 될 때까지</strong></h3><p>어떤 수 N이 주어졌을 때 다음 두 과정 중 하나를 반복해 1이 될 때 까지 과정을 몇 번 반복했는지 구하는 문제</p><ol><li>N에서 1을 뺌</li><li>N을 K로 나눔</li></ol><p><strong>문제 해설</strong></p><p>나눗셈을 했을 경우 N을 크게 줄일 수 있으므로 최대한 많이 나누게 하는 문제. N이 K로 나누어 떨어질 때까지 1씩 빼주고 나누어 떨어지면 나누면서 횟 수를 카운트 하는 것은 N이 1이 될 때 까지 반복.</p><p>1씩 빼주는 과정을 N이 K로 나누어 떨어질 때 까지 반복하므로 N을 K로 나눈 나머지를 카운트에 더해주고 N에서 한번에 빼주면 반복 횟수를 줄일 수 있음</p><p><strong>코드</strong></p><pre><code class="language-python">import sys input = sys.stdin.readline # 최대한 많이 나누기 n, k = map(int, input().split()) result = 0 while n != 1: # n이 1이 될 때까지 반복 if n % k == 0: # k가 n의 배수이면 n = int(n / k) # 나누기 result += 1 # 카운트 else: result += n % k # n이 k에 나누어 떨어질 때까지 한번에 카운트 n -= (n % k) #한번에 빼기 print(result) </code></pre><h3>백준 문제</h3><p><a href="https://www.acmicpc.net/problem/1080">1080번: 행렬</a></p><p> </p><p> </p> 글 종류 이론 정리 알고리즘 이론에 대한 정리글입니다. 문제 풀이 알고리즘 문제 풀이입니다. 알고리즘 분류 수정 취소