[IT 5분 잡학사전]Ep.22~26 요약 및 TIL

Ep.22 자료구조와 알고리즘

자료구조와 알고리즘은 코드를 더 효율적이고 빠르게 만들기 위해 필요하다.

 

자료구조 ; Data Structure

: 데이터를 효율적으로 보관하고 찾기 위한 것.

: 프로그램의 목적에 따라 사용하는 자료구조가 다르므로 자료구조의 방식은 다양하다.

 

알고리즘

: 컴퓨터에 내리는 지시 사항을 나열한 것.

: Ex) 혜림이의 자기 전 알고리즘 1. 양치 2. 세수 3. 스킨케어 4. 전자기기 충전 5. 눕기

 

 

Ep.23 배열

램 ; Random Access Memory

: 휘발성 메모리. -> 프로그램에 필요한 데이터인 변수, 함수 등이 저장됨. -> 램이 있어야 프로그램 실행 가능.

: 배열을 이용해 램에 주소를 부여한다. -> 데이터에 접근하는 속도가 안정되고 빠름.

 

배열

: 배열은 자료구조.

: 배열의 index는 0부터 시작, index[0]부터 채워져 있어야 함.

: 컴퓨터는 배열의 시작 주소와 길이를 알고 있음. -> 읽는 속도 매우 빠름.

: 배열 내 데이터를 검색할 수 있음. 검색 속도 빠르지 않음.

: 배열에 데이터를 삽입하는 경우

1. 배열 맨 뒤에 데이터 삽입 (배열에 여유공간 있는 경우) : 배열의 시작 주소를 찾고 길이만큼 뒤로 가서 데이터 추가.
2. 배열 중간에 데이터 삽입 (배열에 여유공간 있는 경우) : 추가하려는 위치와 그 뒤에 있는 데이터들 모두 한칸씩 뒤로.
3. 배열에 데이터가 다 차있을 때 : 더 큰 배열을 새로 만든 뒤 이전 배열을 복사해 옮기고 새 데이터 추가.

: 배열에 데이터를 삭제하는 경우

1. 맨 뒤(마지막) 데이터 삭제
2. 맨 앞 or 중간 데이터 삭제 : 삭제 후 삭제한 데이터 뒤의 데이터들 한 칸씩 앞으로 이동.

: 배열은 맨 앞부터 채워져 있어야 하므로 삽입과 삭제 속도 느림.

 

 

Ep.24 알고리즘 속도 표현법

시간 복잡도

: 프로그램의 작업 속도가 얼마나 빠른지 측정하는 프로그램. "얼마나 빠른지"-> 시간(X) 단계(O)

: 시간이 아닌 작업이 거치는 단계를 측정. -> 단계가 적을수록 코드의 작업 속도가 빠르다고 판단.

: 알고리즘으로 작업을 완료할 때까지 걸리는 절차 수는 N이라 함.

: Big-O 표기법 사용.

 

Big-O 표기법

: 시간 복잡도를 표기하는 방법.

: N은 알고리즘으로 작업을 완료할 때까지 걸리는 절차 수.

def print_first(arr):
	print(arr[0]);
// O(1). print_first 함수를 한번 실행하기 때문.

def print_first(arr):
	print(arr[0])
	print(arr[0])
// O(1). print를 두번 수행한다고 O(2)가 아니다. 실행 단계에 영향을 주는 요소만 봐야함.
// 배열의 길이가 실행 단계에 상관 없이 늘 실행 횟수 같으므로 N=1.

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^2). 배열 길이가 길어질 수록 작업 속도는 제곱배로 느려진다.

 

Ep.25 검색 알고리즘

선형 검색 ; linear search

: 배열에서 찾고자 하는 값을 맨 앞에서부터 끝까지 찾아 나감.

: 배열의 길이가 길어지면 검색 시간도 길어짐. -> 비효율적

: 배열 길이에 따른 검색 시간은 y = x 그래프 형태.

 

이진 검색 ; binary search

: 크기가 큰 배열을 다룰 때 효과적.

: 데이터의 정렬이 끝난 배열에서 사용 가능. ex)1,2,3,4,5 또는 5,4,3,2,1 처럼 정렬된 상태의 배열에서만 사용 가능.

: 배열의 중앙에서 검색 시작. 배열의 중간값과 찾고자 하는 값을 비교하여 중간값보다 큰지 작은지 확인. 중간값보다 작다면 중간값 기준 좌측의 데이터들을 대상으로, 중간값보다 크다면 중간값 기준 우측의 데이터들을 대상으로 재탐색. 찾고자 하는 값을 찾을 때까지 이 과정 반복.

: 배열 길이에 따른 검색 시간은 y = log x 그래프 형태.

 

 

 

Ep.26 정렬 알고리즘

버블 정렬

: 인접한 두 데이터를 비교하여 앞의 데이터가 뒤의 데이터보다 크다면 (오름차순 기준) 자리를 바꿈.

: 아래 그림에서 각 행을 사이클이라 한다.

: O(N^2)

: 잘 사용하지 않음.

 

 

선택 정렬

: 전체 데이터 중에서 가장 작은 또는 큰 데이터의 위치를 따로 기억하는 방식으로 정렬.

: 배열에서 데이터가 들어갈 위치가 정해진 상태로 해당 위치에 들어갈 값을 찾는 것.

: O(N^2)

 

 

삽입 정렬

: 앞에서부터 차례대로 이미 정렬된 부분과 비교하여 알맞은 위치를 찾아 삽입하는 것.

: index = 1부터 시작. (앞부분이랑 비교해야 하므로)

: 선택정렬, 버블정렬보다 빠름. O(N^2).  시간 복잡도가 같아도, 처리 속도가 더 빠를 수 있다.

 

 

 

---

 

그래서 오늘 내가 배우고, 느낀건!

• 자료구조는 2020년에 배우고 복습한 적이 없어서 뭘 다루는 과목이였는지 조차 기억이 안났는데, "데이터를 효율적으로 보관하고 찾기 위한 것" 이라고 제대로 정의할 수 있게 되었다. 작년부터 혼자 웹개발에 대해서만 공부해온 터라, 자료구조와 알고리즘을 사용할 일이 없었고 프론트엔드 취업할 때 JS나 파이썬으로 자료구조/알고리즘 공부를 어떻게, 왜 해야하지? 라는 생각을 가지고 있었는데 코드를 효율적으로 짜기 위해 어떠한 개발을 하던 필수적으로 공부해야하는 것들이란걸 알게되었다.

 

• 배열은 자료구조. 배열은 램에서 데이터를 다룰 때 사용. (주소 부여해 데이터 접근 용이하게 함.)

 

• 시간복잡도 오랜만에 보니까 헷갈림. 일단 정처기 보고 .. 종설 여름방학까지 끝내고 .. 종설 막바지부터 코테 준비할 때 .. 알고리즘을 다시 잡을 때 쯔음 .... 다시 개념 또 잡아야지.

 

#노마드코더 #북클럽 #노개북