학습 방법을 바꿔보기.

알고리즘 공부에 대한 마음의 장벽이 높아진다. 나는 공부를 꼼꼼히 하는 편이고, 새로운 것에 적응할 때 시간이 필요한 타입이다. 부트캠프 특성상 다양하게 배우다보니 (알고리즘, AWS, 실전 프로젝트, 자바, 파이썬, 자바스크립트 등등..) 마음은 조급한데, 익숙해지지는 않아서 재미를 붙이기가 어려웠다.

 

부트캠프는 압축 성장에 최적화 되어 있다. 압축 성장이 가능한 이유는, 커리큘럼보다도 동료들 덕분이다.

나와 같이 시작한 팀이 앞서가고, 때론 날아다니는 걸 보면 긴장하고 자극받는다.

그런데 압축적인 스트레스도 함께온다.

 

내가 익숙했던 경영/문과 공부는 시간에 비례해서 성장할 수 있었지만, 프로그래밍 공부는 외국어 공부와 비슷해서, 절대적인 시간과 공부량이 필요했다. 그래야만 한 단계를 넘을 수 있다. 알고리즘을 풀 때는, 내가 느리다는 걸 매 순간 자각했기 때문에 (물론 다른 영역에서도..), 하기 싫어졌다. 새로운 집에 적응하고, 개인적인 사정 등 여러 변화를 겪으면서 이미 에너지를 많이 썼고, 알고리즘이라는 새로운 과목 앞에서 뒷걸음치게 됐다.

 

오늘은 잠깐 멈춰서, 공부법을 바꿔보았다.

 

(1) 강의 목차를 꼼꼼히 보기.

(2) 조용한 시간에 슬랙/게더 끄고 공부하기 (9시 이전, 오전 6시 이후 시간)

(3) 시각화 (Python tutor, 공책에 필기)

(4) 시간이 조금 걸려도, 천천히 이해갈때까지 하기. 조바심은 갖지 말되 어느정도의 top-down은 적용할 것.

(5) 앞으로 해야할 것: 백준 단계별로 풀기 주 2회씩 하기.

늘 강연부터 들었는데, 자꾸 중간에 멈추다보니 몰입도가 떨어졌다. 나는 영상보다 글에 대한 집중도가 높기 때문에, 오늘은 강연 노트를 먼저 보고 흐름을 이해해보기로 했다.

• 1주차: 시간/공간 복잡도, 알고리즘 구현력 기르기
• 2주차: 어레이, 링크드 리스트, 이분탐색, 재귀 (데이터 탐색, 삽입, 정렬, 삭제)
• 3주차: 정렬, 스택, 큐, 해쉬 - 코딩테스트의 대표적인 자료 구조. 어떤 경우에 쓸까?
• 4주차: 힙, BFS, DFS, Dynamic Programming
• 5주차: 종합 알고리즘 문제 풀이

왜 튜터님은 목차를 이렇게 짰을까?

 

1주차는

이렇게 시작한다. 알고리즘 공부를 왜 해야할까?

좋은 개발자가 되려면, 좋은 프로그램을 구현해야 한다. 좋은 프로그램은 적은 공간을 이용해서 빠른 속도로 수행되는 프로그램이다. 다양한 경우에 따라, 최선의 자료구조/접근 방법이 다르기 때문에 여러 자료구조/방법을 숙지해야 한다.

 

2주차에서는

어레이(배열)와 링크드 리스트의 차이점,

이진 탐색의 효율성과 전제조건,

재귀 함수의 방법과 전제조건에 대해 배운다.

 

어레이는 캡슐 호텔, 링크드 리스트는 화물칸으로 이어진 열차라고 생각해보면 이해가 쉽다.

-배열은 크기가 정해진 데이터의 공간이기 때문에, 한 번 정해지면 바꿀 수 없다. 방이 9개 있는 캡슐 호텔인데, 만실인 상황에서 손님이 9명 더 오신다면? 호텔을 새로 지어야 한다.

*원소를 새로 추가하려면, 다시 새로운 공간을 만들고 할당해야 하기 때문에 매우 비효율적인 자료구조다.

-배열은 원소에 즉시 접근할 수 있다.

-배열은 원소를 중간에 삽입/삭제하려면 모든 원소를 다 옮겨야 한다. 최악의 경우 배열의 길이 N만큼 옮겨야 하기 때문에, O(N)의 시간 복잡도를 가진다.

 

링크드 리스트를 화물칸에 비유할 때, 화물 열차 칸은 노드, 연결 고리는 포인터라고 생각해보자.

 

-배열과 달리 크기가 정해지지 않은 데이터의 공간이다. 즉, 연결고리로 이어주기만 하면, 자유롭게 늘어날 수 있다.

-인덱스로 탐색하는 배열과 달리, 리스트는 연결고리를 따라 탐색한다. 최악의 경우에는 모든 경우를 탐색해야 하므로 O(N)의 시간 복잡도를 가진다.

-리스트는 원소를 중간에 삽입/삭제 하기 위해서는 앞 뒤의 포인터만 변경하면 된다. 원소 삽입/삭제가 O(1)의 시간 복잡도 안에 가능하다.

 

이진 탐색과 순차탐색

이진 탐색은 범위의 절반씩 후보를 줄이면서 탐색을 시도해보는 것이다. (EX. 100이 있다면, 50을 시도해보는 것.)

단, 이진 탐색은 일정한 규칙으로 정렬 되어 있을 때만 가능하다.

 

재귀함수란?

재귀 (recursion): 어떠한 것을 정의할 때, 자기자신을 참조하는 것.

재귀 함수는 반드시 빠져나가는 지점을 명확하게 해줘야지, 무한 루프에 빠지지 않는다.

 

3주차는

정렬, 스택/큐, 해쉬에 대해 배운다.

들어가기 전에 각 알고리즘을 한 마디로 정리해보자.

정렬: 데이터를 순서대로 나열하는 방법.

Stack: Last in, first out

Queue: first in, first out

해쉬: 알고리즘으로 문자열을 고정된 길이의 데이터로 만들 때 씀.

 

정렬

정렬이란? 데이터를 순서대로 나열하는 방법.

이진 탐색 / 데이터의 효율적인 탐색을 가능하게 함.

 

(1) 버블 정렬

앞과 뒤 비교해서 자리를 교체하면서 정렬하는 방식

*파이썬에서 두 변수의 값 교체하는 법

a,b = b,a

*range는 보통 (1,10) 이런 식으로 인자를 2개 넣는다. range는 파라미터 1개만 가질 수도 있다. range(a)의 형태로 들어가게 되면, 0부터 a-1까지의 숫자를 뜻한다. 즉 range(4)라면, 0,1,2,3 이다.

배열의 크기 -1 인 4만큼 반복 후-> 하나씩 줄어들면서 반복합니다.

(2) 선택 정렬

버블 정렬과 달리 "최솟값" 을 찾아 변경한다.

(3) 삽입 정렬

선택 정렬은 전체에서 최솟값을 선택하는 반면, 삽입 정렬은 전체에서 하나씩 올바른 위치에 삽입한다.

선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾼다.

반면, 삽입 정렬은 필요할 때만 위치를 변경한다.

 

 

알고리즘을 풀면서, (1) 시각화하기 (2) 공책에 써가면서 풀기 가 집중하고, 이해하는 데 정말 큰 도움이 됐다.

Pytutor는 알고리즘 코드를 넣으면, 거치는 모든 단계를 시각화해주는 엄청난 툴이다 (단연코 코딩을 시작한 후 알게 된 최고의 리소스다) 이 코드를 쪼개보면 58단계로 나눌 수 있는데, 그걸 직접 손으로 해보면, 선택정렬이 비효율적이군 이라는 것을 몸소 배울 수 있다.. 비슷한 코드로 해보면, 삽입정렬은 39회 정도로 훨씬 짧다. 아래 삽입정렬에는 break 문이 있다. bubble 정렬과, 선택 정렬은 O(N^2) 만큼 반복해서 비교해야 한다. 반면, 삽입 정렬은 비교를 안해도 되는 순간에는 Break 를 하도록 한다. 시간 복잡도 최선의 경우에는 N이다. (거의 정렬이 된 상태의 배열을 입력했을 때, 삽입 정렬은 특히 이득이다)