📚한 장으로 보는 알고리즘 공부 순서📚

  카이스트에서 진행되는 SW정글 커리큘럼을 바탕으로 작성하였습니다. 나중에 복습할 때 찾아보기 위해 따로 정리를 했습니다. 파트마다 저의 사족이 달려있는데 참고하실 분들을 위해 저의 상황을 말씀드리자면, python으로 학습을 진행하였고 약 4주간 매일 평균 5~6문제 정도 풀었습니다.(풀었다는 말이 부끄럽게 많이 해답을 찾아보긴했는데..) 정글에 입소하기 전 코딩 공부는 국비교육을 이수한 것이 전부입니다. 문과 대학 출신이라 코딩에 대해 전혀 모르는 상황이었고 알고리즘 공부에 있어서는 바닥에서 출발한 것 같습니다.
  이론 공부는 아래 책으로 진행하였습니다!!

Do it! 자료구조와 함께 배우는 알고리즘 입문: 파이썬 편:내 손으로 직접 코딩하며 확인한다

아래 파트는 책의 파트가 아닌 정글에서 나눠주신 파트입니다.

Part 1. 등교준비는 차근차근.🏋🏋

핵심 키워드 :
배열, 문자열, 반복문과 재귀함수, 계산복잡도, 정렬, 완전탐색, 정수론

추천 : 내가 현재 사용하는 언어(예를 들어, Python, C 등)의 기본적인 입출력 방식을 모른다거나, 자료형, 정렬 방식 등을 정확히 알지 못 한다면 반드시 익히고 넘어가야할 파트.

문제번호	주제	문제제목	공부포인트
2557	입출력	Hello World	일단 맞으면 기분 좋음
10869	입출력	사칙연산	/, //의 차이는?
2588	입출력	곱셈	자료형, 자릿수별 출력
2753	조건문	윤년	if else
10871	반복문	X보다 작은 수	반복문(end와sep은 덤)
8958	배열	OX퀴즈	인덱스 , 이중for문
4344	배열	평균은넘겠지	소수점 출력
11654	문자열	아스키 코드	아스키 코드는 든든한 국밥
1152	문자열	단어의 개수	split, remove
2869	수학	달팽이는 올라가고싶다	나는 집 가고 싶다(import math)
1978	수학	소수 찾기	컴퓨팅 사고
10872	재귀함수	팩토리얼	공포의 재귀 시작
1914	재귀함수	하노이 탑	print를 어디에 둘까?
9663	재귀함수	N-Queen	방문한 지역 체크, 재귀
2750	정렬	수 정렬하기	뭐야 쉽네(지옥의 3연벙 시작)
2751	정렬	수 정렬하기2	어? 시간초과?(sys.stdin.readline)
10989	정렬	수 정렬하기3	어? 메모리초과?(도수정렬)
1181	정렬	단어 정렬	글자 크기 순 정렬, 중복제거
2390	완전탐색	일곱 난쟁이	permutation, combination
10819	완전탐색	차이를 최대로	max, abs, itertools 종합선물셋트

  파트1 중 나를 가장 골치 아프게 한 친구는 다름 아닌 재귀(recursion).. 파트1 특성상 여기 나온 개념이나 풀이 방식은 파트4까지 쭈욱 이어지는데 재귀는 아무리 접해도 쉽지가 않았다. 그래도 파트4까지 공부를 마치고 다시 돌아와서 풀어보니 새로운 느낌이었다. 특히, N-Queen을 처음 풀 때만 해도 DFS를 모르다보니까 너무 어려웠는데 DFS를 학습하고 와서 다시 보니 이런 거였구나!! 하게 되는 그런 즐거움이 있다.

Part 2. 엄마 내 교복바지 어딨어?🤔🤔

핵심 키워드 :
이분탐색, 분할정복, 스택, 큐, 우선순위 큐

 추천 : 내가 설계한 논리는 맞으나, 문제를 푸는데 시간초과가 많이 난다면 꼭 익혀야 할 파트. 컴퓨팅 사고로의 전환에서 가장 중요한 파트가 아닌가 싶음. 시간복잡도(time complexity)를 따지지 않고 코드를 짜는 건 컴퓨터과학에서 지양되어야 할 방향임을 절실히 확인.

문제번호	주제	문제제목	공부포인트
2805	이분탐색	나무 자르기	오름차순 정렬 후, start, end값으로 mid를 찾자
2110	이분탐색	공유기 설치	코드가 진행되는 과정을 완벽히 이해해야 풀 수 있음
16564	이분탐색	히오스 프로게이머	start, end를 뭐로 잡을래?
1629	분할정복	곱셈	분할정복은 재귀가 필수, 나머지분배연산법칙
2630	분할정복	색종이 만들기	어디를 기준으로 나눌 지 보이나요?
2261	분할정복	가장 가까운 두점	논리구조 짜기가 까다롭지만 짜고 보면 쉬운.
10828	스택	스택	Last In First Out
9012	스택	괄호	이 문제를 보고 스택을 못 떠올린다면..?
2504	스택	괄호의 값	컴퓨팅 사고 전환이 필요해
2493	스택	탑	시간 빌게이츠도 포기한 내 풀이(완전탐색)
2164	큐	카드2	popleft()는 일단 쓰면 튀어나감
11866	큐	요세푸스 문제 0	deque를 활용한 컴퓨팅 사고
3190	큐	뱀	방향 문제, bfs를 알고나니 다른 문제로 보인다!
11279	우선순위 큐	최대 힙	heappop은 값이 가장 낮은 걸 뱉는다. 그렇다면?
1655	우선순위 큐	가운데를 말해요	가운데를 말하는 tree가 있다?
13334	우선순위 큐	철로	정렬만 잘 한다면 쉬운 문제.

  파트2의 핵심은, binary search, divide and conquer 등을 잘 활용하여 시간 복잡도를 낮추는 거 같다. 처음 공부할 때는 시간복잡도가 뭔지 몰라서 고생했다. 분명 이렇게 하면 답이 나오고 내 비주얼 스튜디오에서도 올바른 답이 출력되는데 제출만 하면 시간초과란다. 이제는 문제를 받으면, n, m 값의 범위부터 확인하게 된다. 물론 그렇다고 하여 시간복잡도를 정밀히 계산하는 건 아니지만, 대충 완전탐색을 하면 시간초과가 뜨겠구나 정도는 파악할 수 있다. 컴퓨터에게 넘겨줄 때 불필요한 부분은 쳐내고 내가 원하는 답을 빠르게 얻을 수 있는 그런 이쁜 코드를 짤 수 있도록 열심히 공부해보자!

Part 3. 그래프🔄를 모르면 너는 갈 수 없다🔙

핵심 키워드 :
그래프(vertex, edge, node, arc), BFS, DFS, 위상정렬

추천 : 주어지는 데이터 간의 관계가 보인다면, 그래프를 그릴 수 있다. 노드 간 연결을 다 했는데 그 다음을 모르겠다면 반드시 익혀야 할 파트.

문제번호	주제	문제제목	공부포인트
1991	그래프탐색기본	트리순회	전위순회, 중위순회, 후위순회
1260	그래프탐색기본	DFS와 BFS	DFS와 BFS를 배우고 싶다면 이걸 꼭 먼저
5639	그래프탐색기본	이진 검색 트리	이진탐색을 생활화합시다!
1197	그래프탐색기본	최소스패닝트리	Kruskal, Prim 알고리즘
11725	DFS	트리의 부모찾기	재귀 구조를 완벽히 이해했다면 쉬움
1707	DFS	이분 그래프	-+-+-+가 핵심
21606	DFS	아침 산책	DFS가 어떤 값을 return하는 지가 포인트
14888	DFS	연산자 끼워넣기	DFS는 재귀다!(조합풀이랑 시간 비교)
2573	DFS	빙산	분할정복, DFS, 방향 삼위일체
2178	BFS	미로 탐색	BFS는 deque을 쓰면 편리해
18352	BFS	특정거리의도시찾기	이 때는 몰랐지 BFS+DP라는 걸
1916	BFS	최소비용구하기	다익스트라 알고리즘(heapq만 썼을 뿐인데!)
7569	BFS	토마토	3차원 BFS
3055	BFS	탈출	BFS가 동시에 2개가 돈다면?
2252	위상정렬	줄세우기	진입차수가 0인 노드부터 시작
2637	위상정렬	장난감조립	위상정렬 구조 잡기 좋은 문제

  알고리즘 공부에 재미를 느끼기 시작한 파트. 문제는 이전 파트들에 비해 어려워 직접 풀지 못 한 문제가 많지만, DFS와 BFS 방식에 대한 기초가 잡히고 나니 다른 사람이 작성한 코드를 봐도 이해하기 수월하였다. 파트3부터 한 알고리즘으로 문제를 푸는 것보다 이전에 배웠던 것을 활용하면 시간을 단축하기가 좋았다. 여담으로 이진검색트리(5639)를 풀 때, 중간 mid값을 찾는 과정이 나오는데 나는 완전탐색을 통해 mid값을 찾았더니 시간⏰이 3700ms이나 나온 반면, 이진탐색을 수행한 코드는 100ms밖에 나오지 않았다. 시간을 줄일 요소가 보인다면 최대한 줄여보자!!

Part 4. 하교 후 분식집. 뭘 먹어야 제일 행복할까?😋🥘😋

핵심 키워드 :
동적 프로그래밍(DP), 그리디

추천 : 재귀, 분할정복은 어느 정도 이해하고 있지만 풀이 상 시간초과 혹은 메모리초과가 발생한다면 공부하기 좋은 파트. 특히, 그리디 알고리즘을 사용하면 대부분 앞서 발생한 문제가 해결될 수 있으나 적재적소에 사용하지 않는다면 '틀렸습니다'를 맞이할 수 있으니 주의!

문제번호	주제	문제제목	공부포인트
2748	DP	피보나치 수2	바텀업, 탑다운 2가지 모두 학습해보자
1904	DP	01타일	점화식을 찾는 게 중요하다!
9084	DP	동전	DP테이블 만들기, 재귀해 구상하기
9251	DP	LCS	DP테이블 x축,y축 잡기
12865	DP	아주 평범한 배낭	Knapsack 알고리즘(국밥 문제)
11053	DP	가장 긴 증가하는 부분 수열	시간복잡도를 고려한 알고리즘 설계
2098	DP	외판원 순회	비트마스킹, 또 등장한 DFS+DP
2253	DP	점프	DP는 모든 테이블을 채워야한다.
11047	그리디	동전 0	앞선 선택이 뒤에 영향을 주면 안된다
1541	그리디	잃어버린 괄호	풀이를 보고 제일 충격받은 컴퓨팅 사고(Thinking)
1931	그리디	회의실 배정	그리디는 정렬이 핵심
1700	그리디	멀티탭 스케줄링	그리디 알고리즘 사용 판단 근거를 찾기

  DP와 그리디 알고리즘 모두 주어진 상황이 최적부분구조(Optimal substructure)를 만족해야 사용가능하며, 재귀해를 가져야한다. 최적부분구조라는 말이 쉽게 와닿지 않았으나, CLRS 책에서 LCS 문제를 친절히 설명해주는 부분이 나오는데 그 부분을 학습하며 최적부분구조에 대해 이해할 수 있었다. 그리디 알고리즘의 경우, 앞의 선택이 이후 선택에 영향을 주지 않아야한다는 조건이 까다로웠다.

  알고리즘 마지막 파트를 하는 중인데도 여전히 컴퓨팅 사고로의 전환은 쉽지 않은 것 같다. 정글 운영진 분들과 티타임을 갖는 시간이 있어 크래프톤 장병규 의장님께 질문을 드렸다. 컴퓨터도 결국 인간이 사고한 걸 수행하는 기계인데 빠른 수행시간을 보이는 코드들을 보면 전혀 이해가 가지않는데 그 코드를 보고 공부하는게 맞는 지 여쭤보았다. 어느 정도 나는 내가 맞다는 생각에 드린 질문이었으나 의장님의 대답은 충격적이었다.

그게 컴퓨터에 적합한 코드이며, 이해가 되지 않는다면 공부하는 초기에는 그 코드를 통째로 외우는 게 필요하다

1541 문제가 딱 좋은 예시인 거 같다. 나의 사고로는 int로 전환하여 앞에서부터 차근차근 계산을 하는 게 맞다고 생각하였고 시간이 오래 걸렸지만 40줄이 넘어가는 코드를 작성하였다. 다른 사람들의 코드를 보는데, 단 10줄도 안되는 코드로 너무나 쉽게 답을 찾는게 놀라웠다. 이런 부분들이 아직 많이 부족한 거 같지만 배우는 재미가 있어 앞으로 달려가 나도 누군가 감탄할 수 있는 그런 코드를 작성하고싶다.