재귀의 장점은 프로그램이 간결하다는 장점이 있지만, 스택 메모리 오버플로우 가능성이 존재한다는 점과 프로그램 가독성이 떨어진다는 단점이 있다 [참고] https://www.geeksforgeeks.org/iterative-quick-sort/ 재귀함수는 비재귀함수는 for, while 반복문으로 짤 수 있다. 퀵 소트를 구현하기 위해서는 quicksort 함수를 재귀함수로 이용했는데 stack 자료구조를 이용해 partition의 반환값을 비교해 아직 부분집합의 크기가 1보다 크다면 stack에 넣어 반복문을 수행시킬 수 있다 stack STL을 사용하는 것은 느리다. 배열로 대체하도록 한다

위와 같이 알려진 정렬 알고리즘은 무수히 많다. 이 정렬 알고리즘을 모두 알면 좋겠지만, 나눠진 이유와 이에 맞춰 사용해야할 정렬 알고리즘을 적절히 판단해야만 한다 1) 정렬이 수행되는 시간복잡도가 다르다. 시간복잡도가 매번 평균 시간복잡도로 나오진 않지만 대체적으로 빠른 것과 느린 것이 있다. 데이터 양이 작다면 시간복잡도를 크게 고려할 필요가 없기 때문에, 코드가 짧은 bubble sort, selection sort, insertion sort가 있다. 반대로 데이터 양이 크다면 시간복잡도를 고려해야하기 때문에 코드가 길지만 merge sort, quick sort를 구현해야만 한다 2) 속도가 아닌 공간복잡도를 고려해야할 수 있다. merge sort는 NlogN의 빠른 알고리즘이지만 분할 정렬된..

CS 면접에서 실제로 나왔던 면접 질문이다 "Sorting Algorithm에서 stable 하다는 것은 무엇을 의미하나요?" stable한 sort는 중복 키 순서 유지를 보장하고, unstable은 그 순서가 보장하지 못한다 수많은 정렬 알고리즘이 있는데, stable과 unstable 성질로 나눌 수 있다 stable sort - bubble, insertion, merge unstable sort - selection, quick, heap [참고] http://blog.naver.com/zephyehu/150013176075

삽입 정렬 알고리즘은 key 값 앞에는 정렬이 되어있다는 가정 하에서, 앞쪽을 뒤에서부터 순서대로 탐색하면서 넣어줘야 할 위치를 찾는다. 탐색하는 과정에서 순서를 바꿔줘야 한다면 지속적으로 swap을 해준다

선택 정렬이란 가장 작은 것을 선택해서 앞으로 보내는 정렬기법이다. 가장 작은 것을 선택하는 데에 N번과 리스트의 길이 N이 곱해져서 총 시간복잡도 O(N^2)을 갖게 된다

휴일이 시작하면서부터 바로 캠핑을 즐기는 것이 최적의 해를 구하는 답이 된다. 나머지 연산을 통해 마지막 남은 연휴에 대해서는 즐길 수 있는 날과 대소비교를 통해 결과값을 구하면 된다 문제: https://www.acmicpc.net/problem/4796 깃허브주소: https://github.com/surinoel/boj/blob/master/4796.cpp