자료구조 = 식재료 , 알고리즘 = 요리
식재료가 있어야 요리를 한다.
자료구조부터 공부하고 알고리즘 공부하자!
1. 자료구조 공부 순서
A. Array
B. List
a. ArrayList
b. vector
c. LinkedList (simple / doubly / double-ended / circular)
d. Stack (array / list)
e. Queue (array / list / priority / deque / circular)
C. HashMap
D. Tree (simple / binary-search / segment)
E. Heap (max / min)
F. Graph (array / list)
G. HashSet
※ 볼드체로 표시한 것은 코테에서 특히 중요한 자료구조들이다.
2. 자료구조 공부 방법
A. 위 목록의 자료구조들을 순서대로 구글 블로그에서 찾아 따라 구현해본다.
a. 한두 번 정도 집중해서 따라쳐보면서, 내부 작동 원리를 파악한다.
b. 특히 멤버변수로 무엇이 선언되었는지, 어떤 메소드를 포함하고 있는지는 암기에 가깝게 파악해야한다.
B. 한 유형의 자료구조를 따라치면서 파악했다면(암기X), 바로 백준 온라인 저지에서 해당 자료구조의 문제를 푼다.
a. https://www.acmicpc.net/problemset?sort=ac_desc&algo=175
문제 - 1 페이지
www.acmicpc.net
b. 가장 기본적인 '스택, 큐' 등의 이름이 붙은 문제를 풀면 된다. 사실상 해당 자료구조를 구현하는 문제이다.
하지만 암기까지 된 것은 아니기 때문에 잘 안 될 것이다.
괜찮다. 다시 따라 구현하면서 문제를 해결하자.
c. 이제 해당 자료구조를 이용해서 푸는 문제로 보이는 것들을 골라서 풀기 시작한다.
이때부터는 구현된 코드를 보면서 풀면 안 된다. 암기해서 풀어야 한다.
개인차는 있겠지만 10 문제 내외 풀다보면 입맛에 맞게 자료구조를 변형해서 문제를 풀고 있는 자신을 발견한다.
C. 자바의 경우 Array, ArrayList, HashMap, HashSet 등을 문제에서 직접 구현해서 쓰는 경우는 많이 없는
것 같다. 다만 이들의 내부 작동원리나 거기에 포함된 개념들은 매우 중요하기 때문에 반드시 공부해놔야 한다.
https://d2.naver.com/helloworld/831311
1. 알고리즘 공부 순서
<A 그룹>
A. Big-O 표기법
----------------------------------------------------------------
<B 그룹>
B. 정렬
a. slow: 선택정렬, 삽입정렬, 버블정렬
b. fast: 합병정렬, 퀵 정렬, 힙 정렬
C. String (문자열)
----------------------------------------------------------------
<C 그룹>
D. Exhaustive Search (완전탐색, Brute Force Search)
E. Greedy (탐욕법)
F. Divide and Conquer (분할 정복)
----------------------------------------------------------------
<D 그룹>
G. Recursion (재귀)
H. DFS, BFS (깊이우선탐색, 너비우선탐색)
I. Dynamic Programming (DP, 동적프로그래밍)
J. Backtracking
2. 알고리즘 공부 방법
A. 우선 A그룹의 'big-O 표기법'은 공부해야 한다.
a. 면접에서 big-O 표기법의 개념에 대해 묻거나, big-O를 고려한 문제풀이를 요구할 수 있기 때문이다.
B. B그룹의 문자열은 문제를 정말 많이 풀어보자. 정렬은 요즘 입사 코딩테스트에 잘 안 나온다고 하더라...
a. 문자열 문제는 닥치는대로 풀어라.
보통 첫번째 문제는 지원자의 간도 좀 보고, 긴장도 풀어줄 겸 문자열 문제를 주는 경우가 많다.
여기서 버벅대면 시험의 리듬을 되찾기 힘들다.
char, char[], String, String[], StringBuilder 등의 개념, 사용법, 캐스팅 정도는 손가락이 기억하고 해내야 한다.
b. 정렬은 한두 번쯤 구현을 따라해보며 내부 작동원리를 파악해놓을 필요는 있을 것 같다.
C. C그룹은 제어문만 가지고도 문제를 해결할 수 있는 알고리즘 그룹이다.
a. 완전탐색은 개인적으로 중요하다고 생각한다.
일단 컴퓨터의 연산 능력에 대한 감을 익힐 수 있기 때문이다.
따라서 big-O 표기법에 따른 각 문제 해결 전략의 효율성을 가늠해볼 수 있는 지표로서의 역할을 한다.
또한 문제의 풀이 방법이 잘 생각나지 않을 때, 완전탐색의 접근법으로 풀려고 하다보면 적합한 알고리즘이 생각날 때도 있다.
b. C그룹을 공부하려니 지겨워서 자꾸 텐션이 떨어지는 느낌이 든다면 C그룹을 건너뛰고 D그룹을 먼저 공부할 것을 추천한다.
D. 컴퓨팅적 사고력의 꽃, 재귀
a. 일단 지나가는 문제 중 절반은 재귀의 개념에 기초한 알고리즘으로 풀어내는 것 같다.
다시 말하면, 재귀가 익숙하지 않으면 문제를 효율적으로 풀어낼 알고리즘을 익힐 수 없다는 뜻이다.
그런데 보통 사람이라면 아주 기초적인 재귀의 풀이결과도 이해가 안 될 것이다.
그건 당연한 것이니 너무 실망하지 않아도 된다.
b. (재귀 접근 팁)
재귀를 이용한 풀이를 따라가다보면 뭔가 결론이 나기도 전에 자기 또는 다른 함수를 호출해버린다.
그래서 그걸 쫓아가면 머리가 과부하된 채로 길을 잃는다.
이때는 다음의 순서로 문제를 파악해본다.
1. 문제가 해결되는 과정을 머릿 속에 그려보고 비슷한 작업이 반복되는 것을 발견한다.
2. 한 작업과 이어지는 작업이 어떤 유사성을 갖는지 파악한다.
3. 유사성을 파악했다면 그 작업의 '끝'으로 간다.
4. 사건들의 끝에서 작업할 내용과 반환할 내용을 생각하여 재귀 호출을 끝낸다.
5. 다시 앞으로 가서, 각 작업들에서 작업할 내용과 다음 작업에 넘겨줄 내용을 생각하여 재귀적으로 호출한다.
c. 기초적인 재귀 함수의 감을 잡는 데에는 '트리 순회', '피보나치 수열', '팩토리얼'의 구현을 따라해보자.
d. 그 이후에 백준 온라인 저지에서 '하노이 탑 이동 순서(11729)', '별 찍기 - 10(2447)' 등을 풀어보면 된다.
e. 흐름을 하나하나 통제하려고 하지 말고, 구조를 만드는 것에만 집중하고 그 구조를 신뢰해주면 쉽게 감이 잡힐 것이다.
어차피 잘못된 구조라면 원하는 결과가 나오지 않을테니 그때가서 흐름을 보고 구조를 손봐주면 된다
f. DFS, BFS, DP, Backtracking 등의 알고리즘은 해당 알고리즘을 잘 설명해놓은 블로그 찾아보고 관련된 기초
문제부터 풀면 된다. 얘네는 끝이 없는 것 같다.
[참고하면 좋은 글]
https://baactree.tistory.com/52
알고리즘 공부, 어떻게 해야하나요?
오랜만에 정상적인 포스팅을 쓴다. 메일로 가장 많이 물어 보는 질문들이 [알고리즘 공부 어떻게 해야하나요? 어떻게 하셨어요? 뭘 공부해야 할 지 모르겠어요.] 와 같은 질문들이다. 위 질문에
baactree.tistory.com
https://qkqhxla1.tistory.com/990
취업을 위한 알고리즘 공부법.
자소서 : http://qkqhxla1.tistory.com/797 면접 후기 : http://qkqhxla1.tistory.com/799 내가 한 공부들과 방법 : http://qkqhxla1.tistory.com/802 취업을 위한 알고리즘 공부법 : http://qkqhxla1.tistory..
qkqhxla1.tistory.com
※ 알고리즘 초보가 나름대로 파악한 공부법입니다. 틀린 사실이 있거나 보완할 내용이 있다면 지적해주시면 3대가 흥할 것입니다.