개발자 99% 커뮤니티에서 수다 떨어요!
📌오늘 TIL 3줄 요약
알고리즘은 컴퓨터에게 내리는 지시 사항을 나열한 것/자료구조는 데이터를 효율적으로 보관하고 찾기 위한 것!
알고리즘의 시간 복잡도는 작업 단계의 수와 비례한다.
선형 검색은 순서대로/이진 검색은 중앙에서 up & down !
📆TIL (Today I Learned) 날짜
2023.10.12
📖오늘 읽은 범위
ep22. 자료구조와 알고리즘은 필수라고?
ep23. 배열이 뭐죠?
ep24. 알고리즘의 속도는 어떻게 표현할까?
ep25. 검색 알고리즘이 뭐죠?
📑책에서 기억하고 싶은 내용을 써보세요.
(ep22)
자료구조와 알고리즘은 언제 필요할까?
: 코딩 공부를 시작할 때부터 자료구조와 알고리즘을 공부할 필요는 없다.
프로그램이 돌아가는 수준으로 개발을 한 후에 코드를 정리, 관리 하는데,
이때 자료구조와 알고리즘이 필요하다.
알고리즘
: 알고리즘이란 컴퓨터에게 내리는 지시 사항을 나열한 것이다.
(등교 준비하기 알고리즘도 더 효율성이 좋은 알고리즘을 사용한다면 등교 속도가 빨라지듯이,
컴퓨터도 마찬가지이다.)
자료구조
: 자료구조는 데이터를 효율적으로 보관하고 찾기 위한 것이다.
자료구조의 여러가지 방식
⇒ 데이터 크기 기준/데이터를 작은 것부터 큰 순서로 정리
검색을 위한 인덱스 기준/이름표를 붙여서 정리
생성 시간 기준/데이터가 들어오는 순서로 정리 ...등
자료구조의 방식이 다양한 이유
⇒ 프로그램의 목적이 다양하기 때문
(ep23)
배열(array)
: 자료구조이다.
시간 복잡도 = 작업 속도 (작업을 하는데 필요한 단계가 적으면 작업 속도가 빠르다고 함)
메모리
: 컴퓨터의 기억 공간을 말하는데 휘발성 메모리와 비휘발성 메모리로 구분한다.
휘발성 메모리 ⇒ 램(RAM, Random Access Memory)처럼 컴퓨터 전원을 껐을 때 저장한 값이 사라지는 것
비휘발성 메모리 ⇒ 컴퓨터의 하드 드라이브(C, D)처럼 컴퓨터를 껐다가 다시 켜도 데이터가 남아있는 것
RAM은 데이터에 접근하는 속도가 매우 안정되고 빠르다.(주소가 있어서 그 주소를 통해 빠르게 접근)
배열의 시간 복잡도
: 1) 읽는 방법과 속도
⇒ 컴퓨터가 숫자를 0부터 세기 때문에 배열도 0부터 숫자를 매긴다.
이 숫자(주소)를 통해 데이터를 찾기 때문에 읽는 속도가 매우 빠르다.
2) 검색하는 원리와 속도
⇒ (선형 검색)숫자(주소)를 통해 검색하지 않고 들어있는 data를 확인하면서 검색하기 때문에
처음부터 순서대로 확인을 해야 한다.
0번째에 있다면 검색이 빠르게 끝나겠지만 마지막에 있거나 없다면 오래 걸린다.
3) 데이터를 삽입하는 원리와 속도
⇒ 마지막에 삽입하려면 길이만큼 뒤로 가서 추가하면 되니까 편하다.
배열 중간에 추가하려면 그 위치를 비우기 위해 데이터들을 옮기고 삽입해야 하니까 많은 작업이 필요하다.
배열이 꽉 차 있을 때는 새 배열을 만들고 이전 배열을 복사해서 옮긴 다음 추가를 해야해서 가장 느리다.
4) 데이터를 삭제하는 원리와 속도
⇒ 삽입하는 원리와 비슷하다.
마지막 데이터 삭제가 가장 쉽고 맨 앞에 있는 데이터 삭제가 가장 어렵다.
(ep24)
Big-O 표기법
: 시간 복잡도를 절차 수 N을 이용해서 O(N), O(log N)과 같이 표현하는 것
배열의 길이와 상관없이 딱 한 번만 실행하고 끝나는 것은 O(1) (⇒ print(arr[0]))
배열의 길이에 따라 실행 시간이 달라지는 것은 O(N) (⇒ 반복문을 통한 print(arr[n]))
이차 시간(quadratic time) ⇒ 중첩 반복문이 있을 때 발생한다. (⇒ 반복문 안에 반복문 print(x, n))
이차 시간은 배열 길이가 길어질수록 작업 속도가 제곱배로 느려지기 때문에 O(N^2)
(ep25)
선형 검색(linear search)
: 배열의 맨 처음부터 검색한다. (찾는 데이터가 마지막에 있으면 제일 느리게 된다.)
배열 길이가 길어지는 만큼 검색 시간도 길어지기 때문에 y = x 형태이다.
이진 검색(binary search)
: 특정 알고리즘은 특정 자료구조에서만 사용할 수 있는데
이진 검색은 데이터의 정렬이 끝난 배열에서만 사용할 수 있는 특정 알고리즘이다.
(⇒ 정렬이 끝난 배열? 1, 5, 9처럼 뒤죽박죽이 아닌 1, 2, 3 또는 3, 2, 1처럼 보기 좋게 정렬된 배열)
이진 검색은 배열의 중앙에서 검색을 시작하고 up & down한다.(찾으려는 숫자보다 중앙값이 큰지 작은지 확인)
중앙값을 확인해서 한 쪽은 버리고 살린 한 쪽의 중앙값을 또 확인 ...반복 /y = log x 형태이다.
💡오늘 읽은 소감은? 떠오르는 생각을 가볍게 적어보세요.
오늘 책을 읽기 전에 Big-O 표기법을 봤다면 많이 당황했겠지만 오늘 이후에 본다면 당황하지 않을 거 같다 : ) !
❓궁금한 내용이 있거나, 잘 이해되지 않는 내용이 있다면 적어보세요.
😊오늘 읽은 다른사람의 TIL
summereuna님의 TIL (https://velog.io/@summereuna/%EB%85%B8%EA%B0%9C%EB%B6%81-06.-TIL-IT-5%EB%B6%84-%EC%9E%A1%ED%95%99%EC%82%AC%EC%A0%84-e.2225)
👍나의 최애 북틸
danheean님의 TIL(https://nomadcoders.co/community/thread/6515)
↳ 소감 3줄 요약도 추가해서 danheean님의 독서 후 소감을 많이 느낄 수 있었어요 !
hanlyn1110님의 TIL(https://nomadcoders.co/community/thread/6129)
↳ "개발자 꿈나무"라는 표현이 도입부에서 확 눈길을 끌었어요 !
kimberlyj님의 TIL(https://nomadcoders.co/community/thread/8417)
↳ 북클럽 챌린지를 먼저 끝낸 분의 최종 독후감을 보니까 저의 마지막 날은 어떤 뿌듯함이 있을까 기대가 돼요 !