[TIL] IT 5분 잡학사전 #22-#25

오늘 TIL 3줄 요약

• 알고리즘은 컴퓨터에게 내리는 지시 사항을 나열한 것이다.
• 배열은 위치를 지시해서 데이터를 읽을 수 있으며 배열에서 검색은 빠르지 않다.(박스를 모두 열어 보고 들어 있는 데이터를 확인하기 때문 이를 선형검색 linear search라고 한다)
• 선형 검색 알고리즘은 맨 처음 배열부터 검색을 시작하고 이진 검색 알고리즘은 데이터의 정렬이 끝난 배열에서만 사용할 수 있다. 거대한 배열을 다룰 때 효과적이다.

 

TIL (Today I Learned) 날짜

2023.03.21

오늘 읽은 범위

3장. 코딩별 안내서_ 컴퓨터 공학 편

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

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

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

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

 

 

책에서 기억하고 싶은 내용

• 알고리즘은 컴퓨터에게 내리는 지시사항을 나열한 것이다. 실생활에서 네이버 지도 앱에서 가장 중요한 핵심 기능(목적지까지 최대한 빨리 가는 방법)을 구현하기 위해 패스 파인더(pathfinder)알고리즘을 사용한다. 이미지를 최대한 덜 손상하면서도 용량을 효율적으로 줄일 수 있는 알고리즘을 압축 알고리즘(compression) 이라고 한다. 데이터를 다룰 때, 효율성과 필요성을 위하여 자료구조를 공부해야 할 필요성이 있다.
• 메모리는 컴퓨터의 기억공간이고 비휘발성 메모리는 컴퓨터의 하드 드라이브(C,D) 같은 것이다. 휘발성 메모리는 컴퓨터를 끄면 램에 있는 데이터는 사라지고 프로그램에 필요한 데이터가 저장되며 램(RAM, random access memory)을 들 수 있다.
• 배열은 위치를 지시해서 데이터를 읽을 수 있다. 배열에서 검색은 빠르지 않다.(박스를 모두 열어 보고 들어 있는 데이터를 확인하기 때문 이를 선형검색 linear search라고 한다)컴퓨터는 배열이 어디서 시작하는지, 배열의 길이는 얼마인지를 기억하고 있다.
• 배열은 맨 앞부터 차곡차곡 채워져 있어야 하며 배열은 삽입과 삭제가 느리다.
• 선형 검색 알고리즘의 시간 복잡도는 O(N)이다. 즉 선형 검색 알고리즘은 배열의 길이가 N일 때 총 N번 검색하는 과정이 필요하다.
• 시간 복잡도를 표기하는 방법을 Big-O 표기법 이라고 한다. 단지 설명을 간단하게 만들어 줄 뿐 아니라 알고리즘 분석을 빠르게 할 수 있게 해주고, 실행 단계에 영향을 주는 요소만 본다.
• 선형 검색 알고리즘은 맨 처음 배열부터 검색을 시작한다.
• 이진 검색 알고리즘은 데이터의 정렬이 끝난 배열에서만 사용할 수 있다. 거대한 배열을 다룰 때 효과적이다.

오늘 읽은 소감? 떠오르는 생각

• 알고리즘이 뭘까 하면서 생각해보던 때가 있었는데, 책에 나온 등교 준비 알고리즘 예시가 아주 좋았다. 머릿속으로 상상하며 아 이게 알고리즘이구나 하고 이해하기 쉽도록 알려준 내용에 끄덕끄덕하며 읽었다. 배열에 대한 내용에서 선형 검색이 데이터 내용을 하나하나 다 열어보고 확인한다는 내용에 대해서 그림으로 쉽게 이해할 수 있었고, 선형 검색 알고리즘과 이진 검색 알고리즘에 대한 설명도 명확하여 좋았다.
• https://7357.tistory.com/145

선형 탐색(Linear search)과 이진 탐색(Binary search)에 대해 알아보자 (Feat.JAVA)