개발자 99% 커뮤니티에서 수다 떨어요!
[IT 5분 잡학사전] TIL #07
오늘 TIL 3줄 요약
초기에는 일단 코드를 정상적으로 실행하는 것을 목표로 삼되, 추후 효율적인 코드를 작성하기 위해서는 꼭 자료구조와 알고리즘 공부를 해야한다!
자료구조 중 배열(array)은 맨 앞부터 차곡차곡 채워져 있기 때문에 삽입(insert)와 삭제(delete)가 느리다.
대표적인 검색 알고리즘으로는 선형 검색(linear search)과 이진 검색(binary search)가 있고, 시간 복잡도(time complexity) 표기법 중 Big-O 표기법으로 나타내었을 때, 선형 검색은 O(N)이고, 이진 검색은 O(log N)이다.
TIL (Today I Learned) 날짜
2023.01.19
오늘 읽은 범위
에피소드 22 - 에피소드 25
책에서 기억하고 싶은 내용을 써보세요.
데이터를 효율적으로 보관하고 찾기 위해 자료구조를 알아야하고, 보다 빠른 속도로 실행하기 위해 알고리즘을 알아야 한다.
자료구조 종류 예시
데이터 크기 기준으로 정리하는 방식
검색을 위한 인덱스 기준으로 정리하는 방식 -> 배열(array)
데이터 생성 시간 기준으로 정리하는 방식
실생활에서 알고리즘 활용 사례
목적지까지 최대한 빨리 가는 방법 -> pathfinder 알고리즘
png, jpg 파일 -> 이미지 압축 알고리즘
배열(array)은 읽는 속도가 매우 빠르나, 추가(add)와 삭제(delete)가 느리다.
읽기(read)
예시) “배열의 2번째 데이터를 줘!”
컴퓨터가 배열의 2번째 데이터에 바로 접근하므로 속도가 매우 빠르다.
검색(search)
예시) “피자를 찾아!”
컴퓨터가 배열의 0번째 데이터부터 읽으면서 ‘피자’ 데이터를 찾기 때문에 ‘피자’가 배열에서 몇번째에 위치하느냐에 따라 찾는 속도가 달라진다. (최악의 시나리오로, 배열에 ‘피자’ 데이터가 없다면, 배열의 전체 데이터를 모두 읽고 ‘피자’ 데이터가 없다고 리턴할 것이다.)
추가(add) 또는 삽입(insert)
예시 1) “배열의 마지막에 토마토를 추가해줘!”
예시 1-3 중 제일 쉬운 케이스로, 컴퓨터가 배열의 크기(N)를 알고 있으므로 N번째 인덱스에 ‘토마토’ 데이터를 추가하며 된다.
예시 2) “배열의 중간에 토마토를 추가해줘!”
배열의 중간에 토마토를 추가하기 위해 ‘토마토’ 데이터를 추가할 위치 이후의 데이터를 뒤로 한 칸씩 옮겨야 한다.
예시 3) “배열의 마지막에 토마토를 추가해줘! 어? 배열이 꽉 찼네? 더 큰 배열에 추가해줘!”
더 큰 크기의 새로운 배열을 생성하고 기존 데이터를 복사한 후 ‘토마토’ 데이터를 추가해야하기 때문에, 예시 1-3 중 시간이 제일 많이 소요된다.
삭제(delete)
예시) “감자 삭제해줘!”
‘감자’ 데이터가 삭제됨으로써 발생한 빈 칸을 채우기 위해 기존 ‘감자’ 데이터 위치 이후의 데이터를 앞으로 한 칸씩 옮겨야 한다.
시간 복잡도(time complexity)는 프로그램의 작업 속도가 얼마나 빠른지 측정하는 척도이다. 대표적으로 최악의 실행 시간을 표기하는 Big-O 표기법이 있다.
Big-O 표기법(배열의 크기가 N일 때)
O(1) -> 한 번만 수행한다!
O(N) -> 최악의 경우, N번 수행한다!
O(N²) -> 최악의 경우, N²번 수행한다!
검색 알고리즘
선형 검색(linear search) : 배열의 첫번째 인덱스부터 시작해서 데이터를 찾을 때까지 검색하는 방법
시간 복잡도(Big-O 표기법 기준) : O(N)
이진 검색(binary search) : 배열의 중앙 값을 기준으로 찾으려는 데이터와 중앙 값을 비교하여 검색하는 방법
사전 조건 : 데이터가 정렬된 상태여야 한다.
시간 복잡도(Big-O 표기법 기준) : O(log N)
배열의 크기가 클 때, 효과적인 검색 알고리즘이다.
오늘 읽은 소감은? 떠오르는 생각을 가볍게 적어보세요
전공 서적으로 자료구조와 알고리즘을 공부하면 되게 복잡하고 어려운데,
매우 알기 쉽게 잘 설명되어 있어 감탄합니다..!
궁금한 내용이 있거나, 잘 이해되지 않는 내용이 있다면 적어보세요.
-
오늘 읽은 다른사람의 TIL
mjeong827님의 TIL (https://nomadcoders.co/community/thread/6612)