크래프톤 정글 2기 1주차 후기

1주차를 마무리했다.

 

1주일간 알고리즘 첫 주 파이썬 문법에 익숙해질 수 있는 기초 문제들과

수학, 재귀, 정렬, 완전 탐색순으로 이어지는 40개 가량의 문제를 풀었던거 같은데

미니 프로젝트로 몰입 환경을 경험한 뒤라 그런 건지 1주 차라 문제가 쉬워서 그런 건지

그렇게 싫어했던 백준 문제에 재미가 붙는게 느껴진다.

이왕 시작한거 그동안 등한시하고 기술면접의 광탈 원인이었던

(Q:  퀵소트가 뭔지 알아요?? A:  빠른거요..)

알고리즘과 자료구조를 다시 한번 차근차근 공부할 수 있는 기회를 놓치고 싶지 않다.

 

 

반드시 해야지

 

이번주 키워드

 

재귀 호출 - 재귀 호출이란 함수 내부에서 함수 자기자신을 또 호출 하는거, 반드시 호출을 종료할 조건문이 필요하다(중요**)

 

시간 복잡도  - 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석

알고리즘으로 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마나 걸리는가?

빅오 표기법을 주로 쓴다 ("이 알고리즘은 평균적으로 이 정도 걸려"보단 "아무리 못해도 절대 이 정도는 된다"가 더욱 신빙성이 높고 평균적인 시간만으로는 최악의 경우를 보장할 수 없댄다)

입력값에 상관없이 즉시 출력값을 얻을수있는 O(1)

입력값에 따라 출력값이 로그함수처럼 오르는 ex)이진탐색 O(log n) 

입력값에 따라 시간또한 똑같은 비율로 증가하는 O(n)

ex)병합정렬 O(n log n) 

(여기부턴 비효율 적이라고 판단) ex) BubbleSort O(n^2) 

ex) 피보나치 수열 재귀 O(2^n)  

O(n!) 

Faster O(1) -> O(log n) -> O(n) -> O(n log n) -> O(n^2) -> O(2^n) -> O(n!) Slower 이 순이다.

 

공간 복잡도  - 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

평균적인 컴퓨터 성능이 좋아져 전보단 중요도가 떨어진다. 알고리즘은 시간 복잡도가 중심

 

quick sort - pivot 값을 설정해 정렬하는 알고리즘(파이썬의 list.sort 도 퀵정렬이다) 

중요 특징 : 병합 정렬은 항상 정 중앙을 기준으로 단순 분할 후 병합 시점에서 값의 비교 연산이 발생하는 반면, 퀵 정렬은 분할 시점(pivot을 기준으로)부터 비교 연산이 일어나기 때문에 그 이후 병합에 들어가는 비용이 매우 적거나 구현 방법에 따라서 아예 병합을 하지 않을 수도 있다. -> pivot값을 어떻게 설정하는지가 가장 중요하다 (O(n log n)의 복잡도에서 최악의 경우 O(n^2)까지도 떨어진다.)

 

insertion sort - 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여 삽입정렬하는 알고리즘

중요 특징 : 안정적인 정렬 방법, 알고리즘 간단, 정렬할 데이터의 크기가 클시에 적합하지않다. O(n^2)의 시간 복잡도

 

merge sort - 주어진 배열을 원소가 하나만 남을때까지 둘로 쪼개고 크기순으로 배열하면서 합치는 정렬 알고리즘

중요 특징 : 분할과 병합, 두개의 배열을 병합할떄 담아놓을 배열이 추가로 필요하다, 시간 복잡도는 O(n log n)이다.

 

heap sort - 최대 힙트리나 최소 힙트리를 사용해 정렬하는 알고리즘

 

힙(Heap)? - 완전이진트리 기반 자료구조, 여러개 값중 가장 큰값이나 가장 작은 값을 빠르게 찾기 위해 만들어진 자료구조 

부모노드의 키값이 자식노드의 키값보다 크거나 작다(항상 성립), 시간 복잡도는 O(n log n)

왼쪽 자식의 인덱스 = (부모 인덱스) * 2

오른쪽 자식의 인덱스 = (부모 인덱스) * 2 +1 

부모 인덱스 = (자식의 인덱스) / 2 

 

quick sort를 가장 많이 쓰는 이유? - ex)머지소트 정렬하려면 추가적인 공간이 필요하지만 퀵소트는 추가적인 공간 x  최악의 경우가 있지만 확률적으로 속도가 가장 빠르다.

 

stable한 정렬이란 무엇인지? - 정렬되지 않은 상태에서 같은 키를 가진 원소의 순서가 정렬후에도 유지되는 정렬

정렬 전

안정 정렬

불안정 정렬

ps. 사실 재미없ㄷ