오늘 읽은 범위
IT 5분 잡학사전
에피소드 22 ~ 에피소드 25
책에서 기억하고 싶은 내용을 써보세요.
ep.22
- 자료구조는 자료(데이터)를 효율적으로 보관하고 관리하기 위해서 사용한다.
- 알고리즘은 지시사항의 나열이다.
ep.23
- 배열에서 수행할 수 있는 지시사항은 읽기(read), 검색(search), 추가(add), 삭제(delete)가 있다.
- 배열은 램에 공간을 미리 할당하고 데이터를 그 안에 순서대로 저장하는 자료구조이다.
- 배열은 데이터를 순서대로 저장하므로 특정 번째의 데이터를 읽는데(read)는 상수 시간이 걸린다.
- 특정한 값을 찾기위해 검색(search)하는 경우 배열을 모두 돌아봐야 하므로 선형 검색 알고리즘을 사용할 경우 O(n)의 시간이 걸린다.
- 배열에 데이터를 삽입하는 경우, 배열에 여유 할당 공간이 있으면서 마지막 위치에 추가할 때는 상수 시간이 걸리지만 중간에 삽입하는 경우 그 뒤의 데이터를 하나씩 뒤로 옮겨야 하고, 맨 앞에 추가할 때는 전부 하나씩 뒤로 옮겨야 한다. 배열에 여유 할당 공간이 없는 경우 더 큰 공간의 배열을 새로 할당하여 값을 복사하고 추가하여야 한다. 이 경우가 가장 느리다.
- 배열에서 데이터를 삭제하는 경우, 마지막 데이터의 경우는 바로 접근해 삭제할 수 있지만, 중간이나 첫번째 데이터를 삭제하는 경우 해당 데이터를 삭제 후 뒤에 있는 데이터를 앞으로 당겨와야 한다. 배열 자료구조가 맨 앞부터 차곡차곡 채워져 있어야 하기 때문이다.
ep.24
- 알고리즘의 속도는 시간복잡도를 표현하는 Big-O 표기법으로 구분한다.
- 알고리즘의 속도를 비교할 때 중요한 것은, input의 크기(배열의 경우 배열의 길이)가 증가하면서 명령 수행 횟수가 얼마나 증가하는지를 보는 것이다. (크기와 상관없이 일정한 부분은 중요하지 않다.)
ep.25
- 검색 알고리즘 중 대표적으로 선형 검색(linear search)과 이진 검색(binary search)가 있다.
- 이진 검색은 선형 검색보다 빠르지만 데이터가 정렬되어 있다는 조건을 만족해야만 사용할 수 있다.
오늘 읽은 소감은? 떠오르는 생각을 가볍게 적어보세요
학부 2학년 때 자료구조, 알고리즘 수업을 들었는데 갑자기 그 좋은 때 생각이 났다. 컴퓨터과학의 이론적인 부분에 흥미가 있어서 어려웠지만 재밌게 수업을 들었던 기억이 난다. 공부한지 오래되었고 상대적으로 다른 것에 비해 소홀히 했던 것이 컴퓨터과학 이론이라 배열 자료구조의 특징에 대해 복습할 수 있는 좋은 기회였다.
궁금한 내용이 있거나, 잘 이해되지 않는 내용이 있다면 적어보세요.
이진 검색이 데이터가 정렬되어 있다는 정렬 조건을 만족해야 사용할 수 있다는데, 정렬 알고리즘이 무조건 O(logn) 보다는 느릴테니 배보다 배꼽이 큰 것 아닌가? 과연 어떻게 적용될 수 있을까?
What's on your mind?