IT 5분 잡학사전 #5

생각 정리 

복잡하고 어려워서 시작하기 어려웠던 알고리즘을 예시를 통해 가볍고 재미있게 배웠다. 오히려 더 자세히 알고 싶다는 호기심까지 생겼다. 같이 알려준 유튜브까지 보니 더 이해가 잘 되었다

읽은 범위 

Ep.22 : 자료구조와 알고리즘은 필수라고?

Ep.23 : 배열이 뭐죠?

Ep.24 : 알고리즘의 속도는 어떻게 표현할까?

Ep.25 : 검색 알고리즘이 뭐죠?

에피소드 22 : 자료구조와 알고리즘이 필수라고?

 

알고리즘은 컴퓨터에게 내리는 지시 사항을 나열한 것

등교를 준비하는 과정을 알고리즘으로 표현할 수 있어 

1. 이부자리에서 일어나기
2. 가방 챙기기
3. 머리 정돈하기
4. 교복으로 갈아입기
5. 세수, 양치하기
6. 집 나서기 

이 순서와 다른 등교 준비하기 알고리즘도 존재할 수 있어 

효율성이 더 좋아서 더 빠른 등교 준비가 가능해서 더 빨리 학교에 도착할 수도 있지

이건 컴퓨터도 마찬가지야

 

데이터를 효율적으로 보관하고 찾기 위한 자료구조
데이터 크기 기준	데이터를 작은 것부터 큰 순서로 정리하는 자료구조
검색을 위한 인덱스 기준	이름표를 붙여서 정리하는 자료구조
생성 시간 기준	데이터가 들어오는 순서를 정리하는 자료구조

프로그램의 목적이 다양할수록, 자료 구조의 방식도 다양해

에피소드 23 : 배열이 뭐죠?

배열의 원리

• 배열의 원리배열은 램에 줄줄이 이어진 형태로 공간을 차지하고 있다
• 컴퓨터는 배열의 시작 주소와 길이를 알고 있다. 그래서 배열은 읽는 속도가 아주 빠르다
• 배열은 맨 앞으로 차곡차곡 채워져 있어야 한다. 그래서 배열은 삽입과 삭제가 느리다

배열의 특징

• 배열을 읽는 방법과 속도
  • 배열을 0부터 숫자를 매긴다
  • 배열에서 데이터를 찾는 속도가 빠르다 
• 배열을 검색하는 원리와 속도
  • 배열에서 검색과정은 박스를 모두 뒤지는 방법으로 진행
  • 박스를 모두 열어 보고 들어 있는 데이터를 확인
  • 검색은 읽기보다 시간이 많이 필요
  • 데이터를 찾는 방식을 선형 검색 (linear search)으로 한정
• 배열에 데이터를 삽입하는 원리와 속도
  • 배열의 길이 5 , 현재 아이템의 수 4
    • 배열에 데이터를 삽입, 맨 마지막에 아이템을 추가 : 컴퓨터는 배열이 어디서 시작하는지, 배열의 길이는 얼마인지 기억하고 있어서 배열의 시작점을 찾고 길이만큼 뒤로 가서(끝에) 새 아이템을 추가한다
    • 배열 중간에 아이템을 추가 : 해당 위치와 그 뒤의 아이템을 뒤로 옮긴 후 새 아이템을 추가한다
    • 배열에 데이터가 모두 차 있을 때 : 새 배열 만들기 > 복사하기 > 추가하기
• 배열에서 데이터를 삭제하는 원리와 속도
  • 삽입하는 원리와 비슷
  • 배열은 맨 앞으로 차곡차곡 채워야 함 > 중간 데이터를 삭제하면 뒤쪽 데이터를 앞으로 다 끌어당김

시간 복잡도
프로그램의 작업 속도가 얼마나 빠르지 측정하는 방법, 실제 시간을 재는 것이 아닌 작업을 얼마나 많은 단계를 거치는지 측정 

 

메모리	컴퓨터의 기억 공간
비휘발성 메모리	컴퓨터의 하드 드라이브, 컴퓨터를 껐다가 다시 켜도 데이터 존재
휘발성 메모리	대표적으로 "램" (RAM: random access memory), 컴퓨터를 끄면 램에 있는 데이터는 사라짐, 프로그램에 필요한 데이터가 저장됨

에피소드 24 : 알고리즘의 속도는 어떻게 표현할까?

빅오(Big-O) 표기법: 시간 복잡도를 이야기할 때는 알고리즘으로 작업을 완료할 때까지 걸리는 절차 수 N을 이용해서 O(N), O(log N)과 같이 표현

def print_first(arr):
	print(arr[0])

이 함수는 배열의 길이와 상관없이 딱 한번 실행하고 끝날 거야

첫 번째 데이터만 출력하는 함수니까

이 함수의 시간 복잡도는 O(1) 이야 

이를 상수 시간(constant time) 내에 실행된다라고 해

 

def print_all(arr):
	for n in arr:
    	print(n)

이 함수는 배열의 따라 실행 시간이 달라져 

이럴 때 시간 복잡도는 O(N) 이야 

보통 선형 검색 알고리즘이 해당할 수 있어

def print_twice(arr):
	for n in arr
    	for x in arr
        	print(x, n)

이 함수는 배열길이가 길어질수록 제곱배로 느려져 

이럴 때는 O(N²) 이야

에피소드 25 : 검색 알고리즘이 뭐죠?

선형 검색 알고리즘	가장 자연스러운 검색 방법, 배열의 길이가 길어지면 검색 시간도 길어짐
이진 검색 알고리즘	배열의 크기가 클 때 선형 검색보다 훨씬 좋은 알고리즘 데이터의 정렬이 끝난 배열에서만 사용할 수 있다
정렬이 끝난 배열	데이터가 순서대로 정렬된 상태

https://www.youtube.com/playlist?list=PL7jH19IHhOLMdHvl3KBfFI70r9P0lkJwL

알고리즘.데이터구조 with Nico