🗒️ 시간 복잡도, 공간 복잡도(Big-Oh Notation)
- 시간 복잡도에는 O(n) - 시간의 상한(최악의 경우), Ω(n) - 시간의 하한(최선의 경우), Θ(n) - 평균적인 경우
- 시간은 한계치가 명확한 반면 공간은 최근 대용량 시스템이 보편화 되면서, 공간 복잡도 보다는 시간 복잡도가 우선이 된다. 그래서 시간 복잡도가 더 중요하게 생각된다.
- 공간 복잡도를 줄이는 방법은 배열의 크기, 동적할당, 재귀호출 수 등으로 줄일 수 있습니다.🗒️ Quick sort, Insertion sort, merge sort, heap sort
- O(n log n) : 퀵 정렬(quick), 힙 정렬(heap), 병합 정렬(merge)
- O(n^2) : 삽입 정렬(insertion)Quick sort를 가장 많이 쓰는 이유
최악의 경우에는 O(n^2)일 정도로 안 좋은 성능이며, Merge sort와 같이 최선, 최악, 평균의 경우에 상관없이 O (n log2 n)을 보장하지 않지만 가장 많이 쓰인다.
이유는??
- 퀵 정렬의 루프는 대부분 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계 되어 있다.
- 메모리 참조가 지역화되어 있어 CPU 캐시의 히트율이 높아지기 때문이다.메모리 참조의 지역화 - 학자들의 연구 결과에 따르면 어던 메모리를 참고하면 그 다음은 주변 메모리를 참조할 확률이 높다는 특성이 있다.
그래서 가깝거나 연속된 위치에 있는 메모리 데이터를 사용하는 프로그램은 그렇지 않은 프로그램보다 속도가 매우 빠르다. 캐시미스가 발생하면 OS가 캐시 메모리를 정리해야 하고 그동안 연산을 멈춰야 하기 때문에 실행 시간이 늘어난다.
퀵정렬은 재귀가 일어나면서 리스트의 크기가 작아지고, left, right 인덱스는 1씩 커지거나 작아지므로 분할이 일어날수록 가까운 인덱스 항목을 참조하기 때문에 캐시미스가 적다. 그래서 가장 빠르고 많이 사용한다.
캐시 히트율 - CPU가 원하는 메모리가 캐시 메모리에 저장되어 있는 상태이고 그 반대는 캐시미스이다.
🗒️ stable한 정렬이란?
- 중복된 값들을 정렬 했을 경우, 그 값들의 순서가 변하지 않으면 stable 정렬, 변하면 unstable 정렬이다.
- [ 1, 2, 3, 4(1), 4(2), 5] - stable
- [ 1, 2, 3, 4(2), 4(1), 5] - unstableStable Sort
- Insertion Sort
- Merge Sort
- Bubble Sort
- Counting Sort**Unstable Sort
- Selection Sort
- Heap Sort
- Shell Sort
- Quick Sortdfs 기본 쌓기
| NO | 유형 | 제목 | 비고 |
|---|---|---|---|
| 15649 | 백트래킹 | N과 M(1) | |
| 15650 | 백트래킹 | N과 M(2) | |
| 15651 | 백트래킹 | N과 M(3) | |
| 15652 | 백트래킹 | N과 M(4) | |
| 15654 | 백트래킹 | N과 M(5) | |
| 15655 | 백트래킹 | N과 M(6) | |
| 15656 | 백트래킹 | N과 M(7) | |
| 15657 | 백트래킹 | N과 M(8) | |
| 15663 | 백트래킹 | N과 M(9) | |
| 15664 | 백트래킹 | N과 M(10) | |
| 15665 | 백트래킹 | N과 M(11) | |
| 15666 | 백트래킹 | N과 M(12) |
❗️❗️❗️ 이거 다 비슷한 문제긴한데 한번씩 해보면 어떤 구조로 방문체크하고 돌아가는지 조금은 이해 할 수 있게 됨
🔺 외판원 순회2 문제중에 계속 35%에서 틀렸다고 나옴
-> 마지막에 출발점으로 돌아올 때 갈 수 없는 경우에도 0을 넣어서 계산하고 있었음.
이유를 모르면 방법도 알 수 없다.
" 대부분의 경우 사람들은 자신의 행동을 올바른 방향으로 이끌기보다는 비참한 결론이 도출되는 방향으로 따라가곤 한다. 철학적 훈련을 받은 사람은 고통과 쾌락에서 벗어나기 위해 초연함을 탐구해야 한다. 삶과 죽음에 매달리는 짓을 멈추기 위해서도 초연함이 필요하다. 재산과 돈에 관해서도 마찬가지이다. "
- 무소니우스 루푸스, 강의록, 6.25. 5-11
" 지금 이렇게 하는 것이 최선의 길인가? " 그리고 이 일은 내가 왜 하고 있는지를 알아야 한다. 이유를 알지 못하면 방식이 옳은 것인지 틀린 것인지도 알 수 없다.
일단 시작하라. 나머지는 따라온다.
" 스승으로서 나의 목표는 자네를 완성시키는 것이야. 제약받지 않고, 충동적인 행동으로 부터 자유로우며, 거리낌 없는 삶을 살아갈 수 있도록 자네를 가르칠 것이네. 사회와 타인의 눈치를 보지 않는 자유로운 삶, 구속받지 않는 행복, 그리고 하찮은 사물들 속에서도 신의 섭리를 꿰뚫어 볼 수 있는 혜안을, 자네는 이 모든 것을 부지런히 배우고 연습해야 할 것이야. 자네가 올바른 마음을 가졌고 내가 바른 목표를 제시하고 교육했다면 왜 이 과제를 완수하지 못하겠는가? 모든 것은 실현 가능할 뿐더러 이미 우리 안에 있다네. 지난 일은 잊어버리게나. 지금부터가 시작이야. 나를 믿고 앞을 보게나. "
- 에픽테토스, 대화록, 2,19.29-34
나이가 들수록 실패에 대한 두려움은 더욱 커진다. 하지만 그런 두려움이 우리를 위협하도록 내버려두지 말아야 한다. 우리가 느끼는 두려움은 대부분 실체가 없다. 그저 느낌일 뿐이다.
" 일단 시작하라, 나머지는 따라온다 "
죽음 속에 깃든 아름다움
" 시간의 작은 조각들이 자연에 순응하며 흘러가면, 마치 잘 익은 올리브 한 알이 땅에 떨어지는 것처럼 우리의 마지막 안식처가 우아하게 다가온다. 이 모든 생명을 기른 대지를 찬미하라. 우리를 키워준 나무들에게도 감사하라. "
- 마르쿠스 아우렐리우스, 명상록, 4.48.2
모두가 간과하고 넘어가는 것에 축복과 조화가 숨어 있다. 자연의 순리에 따라 세상을 바라보면 죽음 속에도 아름다움이 깃들어 있다.
첫 주이기도 하고, 알고리즘 주차 중에서 가장 간단한 문제들을 풀기 때문에 아마 다음 주차부터는 이런 여유시간이 없을 것 같아서 정글에 오게 되면 하고싶었던 것 중 하나인 서울 다녀오기를 미리 했다. 서울숲까지 가는게 목표였는데 친구를 만나게 되서, 낙성대 주변만 구경하면서 리프레쉬하고 왔다. 조금이라도 이렇게 리프레쉬를 해서 다음 주도 잘 버틸 수 있을 것 같다. 덕분에 오늘 공부는 너무 조금밖에 못했지만 그래도 뭐든지 잘 해내는 사람은 일 할 땐 일 하고 , 쉴 땐 쉬는 사람이라고 생각한다. 조금 쉬었으니 다가올 일주일을 더 열심히 하자!
