시간 배분
0800 - 0845: 오늘 계획 세우기
0900 - 1200: 키워드 공부
- 재귀알고리즘 정리 완료
- 큐 정리 완료
- 하노이탑 문제 정리 완료1200 ~ 1330: 랜덤런치
1330 - 1630: 키워드 공부
- 정렬 알고리즘 개론 정리 완료
- 버블정렬 정리 완료
- 선택정렬 정리 완료1645 - 1800: 운동
- 가슴운동(플라이, 벤치, 덤벨, 플라이(아래))
- 사레레, 싯업(상중하)1800 - 1900: 저녁 식사
1900 - 2100: 키워드 공부
- 삽입정렬, 이진삽입정렬
- 백준 1920 문제 풀이2100 - 2200: TIL, 내일 계획
2200 -2300: 코어타임
오늘 목표
- 큐
- 재귀 알고리즘
- 하노이 탑
- 8퀸 문제
- 정렬 알고리즘
- 버블 정렬
- 단순 선택 정렬
- 단순 삽입 정렬
- 셸 정렬
- 귁 정렬
- 병합 정렬
- 힙 정렬
- 도수 정렬
- 브루트포스법
- KMP법
- 보이어 무어법
- 연결리스트
책의 60% 까지는 봤다. 책을 발췌독을 하려다가 선결개념이 많이 부족해서 결국 앞부터 다시 정독을 했다. 자료구조도 체계가 존재했다. 배열을 이해해야 검색을 이해할 수 있고 검색을 이해해야 정렬이 필요한 이유를 이해할 수 있다. 큐와 스택도 재귀 알고리즘과 관련이 깊다. 아직 정렬 진도를 다 못 빼서 아쉽다. 일단 남은 시간은 문자열 검색과 연결리스트를 해결하는데 쓸 계획이다.
오늘 한 한 일
큐 정리 완료
재귀 알고리즘 완료
하노이탑 문제 풀었음
재귀알고리즘과 스택프레임의 구조를 이해하니까 재귀알고리즘의 작동원리가 이해하기가 쉬워졌다. 함수는 호출 될 때 메모리 상에 스택으로 쌓인다. 즉, 함수의 호출 관계와 함수의 실행완료관계는 반대다. 큰문제와 작은문제의 관계를 볼 때 스택을 사용하면 쉽다. 큰문제를 봤는데 해결하기가 어렵다면 작은문제로 쪼개서 재귀알고리즘을 호출한다. 그러다 기저조건에 도달하면 값을 하나씩 반환해서 최종적으로 큰 문제를 해결한다.
재귀 알고리즘의 작동방식을 이해해도 끝은 아니다. 이제부터 시작이다. 문제가 재귀알고리즘을 써야하는 문제인지 우선 파악해야하고 맞다면 어떻게 재귀 알고리즘으로 변형해야하는 지 평가해야한다.
하노이 문제나 피보나치 수열, 팩토리얼 함수만 지켜봤을 때, 적어도 큰 문제의 해답이 작은 문제의 해답에 의존한다면 재귀알고리즘을 적용할 수 있다.
재귀 알고리즘 상에 메모리 부족이 나타난다면 그냥 스택을 도입해서 문제를 풀어도 될 것 같긴한데 한번 해보자.
정렬 개념 정리 완료
버블 정렬 정리 완료
삽입정렬 정리 완료
삽입정렬은 특정 원소를 주목해서 앞에서 자리를 찾아가는 정렬이다. 주목받은 원소는 앞의 원소와 하나씩 비교하여 자기 자리를 찾는다. 배열의 크기가 커질수록 비교 · 교환 비용이 커진다. 따라서 스캔하는 시간을 줄이기 위해 이진검색을 도입하여 이진삽입정렬을 할 수 있다. 파이썬에서는 bisect 모듈을 통해 insort로 이진삽입정렬을 할 수 있다.
1920 수 찾기 문제 풀기 완료
정렬과 이진검색을 활용한 문제였다. 정렬의 경우 파이썬의 내장함수를 사용해서 레버리지를 했지만 이진검색은 직접 구현해야했다. 값을 찾는 경우 뿐만 아니라 값을 찾을 수 없는 상황도 고려해야했다. 값을 찾을 없는 상황을 구현하는 것이 까다로웠다. 값을 찾을 수 없다는 것은 이진검색을 모든 데이터에 대해 완료했다는 의미이다. 따라서 좌측 인덱스가 우측 인덱스보다 커지면 전 데이터에 대해 이진검색을 수행했다고 보고 이를 검색 종료 조건으로 삼았다.