'🗒️ 책 & 강의 정리' 카테고리의 글 목록 (3 Page)

10장 재귀를 사용한 재귀적 반복

2022.12.05

재귀는 함수가 자기 자신을 호출할 때를 뜻하는 용어다. 1. 루프 대신 재귀 루프를 사용할 수 있는 경우라면 거의 대부분 재귀도 쓸 수 있다. 재귀를 쓸 수 있다고 해서 무조건 재귀를 써야 한다는 것은 아니다. 재귀는 명쾌한 코드를 작성할 수 있는 하나의 도구다. 2. 기저 조건 기저 조건(base case): 함수가 반복되지 않는 경우 모든 재귀 함수에는 함수가 무한대로 호출되지 않게 하는 기저 조건이 적어도 하나 있어야 한다. 3. 재귀 코드 읽기 재귀 코드를 읽는 방법 기저 조건을 찾는다. 기저 조건에서 함수가 어떻게 동작하는지 살펴본다. “끝에서 두 번째” 조건을 찾는다. 곧 보이겠지만 이는 기저 조건 바로 전 조건이다. “끝에서 두 번째” 조건에서 함수가 어떻게 동작하는지 살펴본다. 방금 분석한..

🗒️ 책 & 강의 정리/🏗️ 누구나 자료구조와 알고리즘

9장 스택과 큐로 간결한 코드 생성

2022.11.18

9장에서는 스택과 큐를 알아본다. 스택과 큐는 임시 데이터를 처리할 수 있는 간결한 도구다. 운영 체제 아키텍처부터 출력, 데이터 순회에 이르기까지 스택과 큐를 임시 컨테이너로 활용하여 뛰어난 알고리즘을 만들 수 있다. 1. 스택 스택이 데이터를 저장하는 방법은 배열과 같다. 즉, 원소들의 리스트다. 스택에는 다음과 같은 제약이 있다. 데이터는 스택의 끝에만 삽입할 수 있다. 데이터는 스택의 끝에서만 삭제할 수 있다. 스택의 마지막 원소만 읽을 수 있다. 접시 더미를 쌓아올린 것처럼 생각해도 좋다. 스택의 끝(삽입, 삭제, 읽기 가능)을 top, 밑을 bottom이라고 한다. 스택에 새 값을 삽입하는 것을 스택에 푸시한다고도 말한다. 스택의 끝에서 원소를 제거하는 것을 pop이라고 한다. LIFO - L..

🗒️ 책 & 강의 정리/🏗️ 누구나 자료구조와 알고리즘

8장 해시 테이블로 매우 빠른 룩업

2022.11.18

✍🏻 누자알 앞부분은 기본 내용이고, 다시 공부할 필요가 없다고 생각했다. 그래서 정리에 조금 소홀함이 있었다. 그러나 최근 쳤던 코딩 테스트에서 CS 지식 중 선택 정렬과 버블 정렬에 대해 물어보는 문제가 나왔다. 와! 마침 누자알 4장과 5장이 버블 정렬과 선택 정렬에 대해 자세하게 설명하고 있어서 해당 문제를 맞출 수 있었다. 역시 공부는 기본이 중요하다는 것을 다시 깨달았다. 기록하지 않으면 까먹을 것 같아서 느슨해지지 말자는 다짐으로 여기 기록한다. 배열이 정렬되어 있지 않다면 컴퓨터는 선형 검색을 해야 하므로 특정 값이 배열 내에 존재하는지 검색하기 위해 O(N)의 수행 단계가 필요하다. 정렬된 배열이라면 컴퓨터가 이진 검색을 수행할 수 있으므로 O(log N)의 수행 단계가 필요하다. 그러나..

🗒️ 책 & 강의 정리/🏗️ 누구나 자료구조와 알고리즘

6장 긍정적인 시나리오 최적화

2022.11.04

어떤 문제 해결을 위해 여러 알고리즘 중 하나를 선택할 때는, 모든 시나리오를 고려하는 능력이 필요하다. 1. 삽입 정렬 버블 정렬과 선택 정렬의 시간 복잡도는 O(N^2)으로 같지만 실제 실행되는 단계 수는 선택 정렬이 두 배 적다. 즉, 두 배 빠르다. 6장에서는 삽입 정렬에 대해 배우면서 최악의 시나리오가 아닌 다른 시나리오를 분석하는 것에 어떤 장점이 있는지 알아본다. 삽입 정렬의 수행 순서 첫 번째 pass through에서 두 번째 셀의 값을 삭제하고 이 값을 임시 변수에 저장한다. 삭제한 공간은 공백으로 남는다. 공백 기준 왼쪽의 값과 차례대로 비교하여 올바른 위치에 임시 변수의 값을 삽입한다. 두 번째 pass through는 세 번째 셀의 값을 삭제하고, 위의 pass through를 반..

🗒️ 책 & 강의 정리/🏗️ 누구나 자료구조와 알고리즘

5장 빅 오를 사용하거나 사용하지 않는 코드 최적화

2022.11.03

빅 오는 알고리즘을 비교하고 주어진 상황에 알맞은 알고리즘을 결정하게 해 주는 좋은 도구이지만, 유일한 도구는 아니다. 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)..

10장 재귀를 사용한 재귀적 반복

9장 스택과 큐로 간결한 코드 생성

8장 해시 테이블로 매우 빠른 룩업

6장 긍정적인 시나리오 최적화

5장 빅 오를 사용하거나 사용하지 않는 코드 최적화

티스토리툴바