[TIL] 알고리즘 강의를 들으며...

*20221110의 회고

 

   오늘은 오전부터 하루종일 알고리즘과 자료구조 강의를 들었다. 내배캠에서 제공된 강의는 사용하는 언어가 파이썬이라 파이썬 문법에 맞춰서 알고리즘과 자료구조를 설명해준다. 그러나 나는 코테를 자바로 공부하고 있는 입장이기 때문에, 문제를 푸는 방법에 대해서 설명을 해주면 자바로 구현은 할 수 있고, 알고리즘과 자료구조의 원리에 대해 설명해주면 원리를 이해할 수는 있어서 문제가 없다고 생각을 했다. 그러나 오늘 강의를 들으면서, 자료구조를 구현해보는 실습을 진행하는데 파이썬으로 구현하는 모습을 보니 조금 헷갈리기 시작했다. LinkedList 를 구현해보는 실습이였는데, 보면서 이해가 잘 되지 않아 구글링을 하면서 들었다. 그래서 든 생각은, 자바로 된 알고리즘 자료구조 강의가 있으면 좋겠다 하는 생각이였다. 스파르타 코딩클럽 사이트에 들어가보니 알고리즘 자료구조 관련 강의는 파이썬을 사용하는 강의 하나밖에 없었다.. ㅠㅡㅠ 그래서 너무 슬프다 흑흑 ...ㅎㅎ

 

   아무튼 오늘 배운 개념들을 회고해보려 한다. 아니 학부때는 그렇게 낯설고 어려웠던 시간복잡도, 공간복잡도가 용어는 한번 들어봤다고 익숙한 건지, 강의에서 설명해주는데 어려움 없이 이해가 쏙쏙 되었다. 역시 공부하고자 하는 마음만 있으면 어려울 건 없구나 생각했다. 학부 땐 내가 이걸 왜 듣고 있나 하면서 억지로 수업을 들었기 때문에 이해하려는 노력조차 안했던게 아닐까...ㅋㅋ 나 정말 학부 때 왜 공부 안 했니 ~ ~!! 증말 너 좀 혼나자....

 

- 시간 복잡도 : 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계

- 공간 복잡도 : 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계

    -> 대부분의 문제에서는알고리즘의 성능이 공간에 의해서 결정되지 않는다. 따라서 공간 복잡도 보다 시간 복잡도를 더 신경써야 한다.

 

- 점근 표기법 : 알고리즘의 성능을 수학적으로 표기하는 방법, 알고리즘의 "효율성"을 평가하는 방법. 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법.

    - 빅 오(Big-O) : 최악의 성능이 나올 때 어느정도의 연산량이 걸릴 것 인지

    - 빅 오메가 (Big-Ω) : 최선의 성능이 나올 때 어느정도의 연산량이 걸릴 것 인지

    -> 알고리즘의 성능은 입력값에 따라, 입력값의 분포에 따라 변화할 수 있음.

 

- 알고리즘에서는 거의 모든 알고리즘을 빅 오 표기법으로 분석한다. -> 최악의 경우를 대비해야 함.

- 문제를 앞으로 풀 때 마다 시간&공간 복잡도를 고려해보자!

    - 입력 값에 비례해서 얼마나 늘어날지 파악해보자

    - 공간 복잡도 보다는 시간 복잡도를 더 줄이기 위해 고민하자

    - 최악의 경우에 시간이 얼마나 소요될 지(빅 오 표기법)에 대해 고민하자

 

- 배열(Array)

    - 크기가 정해지면 바꿀 수 없음

    - 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 함 -> 최악의 경우 배열의 길이 N만큼 옮겨야 하므로 O(N)의 시간 복잡도를 가짐

    - 원소를 새로 추가하려면, 새로운 공간을 할당해야 하므로 매우 비효율적

 

- 연결리스트(LinkedList)

    - 각 원소는 다음 원소를 연결짓는 연결고리로 이어져 있다.(=리스트 : 크기가 정해지지 않은 데이터의 공간, 자유자재로 늘어남)

    - 리스트는 특정 원소에 접근하려면 연결 고리(포인터)를 따라 탐색해야 한다. -> 최악의 경우 모든 노드를 탐색해야 하므로 O(N)의 시간 복잡도를 가짐

    - 원소를 중간에 삽입/삭제 하기 위해서는 앞 뒤의 포인터만 변경하면 됨 -> 원소의 삽입/삭제를 O(1)의 시간복잡도 안에 할 수 있음

    - 데이터가 연속된 위치에 저장되지 않고, 모든 데이터가 데이터부분, 주소 부분을 가지고 있음

 

=> 데이터에 접근하는 경우가 빈번하다면 -> Array 사용 (Array : O(1), LinkedList : O(N)),

      삽입과 삭제가 빈번하다면 -> LinkedList 사용 (Array : O(N), LinkedList O(1))

 

+ 강창민 튜터님께서 실시간 강의로 해주신 말씀인데, 자료구조를 선택할 때 1.삽입시간 2.삭제시간 3.검색시간 4.정렬여부 이 4가지를 고려해서 선택을 하라고 하셨다. 오늘 배운 내용들 잘 기억하자! 그럼 이제 남은 강의를 들으러 가야겠다. 오늘하루도 너무 수고 많았고 내일은 더 더 열심히 해보자!!