오늘 배운 것🤓

Hash를 이용한 알고리즘 문제 풀이

1. 완주하지 못한 선수
   • 마라톤에 뛰는 선수와 완주한 선수가 담겨있는 리스트를 받으면 완주하지 못한 선수를 찾는 문제
     단, 완주하지 못한 선수는 1명이다.
   • 이름이 겹칠 수도 있기 때문에 마라톤을 뛰는 모든 선수들에게 점수를 1점씩 부여하고 완주할때 1점을 감점함으로써, 1점이 남아있는 선수를 찾으려고 했다.
   • 이때, 선수의 이름을 key로 하려고 하기 때문에 Hash를 사용했다. python에는 dictionary 데이터 타입 사용
2. 체육복
   • python에서 제공하는 내장 자료형인 set도 해시를 이용한 자료형이기 때문에 Hash를 사용한 문제로 분류했다.
   • 여벌의 체육복을 가져온 학생들이 체육복을 도난당한 학생들에게 체육복을 빌려주는 문제
     단, 학생들은 자신보다 한치수 작거나 한치수 큰 학생에게만 빌려줄 수 있다.
   • 여벌의 체육복을 가진 학생과 도난당한 학생의 교집합을 제거하여, 여벌의 체육복을 가진 학생을 정렬한다. 정렬한 학생 리스트를 돌면서 도난 당한 학생 중 빌려줄 수 있다면 빌려주면서 제거한다.
   • 이 방법은 정렬을 하기 때문에 $O(NlogN)$시간 복잡도를 갖지만, 여벌의 체육복을 가진 학생에 대해서만 정렬하기 때문에 여벌의 체육복을 가진 학생의 수가 적다면 이 방법을 고려해볼 수 있다.

정렬을 이용한 알고리즘 문제 풀이

1. 가장 큰 수
   • 여러개의 수가 있는 리스트를 받아 그 수를 조합하여 만들 수 있는 가장 큰 수를 반환하는 문제
   • [3, 32] 가 있다면 3보다는 32가 더 크기 때문에 323 이라고 생각할 수 있지만, 332로 조합해야 더 큰 숫자임을 확인할 수 있다. 이는 각 원소를 반복하여 늘어놓았을 때 더 큰 숫자를 앞으로 정렬함으로써 해결할 수 있다.(3-> 3333, 32-> 3232)
   • 기본적인 정렬 방법이 아닌 내가 만드는 규칙을 적용하기 위해서 list.sort(key=lambda x : ~~) 를 사용하자.

Greedy를 이용한 알고리즘 문제 풀이

우선, 탐욕법은 알고리즘의 각 단계에서 그 순간에 최적이라고 생각하는 것을 선택하는 것이다. 현재의 선택이 마지막 해답의 최적성을 해치지 않을 때 탐욕법을 사용한다.

1. 체육복
   • 위에서 예시로 들었던 문제를 탐욕법으로 풀 수 있다.
   • 전체 학생의 체육복 현황에 대한 배열을 만들어서, 여분의 옷을 가지고 온 학생은 1을 더해주고, 도둑맞은 학생에게는 1을 빼준다. 현황 배열을 차례로 돌면서 여분이 있는 학생 앞/뒤 학생을 확인하며 체육복을 빌려준다.
   • 이 때, 앞에서 뒤로 빌려주든, 뒤에서 앞으로 빌려주든 순서를 잘 지켜서 빌려주어야 한다.
2. 큰 수 만들기
   • 주어진 수에서 k만큼 숫자를 뺐을 때 가장 큰 수를 반환하는 문제
   • 주어진 수를 처음부터 꺼내서 모으지만, 모아진 숫자의 마지막 숫자보다 현재 숫자가 더 크다면 마지막 숫자를 제거하고 현재 숫자를 넣는다.

느낀 점😊

지금껏 왜 알고리즘 문제를 공부하지 않았는지 후회될 정도로 굉장히 재미있게 수업을 들었다. 새로운 풀이가 나올 때 마다 항상 감탄하게 된다. 이번에 배운 탐욕법은 다른 문제가 나온다면 적용하기 어려울 것 같다. 많은 문제를 풀어볼 필요가 있다.