[IT 5분 잡학사전 - 컴퓨터 공학 편] DAY7, EP.22 ~ EP.25

✔오늘의 3줄 요약

• 개발자가 되고 싶다면 결국에는 자료구조와 알고리즘을 공부하고, 자신의 코드에 적용할 수 있어야 한다.
• Big-O 표기법의 기본 개념
• 배열과 알고리즘

 

 

✔오늘 읽은 범위

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

EP.23 배열이 뭐죠?

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

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

 

 

✔기억하고 싶은 내용

1. 자료구조와 알고리즘은 언제 필요할까?

돌아가는 수준으로 개발 - 코딩은 다 했고, 버그도 없는상태

코드를 정리 - 협업하기 편하도록 코드를 정리, 관리

효율적인 코드, 속도가 빠른 코드를 고민하게 될 때 자료구조와 알고리즘이 필요하다.

 

 

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

예) 출근 준비하기 알고리즘

1.일어나기 2.씻기 3.머리 말리기 4.옷 갈아입기 5.가방 챙기기 6.집 나가기

 

 

- 실생활에서 알고리즘을 사용되는 알고리즘

패스파인더(pathfinder) 알고리즘

목적지에 최대한 빨리 가는 방법을 알려주는 기능을 구현하기 위해 사용한다. 예) 지도 앱

 

압축(compression) 알고리즘

이미지를 최대한 덜 손상하면서 용량을 효율적으로 줄일 수 있는 알고리즘

PNG, JPG 파일 모두 이미지 압축 알고리즘으로 만든 파일들이다.

 

 

2. 자료구조를 공부해야 하는 이유

프런트엔드 개발자라면 백엔드에서 내려받은 JSON 데이터로 보기 좋게 화면에 띄우는 역할을 한다.

하지만 데이터가 마구잡이로 보관되어 있다면 개발 효율을 저하시킨다. 그래서 자료구조를 공부해야 한다.

어떤 자료구조를 사용하는지에 따라 프로그램 속도가 빨라지거나 느려질 수 있다. 짐을 정리하는 방식에도 여러가지 방법이 있는 것 처럼..

 

데이터를 작은 것부터 큰 순서로 정리하는 자료구조(데이터 크기 기준),

이름표를 붙여서 정리하는 자료구조(검색을 위한 인덱스 기준),

데이터가 들어오는 순서로 정리하는 자료구조(생성 시간 기준) 등 다양하다.

 

 

3. 시간 복잡도

시간 복잡도는 프로그램 작업 속도가 얼마나 빠른지 측정하는 방법

예) 배열에서 특정 값을 검색하는 시간, 특정 값을 특정 위치에 추가하는 시간 등

 

시간 복잡도는 작업이 얼마나 많은 단계를 거치는지를 측정한다.

예) 어떤 작업을 하는데 어떤 코드는 5단계, 어떤 코드는 20단계가 필요하다면 5단계만 필요한 코드의 작업 속도가 빠르다고 하는것.

 

 

4. 메모리

메모리는 컴퓨터의 기억 공간을 말한다.

 

메모리의 종류

1. 비휘발성 메모리 (하드 드라이브 - SSD,HDD 등) - 껏다 켜도 남아있음

 

2. 휘발성 메모리 (RAM - random access memory) - 대표적인 휘발성 메모리, 컴퓨터를 끄면 램에 있는 데이터는 전부 휙 사라진다. 램에는 프로그램에 필요한 데이터가 저장된다.

 

프로그램의 변수, 함수 이런 것들이 램에 저장된다. 램이 있어서 프로그램을 실행할 수 있다. 램은은 데이터가 저장된 위치와 상관없이 일정한 접근 속도를 보장한다. 램은 데이터에 접근하는 속도가 매우 안정되고 빠르다.

 

램이 속도가 빠른 이유

램은 숫자가 적힌 박스가 많이 있는 창고라고 비유하자면, 박스에는 데이터를 1개씩 저장할 수 있고, 박스마다 주소가 있다 그러면 박스에 보관된 데이터를 빠르게 찾을 수 있다.

램에게 4번 박스에 있는 데이터를 봐 라고 지시해서 해당 박스에 들어있는 데이터를 보게 하는것 만약 주소가 없다면 입구 쪽 부터 모두 봐야한다.

 

5. 배열의 원리

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

 

6. 알고리즘의 속도 표현

알고리즘으로 작업을 완료할 때까지 걸리는 절차 수 N을 이용해서 O(N), O(log N)과 같이 표현하는데 이것을

빅 오(Big-O0 표기법이라고 한다.

 

알고리즘의 속도 를 표현하는 방법은 Big-O

 

선형 검색 알고리즘은 배열을 앞에서부터 하나씩 검색, 그래서 배열 크기가 커지면 검색 시간도 정비례로 커진다.

배열의 길이를 N 이라고 하면 검색 횟수는 최대 N이 된다.

시간 복잡도는 O(N)과 같이 표현한다.

"선형 검색 알고리즘은 배열의 길이가N일 때 총 N번 검색하는 과정이 필요하다" 라고 말하는 것보다 "선형 검색 알고리즘의 시간 복잡도는 O(N)이다" 라고 말하는게 더 간단.

 

알고리즘을 선택하기 전에 Big-O 표기법을 보고 어떤 알고리즘을 사용할지 파악할 수 있다.

ex1)

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

배열의 길이와 상관없이 함수는 딱 한 번 실행하고 끝난다. 데이터가 출력하는 함수이기에..

이 함수의 시간 복잡도는 O(1) 이다. 이것을 '상수 시간(constant time) 내에 실행된다' 라고 하기도 한다.

상수 시간이란 이미 실행 횟수가 고정으로 정해진 것을 말한다.

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

이경우에도 시간 복잡도는 O(1)

왜냐하면 Big-O는 실행 단계에 영향을 주는 요소만 보기 때문이다.

Big-O로서 저 함수는 배열 길이와 상관없이 늘 실행 횟수가 같으니까, 같다는 의미로 1을 사용한다.

 

ex2)

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

이번에는 arr의 모든 데이터를 출력한다. 배열의 길이에 따라 실행 시간이 달라진다.

배열 길이가 10이면 10번, 100이면 100번을 출력한다. 그래서 이럴 때 시간 복잡도는 O(N)이다.

 

또 다른 시간 복잡도 이차 시간(quadratic time)

이차 시간은 중첩 반복문이 있을 때 발생한다.

ex1)

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

배열의 길이가 길어질수록 작업 속도는 제곱배로 느려진다. 그리고 이걸  Big-O로 나타내면 O(N²), 제곱배(N * N)을 그대로 표현

 

7. 검색 알고리즘

• 선형 검색(linear search)
• 이진 검색(binary search)

둘다 검색 관련 작업을 수행한다.

 

- 선행 검색 알고리즘

자연스러운 검색 방법, 숫자가 10개 있는 배열에서 7이라는 숫자를 찾는다면 처음부터 차례대로 찾는다.

찾는 데이터가 가장 마지막에 있다면, 배열의 길이가 길다면 검색 시간도 길어진다.

 

- 이진 검색 알고리즘

배열의 크기가 클 때 선형 검색보다 훨씬 좋은 알고리즘이다.

이진 검색 알고리즘은 데이터 정렬이 끝난 배열에서만 사용할 수 있다.

 

이런 특정 알고리즘은 특정 자료구조에서만 사용할 수 있다.

정렬이 끝난 배열이란 데이터가 순서대로 정렬된 상태를 말한다.

 

만약 1부터 10까지의 숫자가 있고, 9를 찾는다고 가정할 때

배열의 중앙인 5를 기준으로 찾는다.

 

[시도 1] 중앙값 5, 왼쪽은 모두 후보에서 제외

[시도 2] 중앙값 7, 왼쪽은 모두 후보에서 제외

[시도 3] 중앙값 8, 왼쪽은 모두 후보에서 제외

 

이렇게 3번 만에 9를 찾을 수 있다.

선생 검색으로 찾는다면 9번을 시도했을 것.. 배열의 크기가 클 수록 탐색 속도의 차이는 더 크다.

데이터가 아무리 많아진다고 해도 검색 시간은 데이터에 비해 그렇게 많이 필요하지 않다.

 

이진 검색 정리

• 이진 검색 알고리즘은 거대한 배열을 다룰 때 효과적인다.
• 이진 검색 알고리즘을 사용하고 싶다면 배열은 항상 정렬되어 있어야 한다.

 

 

✔소감 및 떠오르는 생각

시간복잡도는 시간을 갖고 더 공부해야겠다.

Big-O 표기법은 꼭 알아야 할 중요한 개념, 기본과 내용을 공부하자.

 

✔과제 2. 최애 북틸

https://velog.io/@2m0815/%EB%85%B8%EA%B0%9C%EB%B6%81-Challenge-Day-06-TIL

[노개북] Challenge Day 06 TIL

개념에 대해 상세히 정리해놓은게 참고하기 좋다.

 

https://nomadcoders.co/community/thread/9374

[TIL] IT 5분 잡학사전 EP.16-21 – 노마드 코더 Nomad Coders

간단히 정리한점이 참고하기 좋다.

 

https://south-dev.tistory.com/26

[IT 5분 잡학사전 - 웹 기술 편] DAY5, EP.16 ~ EP.21

내꺼 좋다.