TIL - DAY 5
📝 책에서 기억하고 싶은 내용을 써보세요.
22. 자료구조와 알고리즘은 필수라고?
코드를 효율적으로 만들기 위해!
개발자 작업 과정
프로그램이 돌아가는 수준으로 개발 → 버그 픽스 → 코드 정리: 관리 & 협업이 편하도록 효율적인 코드, 속도가 빠른 코드를 고민 이때 자료구조와 알고리즘이 필요
알고리즘이란? 컴퓨터에게 내리는 지시 사항을 나열한 것
다양한 컴퓨터 알고리즘, 실생활 예
지도앱 - 목적지까지 최대한 빨리 가는 방법 → 패스파인더(pathfinder) 알고리즘
이미지 파일 - 이미지를 최대한 덜 손상하면서도 용량을 효율적으로 줄일 수 있는 알고리즘 → 압출(compression) 알고리즘
데이터를 효율적으로 보관하고 찾기 위한 자료구조
무료 서비스들은 그 대가로 데이터를 수집한다.
개발자라면 반드시 다루는 데이터, 그냥 보관할 수는 없어!
개발 효율성을 위해 공부해야함
자료구조 방식
- 데이터를 작은 것부터 큰 순서로 정리하는 자료구조(데이터 크기 기준)
- 이름표를 붙여서 정리하는 자료구조(검색을 위한 인덱스 기준)
- 데이터가 들어오는 순서로 정리하는 자료구조(생성 시간 기준)
프로그램의 목적이 다양하기 때문에 자료구조의 방식이 다양하다.
23. 배열이 뭐죠?
읽기(read), 검색(search), 추가(add), 삭제(delete) 과정에서의 시간 복잡도(time complexity)
시간 복잡도는 작업 속도!
시간 복잡도는 프로그램의 작업 속도가 얼마나 빠른지 측정하는 방법(예. 배열에서 특정 값을 검색하는 시간, 특정 값을 특정 위치에 추가하는 시간)
메모리: 컴퓨터의 기억 공간
- 휘발성 메모리: 램(RAM, random access memory)
- 비 휘발성 메모리: 컴퓨터의 하드 드라이브 (C, D 드라이브)
램과 함께 생각하는 배열
- 배열을 읽는 방법과 속도: 배열은 0부터 숫자 매김, 읽는 속도는 1단계 알고리즘으로 매우 빠름(작업 속도는 단계를 적게 거칠수록 빠름)
- 배열을 검색하는 원리와 속도: 배열의 검색과정은 들어 있는 데이터를 확인 하기 때문에 읽기보다 시간이 많이 필요(선형 검색, linear search로 한정 했을 경우)
- 배열에 데이터를 삽입하는 원리와 속도
- 마지막 위치에 추가: 배열의 시작점을 찾고 길이만큼 뒤로 가서 끝에 추가하면 됨
- 배열 중간에 추가: 중간에 넣기 위에 기존 데이터 먼저 옮기기, 맨 앞에 넣을 경우 제일 많이 옮겨야 함
- 배열에 데이터가 꽉 차 있을 때: 더 큰 배열을 새로 만들고, 이전 배열을 복사해서 옮긴 다음, 새 데이터를 추가 해야 함
- 배열에서 데이터를 삭제하는 원리와 속도: 삽입 하는 원리와 비슷, 맨 앞부터 차곡차곡 채워야 하기 때문, 중간 데이터를 삭제하면 뒤쪽 데이터를 끌어당겨야 함
배열의 원리
- 배열은 램에 줄줄이 이어진 형태로 공간을 차지하고 있다.
- 컴퓨터는 배열의 시작 주소와 길이를 알고 있다. 그래서 배열은 읽는 속도가 아주 빠르다.
- 배열은 맨 앞부터 차곡차곡 채워져 있어야 한다. 그래서 배열은 삽입과 삭제가 느리다.
24. 알고리즘의 속도는 어떻게 표현할까?
시간복잡도: 알고리즘으로 작업을 완료할 때까지 걸리는 절차 수 N을 이용해서 O(N), O(log N)과 같이 표현하는데, 이것을 빅 오(Big-O) 표기법이라고 하다.
알고리즘의 속도를 표현하는 방법은? Big-O!
선형 검색 알고리즘은 배열을 앞에서부터 하나씩 검색하고, 그래서 배열의 크기가 커지면 검색 시간도 정비례로 커진다. 배열의 길이를 N이라고 하면 검색 횟수는 최대 N이 된다. 이때 시간 복잡도는 O(N)과 같이 표현한다.
“배열의 길이가 N일 때 총 N번 검색하는 과정이 필요하다”라고 말하는 것보다 “선형 검색 알고리즘의 시간 복잡도는 O(N)이다”라고 말하는 게 더 간단하기 때문
시간 복잡도를 표현하는 Big-O 표기법
단지 설명을 간단하게 만들어 줄 뿐 아니라 알고리즘 분석을 빠르게 할 수 있게 해준다.
O(1): 배열의 길이와 상관없이 딱 한 번 실행하고 끝날 때 “상수 시간(constant time, 이미 실행 횟수가 고정으로 정해진 것을 말함 ) 내에 실행된다”라고 이야기 할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
// 배열 arr의 첫 번째 데이터를 출력하는 코드 O(1)
def prit_first(arr):
print(arr[0])
// 배열 arr의 첫 번째 데이터를 2번 출력하는 코드 O(2)로 쓰면 될 것 같지만 O(1)이다
def prit_first(arr):
print(arr[0])
print(arr[0])
/* 배열 길이가 길어져도 검색 시간은 항상 같으니까 O(1), Big-O는 실행 단계에 영향을 주는 요소만 보기 때문에
배열의 길이와 상관없이 늘 실행 횟수가 같으니까, 같ㅇ다는 의미로 1을 사용함) */
O(N): 배열의 길이에 따라 실행 시간이 달라짐, 배열의 길이가 길어지면 시간은 그만큼 늘어난다
1
2
3
4
// 배열 arr의 모든 데이터를 출력하는 코드
def print_all(arr):
for n in arr:
print(n)
O(n^2): 이차 시간(quadratic time)은 중첩 반복문이 있을 때 발생, 배열의 길이가 길어지면 시간은 제곱배로 느려진다
1
2
3
4
5
// 배열 arr의 모든 데이터를 중첩 반복문으로 출력하는 코드
def print_twice(arr):
for n in arr:
for x in arr:
print(x, n)
25. 검색 알고리즘이 뭐죠?
- 선형 검색(linear search) 알고리즘
- 맨 처음 배열부터 검색 시작, 배열 길이가 길어지는 만큼 검색 시간도 길어진다.
- y = x
- 이진 검색(binary search) 알고리즘
- 데이터 정렬이 끝난 배열에서만 사용가능, 배열의 크기가 클 때 사용
- 중앙값을 기준으로 왼쪽, 오른쪽 점프 점프!!
- y = log x
🔥 오늘 TIL 3줄 요약
- 알고리즘과 자료구조: 알고리즘은 컴퓨터에게 내리는 지시 사항을 나열한 것, 데이터를 효율적으로 보관하고 찾기 위한 자료구조
- 시간 복잡도는 작업 속도! Big-O 표기법
- 맨 처음 배열부터 검색 시작은 선형 검색(linear search) 알고리즘, 데이터 정렬이 끝난 배열에서만 사용가능한 이진 검색(binary search) 알고리즘은 중앙값을 기준으로 왼쪽, 오른쪽으로 이동하며 점프!
🤩 오늘 읽은 소감은? 떠오른 생각을 가볍게 적어보세요
자료구조와 알고리즘 공부했지만 다시 공부해야하
🔖 궁금한 내용이 있거나, 잘 이해되지 않는 내용이 있다면 적어보세요.
시간 복잡도 Big-O 표기법 다시 정리해 봐야겠다!!
Comments powered by Disqus.