패스트캠퍼스 챌린지 08일차

---

[오늘 진도]

Part 2. 알고리즘 이론

Ch 12. 기본 정렬 알고리즘

01. 공간복잡도

02. 버블정렬

---

 드디어 오늘은 알고리즘을 시작하는 날이다. 어제 나 자신도 기특해했지만, 강사님께서도 자료구조를 잘 마치고 여기까지 들었다며 축하와 격려를 해주셨다. 알고리즘을 듣고 나면 자료구조에서 어려웠던 부분이 왜 그렇게 나왔는지 이해가 될 거라고 하셨는데 알고리즘을 다 듣고 난 뒤 자료구조를 들을 때 어떨지 기대된다. 선택정렬과 삽입정렬의 강의 시간이 길지 않아 이 두 개도 듣고 포스팅하고 싶었지만 시간이 별로 없어서 보지 못했다.

 공간복잡도는 과거 컴퓨터의 메모리가 크지 않았을 때, 작은 메모리를 효율적으로 사용하기 위해 나타난 개념이다. 컴퓨터의 용량이 커진 요즘 거의 사용하지 않지만, 빅데이터가 등장하면서 다시 관심받고 있다고 한다. 공간복잡도는 이렇게 간단하게 마무리하셨다. 다음은 버블정렬이다. 버블 정렬은 정보처리기사 공부할 때, 거품이 물 위로 동동 떠 오르는 것처럼 가장 큰 값이 가장 끝으로 올라가는 모양새라고 배웠다. 그 당시에는 1회차, 2회차…. 돌렸을 때 결괏값을 묻는 문제가 많아서 가장 큰 값이 가장 끝에 온다는 식으로 생각하면 문제를 풀 수 있었다. 그런데 그림으로 그려보니 헷갈렸다. 아마 첫 번째 걸 요소로 한 바퀴를 도는데 큰 값을 만나면 어떻게 해야 하는지 헷갈려서 그런 것 같다. 강의자료에 정렬의 움직임을 보여주는 사이트 링크를 올려주셔서 그걸 보고 이해해야 했다. 버블정렬의 순서를 정리해둔 그림으로 코드를 직접 작성해보면서 다시 봐야 할 것 같다. 버블 정렬의 시간복잡도는 O(n^2)이지만 boolean 자료형의 변수를 false로 설정하고, 배열의 요소가 움직이면 true로 바꿔줄 때, 반복문을 멈추게 한다면 복잡도를 낮출 수 있다. 아마 나라면 정렬이 되어도 일단 반복문을 다 돌게 해서 시간복잡도를 낮출 생각을 못 했을 것이다. 역시, 강의 초반에 하신 말씀처럼 하나의 알고리즘에 대해 여러 가지 방법을 코드를 구현할 수 있고, 공간복잡도나 시간복잡도를 낮춤으로써 효율적으로 구현할 수 있다는 걸 직접 보니 신기했다.

 

* 알고리즘과 자료구조를 직접 볼 수 있는 사이트를 공유한다.

https://visualgo.net/en

VisuAlgo - visualising data structures and algorithms through animation

 

---

 

https://bit.ly/3FVdhDa

수강료 100% 환급 챌린지 | 패스트캠퍼스

- 본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다. -