[정글/회고] 알고리즘 특강

오늘 코치님이 간단하게 알고리즘 관련해서 강의를 해주셨는데 내용을 정리해보려고 한다.

 

1. 재귀함수를 짜는 방법

재귀함수는 점화식을 구한 후 점화식을 코드로 나타내는 방법으로 접근하면 쉽다.

코치님의 교수님께서는 base condition과 함수를 구한 후 그것을 코드로 나타내라고 하셨는데 점화식으로 이해하면 쉽다는 이야기인듯

마침 나도 비슷한 방식을 사용하고 있어서 조금은 괜찮은 방향으로 문제를 풀고 있었구나 생각했다.

알고리즘 스터디를 할 때 먼저 문제를 분석한 후 코드 설계(수도 코드 짜기)를 한 후 그에 맞게 코드를 생성하는 연습을 했었는데 괜찮은 방법인듯! 그 때도 어떻게 보면 대기업 합격한 분들의 문풀 팁을 듣고 풀이 방법을 바꾼건데 역시나 잘 하는 사람들을 모방해야 좋은 것 같다.

 

2. 재귀를 사용하는 이유

정렬 알고리즘(예를 들면 퀵소트)과 팩토리얼, 피보나치 수열 등은 재귀로도 짤 수 있고 반복문으로도 짤 수 있다. 

그리고 앞에 나와서 팩토리얼을 백지에 손코딩해보라고 하셨는데 진심 나는 아직 멀었구나 싶었다 ..

입력 예제를 실행시켜봐야 제대로 돌아가는 코드가 맞는지 아닌지를 판단 가능한 수준인가보다.

오늘 이걸 좀 열심히 해야겠다. 근데 생각해보니 오늘 재귀에 대해서 자세히 설명해주셨으니까 내일 이 내용이 시험에 나올듯..? ..

 

암튼. 이진트리를 전위, 중위, 후위순회하는 알고리즘을 재귀 또는 반복문으로 짜보면 반복문이 짜기가 진짜 어렵고 디버깅해서 오류 찾기도 힘들다고 한다. (특히 후위가 가장 힘들다고 함)그래서 재귀를 쓰는 것인데 재귀로 짜면 1초만에 짤 수 있다고 한다. 그래서 재귀를 쓰는 것이라고 한다. 어제 나왔던 퀴즈에서 재귀를 왜 쓰냐는 문제가 있었는데 그에 대한 답변을 예를 들어서 자세하게 해주셨던 것 같다. 나 이 문제 맞힘 ㅎㅎ 코드가 간결해지기 때문이다. 

 

3. 문제 안 풀리면 언제 답지를 봐야 하나요?

지금은 지식을 최대한 많이 습득하는 단계이므로 답안을 보면서 문풀 방법을 많이 많이 익히는 걸 추천한다. 이 단계가 지나고 조금 더 실력을 키우고 싶을 때 오래 생각하면서 문제를 딥다이브해봐라.

 

4. 알고리즘을 대하는 자세

알고리즘 문제 풀이를 왜 하는지에 대해서 설명해주신 것 같다. 내가 떠올린 아이디어 대로 코드를 짤 수 있는 능력을 키우기 위해서..! 

나의 생각을 코드로 그대로 풀어낼 수 있는 능력이 알고리즘 공부의 핵심인 것 같다. 예를 들어 dfs라면 dfs는 노드들을 깊이 우선 탐색하는 겁니다~ 하고 그림 그려서 설명할 수 있을 정도로 알고있으면 되고 그걸 백지 상태에서 코드를 짤 수 있으면 다 배운 것이다. 나는 지금 이걸 할 수 있는 사람이 되려고 하는 거고

 

* 퀵 정렬이 느리고 불안정적인데도 불구하고 자주 사용하는 이유? 

파이썬의 sort()와 c언어의 내장함수?도 퀵 정렬로 구현되어있다고 한다.

 

이 특강 내용을 다시 정리하면서 생각해보니 내일 시험을 수단으로 써야겠다는 생각이 든다.

내 실력이 어디까지 늘었는지 스스로 증명해보는 시간..... 일주일간 대충 했는지 진심으로 개념을 습득했는지 ㅠㅠ 지금 거의 5시인데 새벽 두세시까지 하면 음.. 한 7시간정도? 남았다. 문제 다 풀고 개념 정리 좀 하고 숙소 가야겠다.