정글에서 온 개발자

나만의 언어로 암기해보기 버블 정렬: 이웃 교환의 연속 셰이커정렬 : 이웃교환을 위 아래 번갈아서 함 단순선택(선택 정렬) : 자리 정해서 한번에 새치기(원격 교환) 단순삽입(삽입 정렬) : 한명씩 새치기 이진 삽입정렬 셸 정렬: 징검다리 교환 퀵 정렬: 피벗을 기준 (원격)교환하며 분할 정복 병합 정렬: 반씩 쪼개서 분할 정복 힙 정렬: 힙으로 정렬해놓고 하나씩 꺼내며(다시 힙으로 만들면서) 정렬 도수 정렬: 누적도수 분포표를 인덱스로 사용하여 정렬 (비교 및 교환이 없음) 아래부터 각 정렬의 설명 버블(이웃 교환의 연속) - O(n^2) 맨 뒷쪽부터 상호 교환을 앞쪽 까지 함(한 패스) 패스를 n 번 반복함 (패스마다 교환이 n-1번씩 줄어듬) 개선 패스에서 교환이 안 일어나면 끝내기(break) 교..

책읽기: Introduction to Algorithms 40페이지까지 읽어보았다. 문제풀기: 18번문제까지 풀었다. 외판원 순회 2 에러 푸느라 애먹었다. 베이스 케이스를 잘못 잡아서 고생했다. 2023.10.17 - [정리] - 알고리즘과 자료구조의 정의 타당하지 않은 알고리즘도 유용할 수 있다는 것을 다시 한번 상기됐다. 알고리즘과 자료구조의 정의 알고리즘 어떤 값이나 집합을 입력으로 받아 또 다른 값이나 값의 집합을 출력하는 잘 정의된 계산 절차 잘 정의된 계산 문제를 풀기 위한 도구 계산 문제를 정의하려면 입력과 출력의 관계를 krafton-jungle-essay.tistory.com 2023.10.17 - [정리] - 알고리즘의 분석 어렴풋했던 내용을 정리하고 넘어갈 수 있었다. 알고리즘의 분..

루프 불변성 점진적인 방법에서 활용 가능하다. For 나 While 등 루프를 돌아도 변하지 않는 조건 알고리즘이 타당한 이유를 쉽게 이해할 수 있게 사용된다. 세가지 특징이 있다. 초기조건 : 첫번째 반복을 시작하기 전에 루프 불변성이 참이여아한다. 유지조건: 다음 반복이 시작되기 전까지도 계속 참이여야 한다. 종료조건: 루프가 종료될 때 그 불변성이 알고리즘의 타당성을 보이는데 도움이 될 유용한 특성을 가져야 한다. 귀납법과 비슷하다. 베이스가 참임을 보임 귀납적 과정을 증명함 +. 마지막으로 알고리즘의 타당성을 보이는 것이 중요 정렬 알고리즘을 풀기로 했으면 루프 불변성이 마지막에 정렬된 수열을 나타내야 하는 것. 분할 정복 재귀적 구조를 가진 알고리즘 중 하나 세단계 분할: 현재 문제를 같은 문제..