[1] 기억해야 할 배운점들
1. 시간복잡도의 개념
빅 오에 따른 Time complexity 그래프의 모습.
시간 복잡도에 상수(constant)는 계산하지 않는다. 현재 내가 배운 시간 복잡도는
- 상수 (O(1))
- 이진 탐색(O(log n))
- 다중 루프문(Nested loops statements)(O(n^n)) 중 이중루프.
"변수" N 이 얼마나 가파르게 변하냐에 따라서 시간 복잡도는 증가하고, 감소한다. 아래에서 우리가 흔히 사용하는 array에서 시간 복잡도를 어떻게 판별할 수 있는지 설명하고, array가 가지는 특징을 설명하려고 한다.
2. Array를 통한 시간복잡도 판단
Array는 내용물을 알 수 없는 상자들을 쭈~~욱 늘어놓은 형태라고 생각하면 된다.
- Array는 정해진 길이를 가진다.(내가 지정하지 않더라도). Array의 각 요소(elements)들은 정해진 칸에 배정되어 있다.
- 우리가 Index에 따라 N번째 상자의 내용물이 궁금할 때는 N번째 상자에 바로 접근해서 열어보면 된다. 하지만! 만약 내가 찾고자 하는 내용물이 몇번째 Index를 가진 지 모른다면? 우리는 N개만큼의 박스를 하나하나 열어봐야 한다. (물론, 특정 index가 아닌 요소의 조회를 위해 이진탐색을 사용 할 수도 있을 것이다.)
- 즉, index번째 Array의 조회에는 'O(1)'만큼의, 내용물 x에 대한 조회에는 'N'만큼의 시간 복잡도를 가진다.
- 삽입과 삭제 또한 동일하다. Array는 정해진 길이를 가지므로, 요소를 추가하는 경우에는 새 Array를 만들고 나머지 Array를 복사해서 새 Array에 붙여넣어 줘야 한다. 따라서 N만큼의 시간 복잡도를 가진다.
- 삭제 또한 그렇다. big O는 최악의 경우를 상정하므로, Array에서 0번째 Index를 가진 요소를 삭제하게 된다면 모든 요소가 한칸씩 앞으로 이동해야 한다. 따라서 N의 시간 복잡도를 가진다.
정리하자면 아래와 같다.
즉, 변수!!가 얼마나 많은 과정(Step)을 거쳤느냐에 따라 효율적이다 / 혹은 비효율적이다를 판별하는 것이 시간 복잡도라고 할 수 있다.
아래부터는 일주일간 배운 것들중 내게 무엇이 부족했고, 무엇을 고쳐나가야 할 지 적어보았다.
[2] 문제 리뷰
이번 주 한주는 진짜 쉽지 않았다. 주 초반에는 파이썬 강의를 빠르게 마무리 하고(비교적 쉬웠으므로) 여유를 가져 보려고 했으나 알고리즘을 시작 한 순간 완전히 깨져버렸다. 알고리즘을 하면서 내가 느낀 문제는 이렇다
1. 문법이 생소함.
Python, Java에 관계없이 내가 생각한 아이디어를 실제 코드로 구현 해 내기가 너무 힘들었다.
2. 디테일이 부족하다.
아이디어, 접근 방법이 모두 맞더라도 디테일이 부족했다. 예를 들어 재귀함수의 경우에는 필히 끝나는 시점이 필요하다. 이 끝나는 시점을 설정 할 때 쉬운 부분들은 따라갈 수 있었지만(자연수의 범위에서만 하겠다~ 라던지)...내 생각에 당연한 것들을 컴퓨터는 당연히 도출하지 못한다.
- 위 사진은 factorial을 구하는 간단한 함수이다. 이 정답에 접근하기까지 꽤 오랜 시간이 걸렸는데, n==1일때 return 까지만썼었다. return 1 을 입력해주지 않아 계속 컴파일 에러가 났었다.
3. 구조에 대한 이해가 부족하다.
- 내 생각에 return은 반복을 끝내고 반환해라...였다.(재귀함수안에서). 그러나 위에서는 if~ return. 의 구조로, return 후의 값이 없다면 "만약 n이 1이면 반환해라." 라는 뜻이 되어버린다. 여기서 구조를 파악하는 것의 중요성을 다시 한 번 느꼈다.
알고리즘 파트에서 내가 느낀 것은 이렇다. 그만큼 어려웠고, 생소했다. 하지만 이런 디테일한 구조화 과정들이나 아이디어를 짜내서 코드를 구현시키는 것들, 그 구현을 위해 고민하고 검색하는 것은 재밌었다. 나에게 재밌었다는 것이 제일 중요하다. 얼마나 어렵든간에 내가 지금 즐겁게 고민하는 시간들이 내게 양분이 되어 줄 것이다.
[3] 해결책들
1. "파이썬 알고리즘 인터뷰" 책 링크
당장 눈 앞의 문제 해결보다는 근본적인 실력 향상을 원해서, 위 책을 배송주문했다. 개념적인 부분부터 잡고 가야한다.
2. "인프런 알고리즘 강의" 링크
현재는 이 강의를 볼 시간이 안나온다. 주말에도 계속 내배캠 강의를 듣고, 문제를 고민하며 살고 있다. 팀 프로젝트에 혹시 조금 여유가 있어서 개인 시간을 가질 수 있거나, 현재 캠프 과정을 수료하고 나서 강의를 들어 볼 생각. 이 강의 + 백준, 프로그래머스 문제들 위주로 풀어볼 생각이다.
3. 무엇보다 익숙해져야 한다.
이해되지 않는 문제들을 이해 될 때까지 풀어보고 있다. 특히 구조에 대한 이해나, 원리에 대한 이해는 반복에서 오는 것 같다. 이진탐색, 재귀함수, 링크드 리스트, 어레이 ... 수업 내용 외에 유투브, 구글링을 통해 더 알아보고 있다.
++ 내게 칭찬할 점들
- 유투브, 구글링 등을 통해 기본 개념을 탄탄히 다지려고 부던히 애썼다. 물론 어려운 말로 설명되어 있었지만...성과가 있었다고 생각한다. 무엇보다 Class, instance(+objects), Method등에 대해서 더 정확히 이해하려고 노력했다. 나는 이제 배운 지 2주차인 학생이니, 기능적인 것들보다 좀 더 근본적으로 (왜 class를 사용하는지, instance는 무엇인지, method는 무엇인지 등) 배워나가는 것이 내게 필요하다고 생각했다.
- 알고리즘을 배워가면서 더더욱 느끼는 것은 객체 지향이 왜 그렇게 중요한지이다. 객체지향의 핵심개념들(Abstraction, Encapsulation, Inheritance, Polymorphism)을 더 찾아보면서 이해를 높였다. 구글링 + 노마드 코더의 유투브 영상으로 대략적 개념을 배웠다. 이 개념들을 체득하고 사용하려면 더더욱 익숙해져야 한다. 무조건 경험하고, 내 손으로 해보자.
- 시간을 허투루 안썼다. 주말 시간 알뜰히 챙겼다. 알고리즘 문제 해결 그 자체를 위해서 쓴 게 아니라 내 지식의 Depth를 위해 사용했다는 것이 더 뿌듯하다.
