본문 바로가기

코딩테스트/안경잡이 알고리즘 강의3

04강 - 삽입 정렬 (Insertion Sort) 삽입정렬이다! 영상은 이해가 갔지만 블로그에 추가 참고 자료가 있어서 그거까지 이해하고 정리해보겠다 [ 삽입 정렬 ] 각 숫자를 적절한 위치에 삽입하여 정렬한다 이 또한 정렬 알고리즘 중에서는 비효율적인 알고리즘이다 삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 방법이다 하지만 무조건 위치를 바꾸는 다른 정렬 방식과는 달리 삽입 정렬은 필요할 때만 위치를 바꾼다 예전부터 사실 삽입정렬이 잘 이해가 안가서 외우기만 했지 제대로 이해한건 이번이 처음이다 직접 한 싸이클씩 해보면서 이해했다.. 얘의 장점은 정렬할 순서인 숫자의 앞에 숫자들은 이미 정렬이 되었기때문에, 정렬할 숫자가 자기자리 찾아서 들어가면 더이상 그 싸이클에서는 자리를 바꿀 필요가 없다는것이다!! 그래서 얘는 거의 정렬이 끝난 알고리즘에서는 .. 2021. 9. 16.
03강 - 버블 정렬 (Bubble Sort) 다음으로 버블 정렬 알고리즘이다 [ 버블 정렬 ] 옆에 있는 값과 비교해서 더 작은 값을 앞으로 보낸다! 몹시 직관적인 해결 방법이다 바로 가까이에 있는 두 숫자끼리 비교해서 지금 당장의 더 작은 숫자를 앞으로 보내주는 것을 반복하는 것이다! 구현은 가장 쉽지만 그만큼 가장 비효율적인 알고리즘이다 이 과정을 반복하면 한 사이클을 돌고 나면 최댓값이 맨 뒤에 가있다 물론 최솟값이 맨 앞에 있다는 것은 보장할 수 없다 왜냐? 옆의 놈이랑만 비교해서 작으면 앞으로 보내주는 거지 최소값을 찾아서 보내는게 아니니까! 그치만 최댓값은 맨 뒤에 있다 왜냐? 옆의 값이랑 비교하는데 크면 계속 뒤로뒤로뒤로.. 보내니까 사이클 당 최댓값은 맨 뒤에 있을 수밖에 없는 것이다 위의 그림처럼! 예전에 강의들을떈 뭔소리야.. 했.. 2021. 9. 13.
02강 - 선택 정렬 (Selection sort) 알고리즘을 공부할 때 가장 먼저 풀어보는 문제는 '정렬(Sort)' 문제이다. => 정렬만큼 알고리즘의 효율성 차이를 극명하게 보여주는 것이 없기 때문이다!! 먼저 선택 정렬 (Selection Sort) 알고리즘이다 [ 선택 정렬 ] 가장 작은 것을 선택해서 제일 앞으로 보낸다 가장 원시적이고 기초적인 방법이다 수열의 앞부터 뒤까지 훑으면서 최소값을 앞으로 보낸다 그러면 한번 훑고 다음에 훑으면 배열이 앞에서부터 하나씩 줄어드는 것이다 이런식으로! 왜냐면 최소값이 맨 앞에 있으니까 맨 앞에 최소값을 제외하고 나머지 애들끼리 최소값 구해서 앞으로 보내면 되니까! [ 코드 ] 아무튼 위 방법으로 코드를 구현하면 아래와 같다 #include #include using namespace std; // 선택 정.. 2021. 9. 13.