9장에서는 스택과 큐를 알아본다. 스택과 큐는 임시 데이터를 처리할 수 있는 간결한 도구다. 운영 체제 아키텍처부터 출력, 데이터 순회에 이르기까지 스택과 큐를 임시 컨테이너로 활용하여 뛰어난 알고리즘을 만들 수 있다. 1. 스택 스택이 데이터를 저장하는 방법은 배열과 같다. 즉, 원소들의 리스트다. 스택에는 다음과 같은 제약이 있다. 데이터는 스택의 끝에만 삽입할 수 있다. 데이터는 스택의 끝에서만 삭제할 수 있다. 스택의 마지막 원소만 읽을 수 있다. 접시 더미를 쌓아올린 것처럼 생각해도 좋다. 스택의 끝(삽입, 삭제, 읽기 가능)을 top, 밑을 bottom이라고 한다. 스택에 새 값을 삽입하는 것을 스택에 푸시한다고도 말한다. 스택의 끝에서 원소를 제거하는 것을 pop이라고 한다. LIFO - L..
✍🏻 누자알 앞부분은 기본 내용이고, 다시 공부할 필요가 없다고 생각했다. 그래서 정리에 조금 소홀함이 있었다. 그러나 최근 쳤던 코딩 테스트에서 CS 지식 중 선택 정렬과 버블 정렬에 대해 물어보는 문제가 나왔다. 와! 마침 누자알 4장과 5장이 버블 정렬과 선택 정렬에 대해 자세하게 설명하고 있어서 해당 문제를 맞출 수 있었다. 역시 공부는 기본이 중요하다는 것을 다시 깨달았다. 기록하지 않으면 까먹을 것 같아서 느슨해지지 말자는 다짐으로 여기 기록한다. 배열이 정렬되어 있지 않다면 컴퓨터는 선형 검색을 해야 하므로 특정 값이 배열 내에 존재하는지 검색하기 위해 O(N)의 수행 단계가 필요하다. 정렬된 배열이라면 컴퓨터가 이진 검색을 수행할 수 있으므로 O(log N)의 수행 단계가 필요하다. 그러나..
나는 데스크탑으로 게임과 타이핑을 같이 하고, 맥북으로는 코딩을 하고 있다. 다른 모니터와 키보드를 사용하는 것으로 의식적으로 코딩할 때 코드 자체에 좀 더 몰입할 수 있는 환경을 만드려는 의도인데... 문제는 데스크탑을 게임과 타이핑(노션, 공부 내용 정리) 용도로 쓰다 보니 전원을 켜면 습관처럼 게임과 디스코드, 카톡을 켜고 놀기 모드로 들어간다는 것이다. 다행히 맥북은 백준을 켜는 습관이 들어서 좀 덜하다. 카톡을 켜기는 하지만... 게임하고 싶은 충동을 계속 의식적으로 누르고 노션을 켜는 습관이 덜 들어서 윈도우의 시작 프로그램을 활용해 보았다. 전원을 켜면 채용 공고, IT 블로그, 면접 대비 CS 지식 정리 사이트가 브라우저로 뜨고, 노션이 켜지면서 오늘의 TDL 달력이 보이게끔 하고 싶었다...
어떤 문제 해결을 위해 여러 알고리즘 중 하나를 선택할 때는, 모든 시나리오를 고려하는 능력이 필요하다. 1. 삽입 정렬 버블 정렬과 선택 정렬의 시간 복잡도는 O(N^2)으로 같지만 실제 실행되는 단계 수는 선택 정렬이 두 배 적다. 즉, 두 배 빠르다. 6장에서는 삽입 정렬에 대해 배우면서 최악의 시나리오가 아닌 다른 시나리오를 분석하는 것에 어떤 장점이 있는지 알아본다. 삽입 정렬의 수행 순서 첫 번째 pass through에서 두 번째 셀의 값을 삭제하고 이 값을 임시 변수에 저장한다. 삭제한 공간은 공백으로 남는다. 공백 기준 왼쪽의 값과 차례대로 비교하여 올바른 위치에 임시 변수의 값을 삽입한다. 두 번째 pass through는 세 번째 셀의 값을 삭제하고, 위의 pass through를 반..
빅 오는 알고리즘을 비교하고 주어진 상황에 알맞은 알고리즘을 결정하게 해 주는 좋은 도구이지만, 유일한 도구는 아니다. 1. 선택 정렬 선택 정렬의 시퀀스 배열의 각 셀을 왼쪽에서 오른쪽으로 확인하면서 어떤 값이 최솟값인지 판단하고 가장 작은 값을 기록한다. 최솟값과 pass through를 시작했을 때의 값을 교환한다. pass through를 반복한다. 2. 선택 정렬 실제로 해보기 & 3. 선택 정렬 구현 (Kotlin) fun main() { selectionSort(arrayOf(10, 9, 4, 6, 7, 8, 3, 2, 11, 1)).forEach { print("$it ") } } fun selectionSort(arr: Array): Array { for (i in arr.indices)..
