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

4장 빅 오로 코드 속도 올리기

2022.11.02

1. 버블 정렬 정렬 알고리즘: 정렬되지 않은 배열이 주어졌을 때, 어떻게 오름차순으로 정렬할 수 있을까? 2 1 3 5 위와 같은 배열이 있을 때, 포인터 1은 2를, 포인터 2는 1을 가리킨다. 포인터 1 > 포인터 2 일 때, 두 항목을 교환한다. 포인터들은 한 칸씩 이동하며 두 항목을 비교하고 필요시 두 항목을 교환한다. 이렇게 한 번 배열 전체를 pass through하고 나면, 다시 맨 왼쪽으로 포인터를 옮겨 교환이 일어나지 않을 때까지 반복한다. 2. 버블 정렬의 구현 생략 파이썬 코드 예쁘다 3. 버블 정렬의 효율성 버블 정렬 알고리즘에서 중요한 단계는 비교와 교환이다. 비교: 배열 크기가 N이라고 했을 때, 비교는 N - 1 + N - 2 + N - 3 + … + 1번 실행된다. 교환: ..

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

3장 빅 오 표기법

2022.10.29

알고리즘의 효율성을 결정하는 주 요인은 알고리즘 수행에 필요한 단계 수 배열에 N개의 원소가 있을 때 선형 검색에 N단계가 필요하다고 표현하면…? 빅 오 표기법 1. 빅 오: 원소가 N개일 때 몇 단계가 필요할까? O(N) “빅 오 엔”이라고 발음한다. 보통 “빅”을 생략하고 “오 엔”이라고 부름. 알고리즘에 N단계가 필요하다는 뜻 O(1) 1장에서 배열 읽기에 필요한 단계 수는 “배열의 크기와 상관없이” 딱 한 단계. 이때의 표기를 O(1)이라고 한다. 즉 배열에 원소가 몇 개든 한 단계만 필요할 때. O(1)의 시간 복잡도를 갖는 알고리즘을 가장 빠른 알고리즘 유형으로 분류한다. 상수 시간(constant time)을 갖는 알고리즘이라고도 표현한다. 2. 빅 오의 본질 빅 오가 진정으로 의미하는 것:..

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

2장 알고리즘이 중요한 까닭

2022.10.29

1. 정렬된 배열 orderred array: 값이 항상 순서대로 존재하는 배열 삽입할 때는 항상 삽입 전에 값의 올바른 위치를 찾고, 다른 값들을 옮겨 공간을 만들어야 한다. O(N) 삽입에 필요한 단계 수는 새 값이 정렬된 배열 어디에 놓이게 되든 비슷하다 앞 부분에 삽입할 경우, 비교가 줄어들고 이동이 늘어남 뒷 부분에 삽입할 경우, 비교가 늘어나고 이동이 줄어듬 2. 정렬된 배열의 검색 선형 검색: 앞에서부터 검색 이 경우 시간복잡도는 O(N)이다. 그러나 더 나은 방법이 있다… 3. 이진 검색(이진 탐색, Binary Search) 1에서 100 사이의 업다운 게임을 생각해 보자. 50, 25, 13… 찾는 값의 범위는 절반의 절반의 절반으로 줄어든다. 4. 이진 검색 대 선형 검색 작은 크기의..

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

1장 자료구조가 중요한 까닭

2022.10.29

1. 자료 구조 데이터: 모든 유형의 정보를 망라하는 용어 자료구조: 데이터를 조직하는 방법 2. 배열: 기초 자료 구조 배열: 데이터 원소들의 리스트 2.1 자료구조 연산 읽기: 특정 위치를 찾아보는 것 검색: 자료구조 내에서 특정 값을 찾는 것 삽입: 자료구조에 새로운 값을 추가하는 것 삭제: 자료구조에서 값을 제거하는 것 3. 속도 측정 연산이 얼마나 빠른가를 측정할 때는 시간 관점에서 측정하지 않고 얼마나 많은 단계가 필요한지를 논해야 한다. 연산의 속도 측정 → 시간 복잡도 측정 == 속도, 시간 복잡도, 효율성, 성능 4. 읽기 읽기: 배열 내 특정 인덱스에 어떤 값이 들어 있는지 찾아보는 것 컴퓨터의 특징 컴퓨터는 모든 메모리 주소에 한 번에 갈 수 있다. 컴퓨터는 배열을 할당할 때 어떤 메..

4장 빅 오로 코드 속도 올리기

3장 빅 오 표기법

2장 알고리즘이 중요한 까닭

1장 자료구조가 중요한 까닭

티스토리툴바