[Question] 이게 왜 그리디인가요?

[deslog]

2023.02.09 모의 코딩테스트를 보면서, 상효님(레몬..)이 질문을 해주셨는데요! 각자 푼 문제들의 어떤 부분이 '그리디 알고리즘'임을 느꼈는가에 대해서 물어봐주셨습니다. 물론, 저도 이부분이 굉장히 궁금했었고, 그리디 알고리즘이 참,,, 애매하더라구여? 그래서 '이부분 때문에 그리디 알고리즘을 사용해야합니다!'라는 것들을 좀.. 짚어봤습니다. 많관부

⚫️ 그리디 알고리즘 (탐욕법)

• 참고 레퍼런스

💡 그리디란

- 현재 상황에서 지금 당장 좋은 것만 고르는 방법
- 매 순간 가장 좋아보이는 것을 선택 → 현재의 선택이 나중에 미칠 영향이나 경우의 수에 대해서는 고려하지 x 
(백트래킹을 통해서 추가 점검을 하지 않는다!! 정말 지금 순간에서 만족하고 끝.)
- 단, 그리디 알고리즘은 항상 최적해를 보장하지 않는다. 단순히 가장 좋아보이는 것들을 반복해서 선택했을 때, 최적의 해를 구할 수 있는지 검토하는 과정이 필요하다!
- 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형

⚫️ 이 문제가 왜 그리디야?

그리디 문제들을 보면, 도대체 그리디가 뭔지 감이 안올 때가 있다. 지금 나도 “이 문제는 ‘그리디’유형입니다.” 라고 말해주지 않으면 아직 그리디가 뭔지, 그리디로 풀어야하는건지? 에 대한 감이 잡히지 않는다. 그래서 지금까지 풀어본 그리디 유형들을 정리해보고자 한다.

▫️ [이코테 예제] 백준 5585번: 거스름돈

그리디 알고리즘을 설명하는 가장 Well-known

이 문제를 보면, ‘최소 동전갯수’로 거스름돈을 주어야합니다. 그렇게 하기 위해서 가장 좋은 방식은? ‘가장 큰 돈을 우선적으로 주는 것’이 가장 좋겠죠. 즉, 500원 짜리부터 아주 탐욕적으로 줘버린다는 소리가 바로 그리디입니다. (나머지 동전들은 고려하지 않은채 500원짜리 먼저 거슬러준다는 것! 500원짜리 이놈이 아주 욕심쟁이다~ 본인이 먼저 거슬러지려고한다~ 이렇게 생각했어요…)

▫️ boj 4796번: 캠핑

• 가장 많은 캠핑장을 사용하기 위한 시각으로만 접근
• (예제1)
  김강산이 묵을 수 있는 최대 일 수: 8일
  캠핑장 오픈 일수: 5일씩
  김강산 총 휴가 일수: 20일
  • 김강산이 못자는 것은 생각하지 않음 (그냥 무조건 날짜 생기면 묵는다고 생각) → 탐욕법? 넹 이게 최선! 최대의 값을 도출해냄
  • 5일오픈하는데, 김강산은 8일까지 묵을 수 있으니까 5일 전부 그냥 잔소리말고 묵는다고 생각
  • 이렇게 다른 경우 생각하지 않고 지금 현재의 최적상황만 생각하는 것이 ‘그리디’가 아닐까…

▫️ boj 1449번: 수리공 항승

• 그리디는, 정렬을 통해 앞에서부터 최적의 무언가를 찾아나서는 것을 의미한다. 그니까 만약 정렬된 Array를 다룰때, Array의 다음 인덱스는 전혀 고려하지 않는 것이다.
• (예제 1)
  누수부분: 4군데
  테이프의 길이: 2
  누수지점: 1, 2, 100, 101
  • 테이프는 자를 수 없기 때문에, 무조건 2칸이 붙어있는 애들만 매꿀 수 있다.
  • 누수지점이 순서대로 입력되지 않을 수 있기 때문에 오름차순으로 정렬해준다.
  • 그다음, 두칸씩 막아나가면 된다!
  • 두칸씩 막을때, 현재 지점에서 앞에있는 테이프와 연결이되는지? 새로운 테이프를 꺼내야하는지?에 대한 고민만 수행하고, 혹시,,, 뒤에서 또 누수가 생기는 경우 어쩌고 저쩌고,, 이런 경우의수는 일절 생각 하지 않는다!

▫️ boj 1931번: 회의실 배정

그리디 알고리즘을 설명하는 가장 Well-known

• 회의의 시작시간과 끝시간이 주어지고, 최대한 많은 회의를 진행하도록 하는 문제
• 최대한 많은 회의를 진행하기 위해서는, 시작시간이 빨라야하고, 시작시간이 같다면,,, 끝나는시간이 빨라야한다!
  • 앞서 있는 회의들이 빨리 끝나면 끝날수록 뒤에서 선택할 수 있는 회의의 수가 늘어나기 때문이다.
• DP로도 풀 수 있는문제, 하지만 모든 경우의수를 연산하는 과정을 포함시켜 효율이 떨어진다고 한다~ 이런유형은 무조건 그리디로!

▫️ boj 10610번: 30

• 전 이게 정말 왜 그리디인지 이해할 수 가 없네요 도통!!! 수학적인 원리를 발견하면, 그리디 풀이가 가능한 문제라고 하는데,,
• 일단 30의 배수가 되기 위해서는 두가지의 조건을 만족해야한다.
  1. 입력받은 수에 0을 포함해야한다.
  2. 각 자리수를 더하면 3의 배수다.
• 이 조건을 만족하면 묻지도 따지지도 않아도 되는 부분이라 그리디인가요..?

▫️ boj 1783번: 병든 나이트

• 나이트가 제대로 병이들어서 오른쪽 방향으로만 이동가능함 (오른쪽으로 이동하는 4가지 방법 존재)
• 체스판의 높이가 제대로 주어지지 않으면, 특정 움직일 수 있는 칸수가 제한되어있음.
• 체스판의 세로길이가 4이상이고, 높이가 7이 넘어간다면 그 어떠한 선택도 고려하지 않고 그냥 오른쪽으로 한칸씩 나아가는게 최선
• 나이트가 한정적으로만 움직이고, 나이트의 현재 위치에서 가장 최선의 선택은 그냥 한가지뿐 → 방향키 네 가지 중 어떤 경우가 더 큰 경우의 수를 갖지? 하는 검증이 따로 필요하지 않기 때문에, 그리디 알고리즘.
  • 오른쪽으로 한칸씩움직이는 게 최적해라는 것을 보장할 수 있는가?
  • 맞다. 4개의 방향키를 이미 모두 선택한 상태라면, 한칸씩 이동하는게 최대의 칸수를 보장받을 수 있다.

▫️ boj 1541번: 잃어버린 괄호

사실 이것도, 수학적인 개념이 더 중점이고 그리디.. 라고 하기에 .. 맞나..? 이게맞나..

• +와 -로 구성된 식이 들어오면, 적절히 괄호로 묶어서 결과값이 최소가 되게 하는 문제
• 직관적으로 생각해보면, 마이너스 되는 수가 가장 커야하니까 + 인애들을 전부 괄호로 묶어서 전부 - 해주면 된다.
• 이코테 해설에 비춰보면,,, ‘최대한 많이 더해서 빼주기’라는 과정 자체가 그리디인듯 하다.
  • 최대한 많이 더해서 빼주기 라는 과정이 최적해를 보장할 수 있을까?
  • 맞다. 수학적인 개념으로 봤을 때, - 연산에 큰 - 연산을 수행하면 최소값으 구할 수 있으니까!(당연한소리)

▫️ pro - 체육복

• 체육복을 잃어버린 학생들 순서대로 여벌있는 친구를 찾아나서는 과정
• 지금 바라보고있는 ‘잃어버린 학생 인덱스’가 체육복을 구할 수 있는지 확인하는 과정 → 그리디
• (예제)
  잃어버린 친구 2번 4번
  여벌을 갖고 있는 친구 3번 5번
  이런 경우라면, 3번친구는 2번과 4번 모두에게 빌려줄 수 있다. 근데! 그리디에 의해서 현재 바라보고있는 친구가 2라면, 2번에게 빌려줘버린다~
  • 이렇게 구한 값이 최적해인가?
    • 아니다. 예외사항이발생하기 떄문에, lost 한 친구들 번호를 한 번 정렬해주어야한다.
    • 아래와 같은 경우가 생김! → 이렇게 그리디는 언제나 최적의 해를 갖지 않으므로, 한 번 검증해줘야한다.

▫️ pro - 조이스틱

• 그리디인 이유
  1. A에서 바꿀 알파벳 문자까지 이동하는 상황: Z,Y,X,,,쪽으로 거꾸로 갈 수 도 있고, A,B, C,,,,쪽으로 바꿀 수 있어서 그때그때 최소가 되는 값을 선택하는 과정이 그리디
  2. 커서를 이동하는 과정: 왼쪽으로 이동할지, 오른쪽으로 이동할지 선택하는 과정에서 그때그때 최소가 되는 횟수를 선택하는 과정이 그리디

▫️ pro - 큰 수 만들기

(이 문제는 어떻게 푸느냐에 따라 그리디를 사용하냐, 마냐가 달려있다. 완전탐색으로 풀수도 있다. 하지만 무수히 많은 런타임에러 친구놈들을 만나게 되겠지만,,,)

• 기본적인 풀이 방식
  • 입력받은 수에서 가장 큰 수가 되기 위해서, 가장 앞자리수에 가장 큰 수가 와야하고, 뒤에 있는 숫자들을 비교하면서 하나씩 제거해주어야한다.
  • 스택을 사용한다.
• 위 풀이 방식을 토대로 설명해보면,
  • 스택을 사용해서 그때그때 스택 맨 마지막에 있는 값과 지금 넣으려느 값을 비교한다. 현재 비교하려고 하는 인덱스를 기준으로 비교해서 최적의 해를 얻으려고 하는 과정이 그리디이다.

▫️ pro - 구명보트

• people을 무게순으로 정렬한 뒤, 가벼운친구 + 무거운친구를 세트로 비교해서 배를 태우려고 한다. 이 과정에서 가벼운친구 + 무거운친구 < limit 이라면, 무거운친구를 한단계 가벼운 친구로 바꿔준다. 배를 태울 친구를 고르는 과정에서, 지금 당장 태울수 있는 친구들만 고려해서 해를 찾아가는 과정이다. → 이것은? 그리디!

▫️ pro - 섬 연결하기

• 그리디 알고리즘의 일종인 크루스칼 알고리즘을 사용함
• 크루스칼 알고리즘이 왜 그리디인가?
  • 그래프에서 가중치가 최소가 될 수 있는 간선들을 고르는 상황이 발생한다 → 이게 바로 그리디
• 여기에 크루스칼, 최소신장트리, Union&Find가 잘 정리되어있네요
  • 알고리즘 - 크루스칼 알고리즘(Kruskal Algorithm), 최소 신장 트리(MST)

▫️ pro - 단속카메라

• 이 문제는 위에서 풀어본 회의실배정 문제와 비슷
• routes는 시작점과 끝점을 포함한 Array가 들어있다.
  • 최적해를 구하는 가장 큰 핵심 포인트는 ‘정렬’이긴 하다.
• 다음 route 출발점이 현재 카메라 위치보다 뒤에 있는지 확인하는 과정이 필요 → 그리디
  • 차례때로 순환하면서 route를 하나씩 파악하고, 그 route를 판단할때 그 당시에 카메라의 위치를 확인하는 이 과정이 순간순간 최적해를 찾는 과정이다.

💬 정리

지금까지 풀어본 문제들을 다시 보면서 왜 그리디알고리즘으로 문제를 풀었는가에 대해서 생각해보았다. 그리디 알고리즘가 뭔지 잘 감이 안왔는데 이렇게 쭉 정리해보니 알 것 같은 느낌적인 느낌?

• 대부분 for문으로 순환하면서, 그 순간순간 어떠한 값과 비교하면서 현재 고를 수 있는 최적의 값을 찾는다.
• 정렬을 이용하여 최적해를 검증하는 풀이도 있기 때문에, 최적해를 선택하고 나서 한 번 더 검증이 필요하다.

그리디란, 단순하게 말하면 ‘제일 좋은거(제일 정답에 가까워질수 있는거)!!’를 고른다고 정리할 수 있겠다. 정말,, 탐욕법이라는 이름이 잘 어울리넹?!

혹시 아닌데 아닌데 난 이렇게 생각하는데 하는 분이 계시면,,, 적극적으로 댓글남겨주세요 ㅠㅠ 위에는 오직 제 ,,, 생각대로 마음대로 그리디라고 단정지은 겁니다....

[SH0123]

한 번 혼자 쓱 다시 코드와 문제들을 살펴본다음 브라운이 정리해준거 보러 왔어요 ~~
깔끔하고 상세하게 정리해주셔서 헷갈리던 부분도 조금씩 받아들여지네요 ㅎㅎ
뭔가 그리디는 다른 알고리즘을 풀어보면 풀어볼수록 더욱 깨닫게 되는 것 같기도해서 앞으로 많이 풀어보면서 그리디랑 계속 비교해보려구요
근데 브라운 글 보면서 그리디에 대해 생각이 딱 하나 떠오른게 있는데, 문제에 대한 풀이를 생각하면서 병든나이트에서 모든 경우를 다 살펴보는게 아니라 n>3, m>7부터는 그냥 딱 두가지 이동방법을 반복해서 쓰면 최대값이 나오겠는데? 라고 머리로 떠올린 그 과정이 딱 그리디인 것 같기도하다는 생각이 드네요 ㅎㅎ
깔끔한 정리 감사합니당 브라운 ~

[chang0-0]

그리디 관련 공부를 하다가 우연히 보게되었는데 정리 엄청 깔끔하게 하셨네요..
좋은 글 읽고 갑니다!