[IT 5분 잡학사전] Assignment #07

 

IT 5분 잡학사전 | 니꼴라스 - 교보문고

 

• 자료구조와 알고리즘은 필수라고?
• 배열이 뭐죠?
• 알고리즘의 속도는 어떻게 표현할까?
• 검색 알고리즘이 뭐죠?

 

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

 

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

 

알고리즘

패스파인더 알고리즘과 압축 알고리즘과 같이 원하는 결과를 빨리 얻어낼 수 있는 방법을 나열한 것이다. 어떤 알고리즘을 사용하느냐에 따라 성능개선에 도움이 된다.

 

자료구조

데이터를 보기 좋게 보관해서 찾기 좋게 하는 방식으로 프로그램 속도에 영향을 미친다. 데이터 크기, 검색인덱스 기준, 생성시간 기준 등 다양한 방식으로 자료구조를 정할 수 있다.

---

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

 

시간복잡도

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

 

메모리

컴퓨터의 기억 공간, 휘발성과 비휘발성으로 나뉜다

하드 드라이브는 비휘발성 메모리이고, 휘발성 메모리는 RAM이다. RAM에는 프로그램에 필요한 데이터가 저장된다.(프로그램 변수, 함수 등)

RAM은 주소를 가지고 데이터를 찾기 때문에 속도가 안정되고 빠르다.

 

배열

배열은 램에 줄줄이 이어진 형태로 공간을 차지하고 있다.

컴퓨터는 배열의 시작 주소와 길이를 알고 있다. 그래서 배열은 읽는 속도가 아주 빠르다.

배열 맨 앞부터 차곡차곡 채워져 있어야 한다. 그래서 배열은 삽입과 삭제가 느리다.

---

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

 

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

배열을 길이가 N이고 선형검색으로 배열 내 모든 데이터를 검색하려면 검색횟수가 N이 된다. 즉, 시간복잡도는 O(N)으로 표기된다.

시간복잡도가 O(1)인 경우, 상수 시간 내에 실행된다고 한다.

 

배열에서 하나의 수를 출력하는 경우 - O(1)

배열의 모든 경우의 수를 출력하는 경우 - O(N)

배열을 중첩해서 돌리는 경우 - O(N2)

---

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

 

선형검색 y=x

원하는 값이 나올 때까지 차례로 검색하는 방법

 

이진검색 y=log x

배열의 크기가 큰 경우, 선형검색보다 효과적이다. 먼저, 배열을 정렬한 상태에서 배열의 중앙에서 검색을 시작한다.

단계마다 배열의 절반을 제외해서 검색하기 때문에 속도가 빠르다.

이진검색 알고리즘은 거대한 배열을 다룰 때 효과적이다.

이진검색 알고리즘을 사용하고 싶다면 배열은 항상 정렬되어 있어야 한다.