[알고리즘 공부] 그리디(Greedy) 알고리즘 with GPT

그리디(Greedy) 알고리즘이란 무엇일까?

 

  안녕하세요. 이번 글은 나동빈님의 저서 [이코테]와 Chat GPT를 참고하여 알고리즘 공부 방식 중 첫 번째로 그리디(Greedy) 알고리즘에 대해서 설명하도록 하겠습니다. 

 

---

 

그리디 알고리즘이란?

 먼저 그리디 알고리즘을 간단하게 표현하면 '당장 좋은 것만 선택하는 그리디'라고 말할 수 있습니다. 이는 현재 상황에서 가장 좋아보이는 선택을 계속해서 하는 것이 특징이며, 각 선택이 부분적으로는 최적일 수 있지만, 전체로 보면 최적이 아닐 수도 있습니다. 다시 말하자면, 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해줍니다. 

 

 글로는 설명이 어려울 수도 있으니, GPT를 통해 생성해낸 간편한 문제로 살펴보도록 하겠습니다. 

 

간단한 예시 with GPT

 아래 문제는 GPT에게 그리드 알고리즘에 대한 간편한 예시를 만들어 달라고 했을 때의 문제입니다. 

 

• 문제 유형 : 그리디 알고리즘
• 문제 내용 : 최대 수의 합 구하기
• 문제 

 주어진 리스트에서 인접하지 않은 수들의 합이 최대가 되도록 서로 다른 수를 선택하려고 합니다. 예를 들어, [1, 2, 9, 4]가 주어졌을 때, 인접하지 않은 수를 선택하여 합을 최대로 만들면 1 + 9 = 10이 됩니다. 이러한 최대 합을 찾는 그리디 알고리즘을 작성하세요.

 

• 입력 : 정수로 이루어진 리스트가 주어진다. (예: [1, 2, 9, 4])
• 출력 : 선택한 수들의 합이 최대가 되도록 할 때의 합을 반환한다. (예: 10)

Code 

def max_non_adjacent_sum(nums):
    if not nums:
        return 0

    incl = 0  # 현재 수를 포함한 최대 합
    excl = 0  # 현재 수를 포함하지 않은 최대 합

    for num in nums:
        # 현재 수를 포함한 경우와 포함하지 않은 경우 중 더 큰 값을 선택
        new_excl = max(incl, excl)

        # 현재 수를 포함한 경우는 이전의 "포함하지 않은 최대 합 + 현재 수"
        incl = excl + num

        # 현재 수를 포함하지 않은 경우는 이전의 "현재 수를 포함한 최대 합 또는 포함하지 않은 최대 합"
        excl = new_excl

    # 최종적으로 두 경우 중 더 큰 값을 반환
    return max(incl, excl)

# 예시 입력
numbers = [1, 2, 9, 4]

# 결과 출력
result = max_non_adjacent_sum(numbers)
print("최대 수의 합:", result)


# 최대 수의 합: 10

 

---

마무리

 여기까지 [이코테]와 chatGPT를 활용하여 그리디 알고리즘에 대해 알아보고 간단한 예시를 살펴보았습니다. 혹시 [이코테]가 무엇인지 모르고 알고리즘 공부를 어디서부터 해야될 지 궁금하신 분들을 위해 아래 글에 제가 작성한 글들을 남겨두도록 하겠습니다. 이를 참고하여 코딩테스트 대비 혹은 알고리즘 공부를 하실 때, 참고해주시면 좋을 것 같습니다! 그럼 이번 글은 여기까지 마무리하도록 하겠습니다. 

 

---

 

관련 링크

2023.12.08 - [IT/관련 정보] - [코딩 테스트] 이것이 취업을 위한 코딩테스트다 with 파이썬

[코딩 테스트] 이것이 취업을 위한 코딩테스트다 with 파이썬

2023.12.16 - [코딩 TEST/코테 대비 과정] - [코딩 테스트] 코딩 테스트 준비 (1)

[코딩 테스트] 코딩 테스트 준비 (1)

2023.12.28 - [코딩 TEST/코테 대비 과정] - [이코테] 유형별 알고리즘 2부 학습 - Step2

[이코테] 유형별 알고리즘 2부 학습 - Step2