알고리즘 스터디!
대학교 동아리 지인들을 모아 알고리즘 스터디를 만들었다.
운영 방식은 다음과 같다. 알고리즘 스터디를 운영하고 싶은 사람들은 참고하면 좋을 것 같다.
운영방식
주마다 아래 목차에 따라 한 목차씩 다룬다.
만약 해당 목차에 대해 더 공부할 필요성이 느껴지면, 스터디원이 다같이 협의에 따라 해당 목차 스터디를 한 주 더 연장하는 등의 조치를 취한다.
목차는 다음과 같다. ('이것이 코딩 테스트다' 라는 책을 참고했다.)
- 그리디
- 구현
- DFS/BFS
- 정렬
- 이진탐색
- 다이나믹 프로그래밍
- 최단경로
- 그래프
- 그밖에 기출문제들...
10,11,12....
첫 번째, 이전 스터디에서 풀기로 정한 문제들을 풀어온다.
꼭 완전히 다 해결하지 않아도 된다. 최대한 할 수 있는 만큼만 해오자.
두 번째, 자신의 코드를 설명할 간단한 자료를 만들어 발표한다.
자료를 만든다는 건 자신의 코드를 리와인드할 수도 있고, 나의 포트폴리오를 쌓는 데에도 의의가 있으니 귀찮더라도 작성하는 것이 좋다.
당부하고 싶은건 개인사정으로 인해 미참석인원이 발생 시, 참석하지 못하는 인원은 본인의 코드설명 자료를 반드시 미리 제출하도록 한다.
세 번째, 한 스터디원의 발표가 끝나면 해당 스터디원의 코드를 리뷰하는 시간을 갖는다.
해당 스터디원의 코드를 개선해줄 수도 있고, "내가 푸는 방법 외에도 이런 식으로 풀 수도 있구나!"라는 깨달음의 시간을 가질 수도 있다.
만약 해결하지 못한 문제가 있을 시, 통과하지 못한 코드를 다른 스터디원들과 함께 검토하며 코드를 수정하는 시간을 갖는다.
필자는 다른 사람의 코드를 이해하고 수정해주는 과정이 알고리즘 스터디의 핵심이라고 생각한다.
네 번째, 스터디원 중 한 사람이 다음주에 다룰 목차를 주제로 발표를 진행한다.
알고리즘에 대한 지식이 전혀 없는 상태에서 문제 해결은 힘들다.
발표를 듣는 사람도, 발표자료를 준비하는 사람도 예습 및 복습의 기회가 될 수 있다.
마지막으로, 다음 스터디까지 풀어올 문제를 정한다.
문제는 3개 정도를 정한다. 이건 스터디마다 재량껏 정하면 된다.
스터디원의 평균적인 수준을 고려해 3개 정도의 문제를 각각 상, 중, 하 난이도로 정하면 좋을 것 같아서 그렇게 정해봤다.
문제 해결은 백준으로 진행했다. 이유는 문제 수도 많고, 유형별로 묶어서 해당 알고리즘을 연습해볼 수 있는 장점도 있으며, 티어 개념을 통해 나의 수준과 문제 수준을 쉽게 파악할 수 있기에 스터디에 적합하다고 생각했다.
그리디 알고리즘(Greedy Algorithm)이란?
그리디 알고리즘이란, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식을 말한다.
지금 당장 가질 수 있는 최고의 이익을 따라가는 알고리즘이기 때문에 탐욕 알고리즘이라고도 부른다.
문제풀이
알고리즘 스터디 규칙에 따라 상, 중, 하 난이도로 다음 세 문제를 정해 풀어보았다.
캠핑(브론즈 1)
여기서 핵심은 sys 모듈을 통한 빠른 입력. input은 prompt 메세지를 입력받고 맨 뒤 개행문자를 삭제하는 기능을 실행하기 때문에 상황에 따라 sys.stdin.readline을 사용 시 시간을 크게 단축할 수 있다.
전체 코드
import sys
input = sys.stdin.readline
count = 0
while 1:
L, P, V = map(int, input().split())
if L==P==V==0:
break
answer = (V//P)*L
if (V-(V//P)*P) > L:
answer += L
else:
answer += (V-(V//P)*P)
count += 1
print(f"Case {count}: {answer}")
설탕 배달(실버 4)
여기서 핵심은 함수 사용. 함수는 return을 사용하면 함수를 즉각 종료하기 때문에, 위 문제풀이 과정에서 for문을 벗어나는 부분과 -1을 반환해야 하는 부분에서 유용하게 쓸 수 있다.
전체 코드
import sys
input = sys.stdin.readline
N = int(input())
def min_bag(N):
for i in range(N//5, -1, -1):
tmp = N - 5*i
if tmp%3==0:
return i + tmp//3
return -1
print(min_bag(N))
카드 정렬하기(골드 4)
여기서 핵심은 Heap 트리다. Heap 트리는 최댓값과 최솟값을 찾는 연산을 빠르게 할 수 있는 완전이진트리다.
Heap 트리 구조를 사용하기 위해서는 Heapq 모듈을 써야 한다. 이 문제를 해결하기 위해 필요한 함수는 다음과 같다.
Heapify(리스트) : 기존의 리스트를 넣으면 해당 리스트를 Heap 트리 구조로 바꿔준다.
Heappop(Heap 트리 구조의 리스트) : 해당 리스트의 트리 최상단 노드를 트리에서 제거하며 그 값을 반환한다.
Heappush(Heap 트리 구조의 리스트, 추가할 값) : 해당 리스트의 트리에 값을 추가한다.
전체 코드
from heapq import heapify, heappop, heappush
import sys
input = sys.stdin.readline
N = int(input())
cards = []
answer = 0
for _ in range(N):
cards.append(int(input()))
heapify(cards)
for _ in range(N-1) :
tmp1 = heappop(cards)
tmp2 = heappop(cards)
answer += tmp1 + tmp2
heappush(cards, tmp1 + tmp2)
print(answer)