이번 포스팅은 알고리즘 특강 후기 글이다.
KB IT's Your Life 7기 커리큘럼 상 코딩 테스트를 위한 알고리즘 특강이 2주간 실시된다.
그래서 이번 기수의 알고리즘 특강은 유튜브에서도 찾아볼 수 있는 '개발남노씨' 강사님이 담당하시게 되었다.
대부분의 개발자를 목표로 하는 사람이라면 한 번쯤 코딩테스트를 경험해봤을 것이라고 생각한다.
내가 KB IT's Your Life 에 전공반 신청할 때에도 코딩 테스트를 본 것 처럼, 거의 모든 경우 반드시 코딩테스트를 거치게 된다.
CS를 공부하는 것과, 개발을 공부하는 것과, PS를 공부하는 것은 생각보다 조금 느낌이 다르다.
CS로 이론을 공부하더라도 실제로 문제를 풀어낼 때 구현하는 것과는 괴리가 있다.
마찬가지로 프론트엔드, 백엔드 개발을 해본다고 하더라도 문제를 풀기 위한 구현력이 상승하는 것은 아니다.
하지만 코딩테스트는 어디에서나, 누구나 거쳐야 하는 관문처럼 자리잡고 있다.
그래서 코딩테스트 공부를 미리미리 해 두는 것이 중요하다.
그런 이유가 있기 때문에 커리큘럼 상에 코딩테스트 특강이 들어있지 않을까.
수업 진행
사실 나는 첫날과 둘째날에 휴가를 써서 제대로 수업에 참여하지 못했다. 수업 처음 진행이 어떻게 되었는지는 잘 모르겠다. 그래서 수업에 대한 회고보단, 실제로 수업이 어떻게 진행되는지를 바탕으로 글을 쓸 생각이다.
우선, 수업에 참여한 인원들에게 공통 노션 페이지에 초대를 해 준다.
메인 페이지에서는 Java와 Python의 이론적인 내용이 있고, 각 회차별로 문제집을 제공해준다.
그리고 KB IT's Your Life 에서는 Java를 기준으로 설명을 해준다.
문제집은 대부분은 프로그래머스에 있는 문제들을 사용하며, 가끔씩 Leetcode 문제도 넣어준다.
코딩테스트 문제들은 프로그래머스 LV2,3 전후의 문제들로 하루에 대략 5~8문제를 풀게 된다.
그러면 구체적으로 어떤 수업을 듣는지 확인해보자.
1일차 - 코딩테스트 개론
첫 날에는 대략적인 코딩테스트에 대한 내용들을 설명해주신다.
자료구조에 대한 내용도 있고, 기본적인 알고리즘도 설명해준다.
하지만 CS에서 배우는 것처럼 해당 자료구조를 구현한다거나, 그 자료구조가 가지는 학문적인 특성을 배우지는 않는다.
단지, 실제 코딩 테스트에서 바로 사용할 수 있도록 어떤 모듈을 사용하는지, 어떻게 인터페이스를 호출하는지 등을 배운다.
알고리즘의 경우도 마찬가지다. 구체적인 "알고리즘" 을 알려주지는 않고, 알고리즘의 패러다임 등을 설명해준다.
그리디 알고리즘이라던가, 분할정복 알고리즘이라던가 말이다.
알고리즘 하나 하나를 뜯어보는 시간은 없고, 문제를 풀 때 어떤 접근법을 사용하는지를 설명해준다.
1주차에는 아주 간단한 문제들을 가져오신다.
코딩테스트의 스타일에 익숙해지고, 입출력이나 모듈을 사용해보는 것에 익숙해지자는 의의를 두는 문제라고 생각하면 된다.
물론 개중에는 조금 어려운 문제들도 있옸다.
개인적으로 주식 가격을 책정하는 문제가 까다롭게 느껴졌다.
해당 문제의 설명은 사진과 같다.
알고리즘 특강이 JAVA를 기준으로 설명하고 있지만, 나는 파이썬이 좋으니까 파이썬으로 문제를 풀었다.
파이썬으로 해당 문제를 두번의 반복을 사용해 O(N^2) 방식으로 구현하는 경우에는 시간 초과로 실패하게 된다.
따라서 알고리즘을 좀 더 효율적으로 개선해야 하는데... 생각보다 마땅한 방법이 떠오르지 않았다.
처음 접근할 때는 값을 비교해야 하니까, 최소 힙으로 구현해야 하는건가 생각해 딕셔너리와 최소 힙을 사용해 구현해봤다.
하지만 이 방법을 사용해도 결국 딕셔너리를 한 번 더 순회하게 되어서 O(N^2) 을 사용하게 되었다.
그렇다면 더 좋은 알고리즘을 만들어야 한다는 것인데...
그래서 힌트를 얻어보니, 스택을 사용하면 된다는 것이었다.
def solution(prices):
stack = []
answer = [0]*len(prices)
for idx, price in enumerate(prices):
while stack and prices[stack[-1]]>price:
last=stack.pop()
answer[last]=idx-last
stack.append(idx)
while stack:
last=stack.pop()
answer[last]=len(prices)-1-last
return answer
스택에 인덱스를 0부터 순회하면서 가격이 떨어지지 않은 경우에 하나씩 쌓아주는 것이다.
나중에 직전 가격보다 가격이 떨어지는 경우에만 쌓인 인덱스들을 LIFO 방식으로 역 순회하면 O(N)에 풀수 있는 문제였다.
역시... 코테는 아이디어가 중요하다.
2일차 - 문자열과 자료구조
둘째날은 문자열을 주로 다루고, 딕셔너리를 집중적으로 사용하기 시작했다.
아무래도 자료구조의 전반적인 특성을 배우고 익히는 과정이었던 것 같다.
그 중에서 개인적으로 전화번호 목록을 리뷰해볼까 한다.
해당 문제는 위 사진과 같다.
전화번호 앞자리의 숫자가 이전에 등록된 숫자로 이루어져 있으면 False를 리턴하는 문제다.
일단 전화번호부의 크기만 봐도 백만개가 있기 때문에 브루트포스를 해버리면 1조번의 순회를 해야 한다.
그러면 당연하게도 시간복잡도에서 터져버리기 때문에 다른 방법을 고안해야 한다.
그럼 이 문제도 해시맵을 사용해야 한다는건가.
처음에는 Radix Sort 방식을 차용해볼까 고민을 했다.
앞자리의 숫자를 가져와서 해시맵에 저장한다면, 10의 단위수를 줄일 수 있게 되니까 말이다.
그러면 총 순회가 1조가 아니라, 평균적으로 100억번을 순회하게 된다. 하지만 이걸로는 불충분할 것이라고 생각했다.
그러면 두번째 자리수도 똑같이 0~9의 버킷으로 구분해버린다면? 평균 1억번으로 줄일 수 있다.
그러면 최대 길이까지 쪼개버리면 O(L)으로 서칭이 가능한거 아닌가?
그렇게 생각하다 보니 Trie 자료구조를 떠올리게 되었다.
학부 자료구조 시간에 Trie를 구현해본 기억이 있다. 구현을 하는데 굉장히 헤맸었던 기억이 난다.
백과사전을 구현하는 문제였다. 단어들의 prefix를 이용해 검색을 할 수 있도록 구현했었다.
잘 생각해보면 이 문제는 결국 백과사전 인덱싱과도 결이 비슷하다는 걸 알 수 있다.
그래서 이 접근법이 틀리지 않았다고 생각할 수 있었다. 그리고 문제를 풀기 위해서 Trie를 구현해봤다.
# 리스트의 크기가 1,000,000 이니까, 완탐을 해버리면? 1,000,000,000,000
# 1조가 나온다. 1 Trillion
# 그럼 Hashmap을 사용해야 할탠데, 접근방법을 모르겠다.
# 그냥 0~9 까지 버킷을 만들어서 100,000 개로 만들어버릴까?
# Trie를 구현해 사용해보기로 했다.
def solution(phone_book):
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node= self.root
for char in word:
if char not in node:
node[char]={}
node = node[char]
node["*"]=True
def start_with(self, prefix):
node=self.root
for char in prefix:
if char not in node:
return False
node = node[char]
if len(node.keys())>1:return True
else : return False
trie = Trie()
for phone in phone_book:
trie.insert(phone)
for phone in phone_book:
if trie.start_with(phone) : return False
return True
처음에는 여기 있는 문제집을 풀면서 자료구조를 구현할 것이라고는 생각해보지 못했는데, 어쩌다보니 Trie를 구현하게 되었다.
어찌 되었던 Trie를 구현해 문제를 해결하는데는 성공했다.
하지만, 이 문제는 당연하게도 자료구조를 구현하는 문제는 아니었다.
"백과사전 방식" 이라는 걸 깨닫는 순간, "정렬" 을 떠올려야 하는 문제였다.
파이썬에서 문자열 리스트를 sort()나 sorted()로 정렬하면 기본적으로 사전식, 즉 lexicographical order로 정렬되기 때문이다.
... 고심해서 Trie를 구현한게 꽤나 헛된 노력이었다는걸 깨달았던 순간이었다.
3, 4일차 - 그래프
3, 4일차는 그래프를 중심으로 수업이 진행됐다.
BFS와 DFS를 이용해서 풀 수 있는 문제들로 구성되어있다.
실제로 BFS와 DFS를 구현할 수 있다면 풀 수 있는 문제들이다.
하지만 문제에 따라서 구현해야하는 방식, 로직의 변경, 제약 조건들 추가되면서 더 복잡하고 어려운 문제로 재탄생한다.
개중에는 아이디어를 떠올리지 못하면 로직 구현 자체가 불가능한 경우도 있었다.
여기서부터는 엣지케이스들을 떠올리고, 해결할 수 있는 능력이 있는지를 파악하는 문제들이 나오기 시작했다.
그래서 이전 시간 문제들에 비해서 어려웠던 느낌이 들었다.
5일차 - 복습과 테스트
한 주의 마지막에서는 지금까지 배웠던 문제들의 개념과 풀이법을 복습하는 시간을 가졌다.
그 후, 오후에는 3시간동안 5문제의 테스트를 보게 되었다.
4문제는 수업 도중에 풀었던 기억이 나서 30분만에 해결했지만, 마지막 문제를 2시간 30분을 다 써도 완벽하게 구현하지 못했다...
물론 그 문제도 문제집에 들어있는 것이지만... 내가 풀어보지 못한 문제였다.
핑계를 대자면... 이틀치 휴가의 공백이 생각보다 컸던 것이 화근이었다.
첫날과 둘째날을 휴가로 결강을 했는데, 3~4일차의 두배의 문제가 들어있었다...
그래서 부랴부랴 문제를 풀어나갔지만, 마지막 4일차의 문제집을 완주하지 못했다.
그런데... 4일차에 있는 문제에서 무려 4문제가 시험에 등장했다.
그래도 BFS, DFS 문제인건 깨닫고 부랴부랴 구현에 들어갔다.
상태를 두가지로 나눠서 각각 BFS로 순회하여 최솟값을 저장해 출력해야 하는 문제였다.
그래서 Flag를 이용해 상태를 나눠서 각각 BFS로 그래프를 순회하도록 만들었지만, 어째서인지 제대로 동작하지 않았다.
언제나 코딩 테스트가 그렇듯, 맨 처음에 들어간 접근 방식이 어긋나면 새로운 방식이 떠오르지 않게 된다.
상태를 나누는 것을, 구현할 Grid 보드에 하나의 차원을 추가해서 저장하면 쉽게 구현되는 문제였지만... 머리가 완전히 굳어버렸다.
그렇게 마지막 문제에서 절반의 테스트케이스만 맞춘 채 시험이 종료되었다.
나에게 하루의 시간을 더 줬더라면... 하는 아쉬움이 남는 시험이었다.
최근 한국 PS의 큰 별이었던 백준 사이트가 서비스를 종료하게 되었다.
백준 사이트는 코딩 테스트를 준비하는 사람들이나, PS를 좋아하는 사람들이 애용하던 문제풀이 사이트였다.
나 또한 코딩테스트를 준비할 때나 스터디에서 가끔씩 사용하던 유용한 곳이었는데, 사라진다니 조금은 아쉽기도 하다.
그런데 금일 기준으로 백준 사이트를 들어가면 채점 서비스를 준비 중이라는 문구가 나온다.
며칠 전까지 서비스 종료였던 것 같은데, 설마 부활하나?
백준은 프로그래머스에 비해서 문제의 종류가 다양하고, 좀 더 엄격한 느낌의 구현을 요구했던 것 같다.
이번 특강을 듣다보니 확실히 PS를 하는 것도 나름 재미가 있다는걸 느낄 수 있었다.
기가막힌 아이디어로 문제를 해결할 때 쾌감이 있다.
백준이 부활하게 된다면 이번에는 제대로 문제풀이를 해 보는게 좋을지도 모르겠다.
최근에 빅데이터 분석기사 필기와, 정보처리기사 필기를 합격했다.
교육을 들으면서 자격증을 공부하기에는 시간이 굉장히 부족하다는 느낌이 든다.
특히 빅데이터 분석기사 필기 시험은 기출에 비해서 문제가 굉장히 난잡했다는 기억이 난다.
그래도 무사히 합격했으니 다행이라고 생각한다.
그리고 최근에 Manim을 공부하고 있다.
아무래도 시각화가 제일 기억에 남는 것 같기도 하고, 전부터 배워보고 싶었기 때문에 조금씩 찾아보고 있다.
시간이 난다면 알고리즘 특강 문제들을 따로 Manim을 이용해서 해설본을 만들어 볼 생각이다.
꽤 재밌지 않을까.
'개발 > KB IT's Your Life 7기' 카테고리의 다른 글
| KB IT's Your Life 7기 - DBMS 훑어보기 (0) | 2026.05.31 |
|---|---|
| KB IT's Your Life 7기 - 코딩테스트 특강 2 (0) | 2026.05.23 |
| KB IT's Your Life 7기 - Java 프로그래밍 2 (0) | 2026.05.10 |
| KB IT's Your Life 7기 - Git 좀 더 잘 써보기 (0) | 2026.05.01 |
| KB IT's Your Life 7기 - Java 프로그래밍 (0) | 2026.04.26 |