[노개북] IT 5분 잡학사전 #07 - EP22~EP25

 

🏷️ 오늘 읽은 범위: Ep.22 ~ Ep.25

 

---

 

💡 책에서 기억하고 싶은 내용을 써보세요.

---

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

[🏷️132p-136p]

"회사 면접을 잘 보려면 이걸 알아야해!”

취업을 위해서는 자료구조와 알고리즘을 공부해야한다는 말을 많이 보았다.
책에서는 자료구조와 알고리즘을 코드를 효율적인 코드, 속도가 빠른 코드로 만들기 위해 필요하다고 설명한다.

알고리즘

• 컴퓨터에게 내리는 지시 사항을 나열한 것.
• 우리가 집을 나설 때 도착지까지 빠르게 가는 방법을 찾는것처럼 알고리즘 중에서도 효율성이 좋은 알고리즘을 사용하면 컴퓨터의 처리속도가 빨라진다.
• 실생활에서는 지도 앱에서 목적지까지 빨리 가는 기능을 구현하기 위한 패스파인더(pathfinder) 알고리즘,
  PNG, JPG 파일과 같이 이미지를 최대한 덜 손상하면서 용량을 효율적으로 줄일 수 있는 압축(compression) 알고리즘이 사용되고 있다.

자료구조

• 자료구조에서 자료는 데이터다.
• 인공지능, 기타 프로젝트에서 데이터를 다루게 되는데, 데이터를 보기 좋게 보관하는 것 외에도 찾기 좋게 제대로 보관해야 개발 효율성이 향상된다.
• 자료구조는 데이터를 어떻게 정리할 것인지를 결정한다. 아래의 표에 있는 자료구조말고도 다양한 방식이 있다.
• 이처럼 자료구조의 방식이 다양한 이유는 프로그램의 목적이 검색, 시간, 데이터 크기 등 다양하기 때문이다.

기준	설명
데이터 크기	데이터를 작은 것부터 큰 순서대로 정리한다.
인덱스	이름표를 붙여서 정리한다.
생성 시간	데이터가 들어오는 순서로 정리한다.

 

EP.23 배열

[🏷️137p-144p]

시간복잡도

• 프로그래밍의 작업 속도가 얼마나 빠른지 측정하는 방법
• 실제 시간을 재는 것이 아닌 작업이 얼마나 많은 단계를 거치는지 측정한다. 적은 단계가 필요한 코드일수록 작업 속도가 빠른 것.

메모리

• 컴퓨터의 기억 공간
• 휘발성과 비휘발성 메모리로 나뉘고 휘발성 메모리는 컴퓨터 전원을 껐을 때 저장한 값이 사라진다.

휘발성 메모리	비휘발성 메모리
램(RAM, random access memory)	하드 드라이브(C, D드라이브)

램

• 램에는 프로그램에 필요한 데이터(변수, 함수 등)가 저장된다.
• 램은 주소지가 적힌 박스가 많이 있는 창고이다. 박스에는 1개의 데이터를 저장할 수 있고, 박스마다 주소가 각각 있기 때문에 박스에 보관된 데이터를 빠르게 찾을 수 있다.

램과 함께 생각하는 배열

“길이가 4인 배열을 램에 할당해 줘!” ⇒ “박스 4개를 붙여서 창고에 자리 잡아줘!”

배열은 램에 배열의 크기만큼 이어진 형태로 공간을 차지한다.

1. 데이터 읽기

• 배열은 0부터 박스에 번호를 매긴다.
• 데이터를 읽을 때 N번째 데이터를 찾기 때문에 1단계 알고리즘을 가져서 처리 속도가 빠르다.

2. 데이터 검색

• 배열에서 N번째 데이터가 아닌 데이터의 값을 찾으려면 0번째 박스부터 모두 열어보고 데이터를 확인하기 때문에 검색의 속도는 읽기 속도보다 느리다.
• 이러한 배열의 데이터 찾는 방식을 선형 검색(linear search)이라 하고, 이외에도 다양한 방식이 존재한다.

3. 데이터 삽입

   데이터 삽입의 시나리오

   1) 배열에 데이터가 꽉 차 있지 않을 때, 마지막 위치에 데이터 추가

   2) 배열에 데이터가 꽉 차 있지 않을 때, 배열 중간에 데이터 추가 

   3) 배열에 데이터가 꽉 차 있을 때

 

   1) 마지막 위치에 데이터 추가

    컴퓨터는 배열의 길이를 기억하고 있어서, 시작점을 찾고 길이만큼 뒤로 가서 끝에 데이터를 추가한다.

   2) 배열 중간에 데이터 추가

   데이터가 들어갈 위치에 있던 데이터들의 위치를 옮겨준다.

   아래의 예시는 2개의 데이터만 옮겼지만, 배열의 길이가 만약 100이라면? .. 많은 작업이 필요할 것이다.

   3) 배열에 데이터가 꽉 차 있을 때

새 배열 만들기 → 복사하기 → 추가하기

   더 큰 배열을 새로 만들고, 이전 배열을 복사해서 옮긴 다음, 새 데이터를 추가해야한다.

   배열에 데이터를 추가하는 가장 느린 경우이다.

4. 데이터 삭제

배열에서 데이터의 삭제는 삽입하는 원리와 비슷하다.

마지막 데이터 삭제가 가장 쉽고, 배열은 맨 앞부터 차곡차곡 채워야하기 때문에 맨 앞에 있는 데이터 삭제가 가장 어렵다.

EP.24 시간 복잡도

[🏷️145p-149p]

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

 

에피소드 23에서 설명한 선형 검색 알고리즘은 배열의 크기가 커지면 검색 시간도 정비례로 커진다.

배열의 길이를 N이라고 했을 때, 검색 횟수는 최대 N이 되므로, 시간 복잡도는 O(N)으로 표현된다.

 

빅오 표기법을 사용하는 이유

• 설명을 간단하게 만든다.

선형 검색 알고리즘은 배열의 길이가 N일 때 총 N번 검하는 과정이 필요해 ⇒ 선형 검색 알고리즘의 시간 복잡도는 O(N)이다.

• 알고리즘 분석이 빨라진다.

Big-O 표기법을 보고 알고리즘을 선택할 수 있다.

 

상수 시간(constant time) - O(1)

시간 복잡도 O(1)로 표현되는, 배열의 길이와 상관없이 함수가 고정된 실행 횟수로 실행되는 것. 아래 사진의 두 코드는 O(1)의 시간 복잡도를 가지고 있다.

이차 시간(quadractic time) - O(N²)

중첩 반복문이 있을 때 발생한다.

배열의 길이가 10이라면 총 100번의 단계가 필요하다.

즉, 배열의 길이가 길어질수록 작업 속도는 제곱배로 느려지기 때문에 O(N²)으로 표현된다.

EP.25 검색 알고리즘

[🏷️150p-153p]

1. 선형 검색 알고리즘(linear search)
2. 이진 검색 알고리즘(binary search) 

선형 검색 알고리즘

• 리스트에서 찾고자 하는 값을 맨 앞에서부터 끝까지 차례대로 찾아 나간다.
• 리스트의 길이가 길어지는 만큼 검색 시간도 길어진다.

이진 검색 알고리즘

• 데이터의 정렬이 끝난 배열에만 사용할 수 있다.
• 리스트의 중앙 값 기준으로 해당 데이터와 찾으려는 데이터의 크고 작음을 비교하고, 찾으려는 데이터가 포함된 범위에서만 검색을 시도한다.
• 이진 검색의 속도가 빠른 이유는 단계마다 배열의 절반을 제외할 수 있기 때문이다.

 

🤔 오늘 읽은 소감은? 떠오르는 생각을 가볍게 적어보세요.

---

컴퓨터 공학 지식 챕터로 들어가면서 이해해야할 것들이 많아졌다.

알고리즘 문제를 풀면서 알고리즘이 정확히 무엇인지 이해하지 않고 공부했던 과거의 내가 민망했다. 단순히 취업을 위한 공부를 하고 있는건 아닌가 하는 생각이 들었다.

 

물론 개발은 재밌지만, 효율적인 개발을 하고싶다고 얘기하려면 그동안 눈감고 미뤄놨던 자료구조와 알고리즘에 관심가져야했다ㅠㅠ

우리는 스스로 자신의 삶을 만들어가고, 자신의 모습을 만들어가는 과정에서의 선택은 스스로 책임져야한다고 했다.

사용자에게 보다 나은 경험을, 효율적인 웹을 만드는 개발자가 되고 싶다면 눈을 가리지 말자!🚀

 

🔍 궁금한 내용이 있거나, 잘 이해되지 않는 내용이 있다면 적어보세요.

---

상수 시간
필요한 수학적 연산 시간이 주어진 입력 자료에 관계 없이 일정할 때의 연산 시간을 의미한다.
ex. 배열 또는 메모리에 있는 하나의 원소에 접근하기 위해서는 배열의 길이에 상관없이 단 하나의 연산이 수행된다.

선형 검색 알고리즘 vs 이진 검색 알고리즘

	선형 검색 알고리즘	이진 검색 알고리즘
시간 복잡도	O(N)	O(logN)
장점	- 검색 방법 중 가장 단순하여 구현이 쉽다. - 정렬되지 않은 리스트에도 사용 가능하다.	- 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되어 속도가 빠르다.
단점	검색할 리스트의 길이가 길어지는 만큼 검색 시간도 길어진다.	- 데이터가 정렬되어 있어야한다.

[WIKI] 선형 검색 알고리즘 / 이진 검색 알고리즘