Community

개발자 99% 커뮤니티에서 수다 떨어요!

← Go back

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

#book_club
1년 전
566

오늘 TIL 3줄 요약

  • 효율적인 코딩을 하기 위해 알고리즘과 자료구조를 공부하자

  • 시간 복잡도(Big-O) => 알고리즘으로 작업을 완료할 때 까지 걸리는 수

  • 배열은 메모리에서 연속된 공간이 할당된 자료구조

TIL (Today I Learned) 날짜

2023. 12. 14

오늘 읽은 범위

EP.22~EP.25

책에서 기억하고 싶은 내용을 써보세요.

자료구조와 알고리즘

  • 문제를 처리 하거나 데이터에 접근 할 때 효율적인 알고리즘과 자료구조의 선택으로 더 빠른 처리가 가능하다.

    • 알고리즘 활용 : 패스파인더 알고리즘 - 최적의 길 찾기, 압축 알고리즘 - 데이터 손실의 최소화/용량 최소화

    • 자료구조 종류 : 배열, 스택, 큐, 트리 등등


메모리의 종류

  • 비휘발성 메모리 : 하드 드라이브, CD같이 컴퓨터를 껐다 켜도 데이터가 남아있는 메모리

  • 휘발성 메모리 : RAM과 같이 전원이 꺼지면 데이터가 날아가버리는 메모리

  • RAM의 속도가 빠른 이유는 주소지를 활용하기 때문이다. 한 공간에 데이터 하나를 보관하기 때문에 주소를 통해 빠른 검색이 가능하다.

*RAM(Random Access Memory) : 프로그램의 데이터를 저장하며 CPU의 처리를 보조.

배열

  • 메모리에서 연속된 공간이 할당된 자료구조로 첫 번째 공간의 숫자가 0부터 시작한다. 읽기, 검색, 추가, 삭제가 이루어진다.

  • 컴퓨터는 배열의 시작 주소와 길이를 알고 있으므로 읽는 속도가 빠르지만, 데이터 자체로 검색하는 것은 비효율적이다. (선형 검색의 경우)

  • 배열은 맨 앞부터 채워야 하므로 배열의 맨 앞, 중간 지점의 데이터 삽입과 삭제가 느리다. (선형 검색의 경우22)


Big-O 표기법

시간 복잡도 : 프로그램(알고리즘)의 작업 속도가 얼마나 빠른지 측정하는 방법.

  • Big-O표기법은 작업을 완료할 때 까지 걸리는 작업의 단계/절차의 수 N을 이용해 나타낸 표기법

  • 선형 검색 알고리즘에서) 배열의 검색 횟수는 배열의 크기에 비례하여 증가한다. - O(N)

  • 중첩 반복문으로 배열을 검색하는 경우 이차 시간 - 입력 값의 크기가 증가 함에 따라 시간이 제곱만큼 증가한다. - O(N^2)


검색 알고리즘 선택하기(선형 검색 vs. 이진 검색)

  • 선형 검색(linear search) : 맨 앞부터 차례대로 검색하는 방법으로 최악의 경우 찾는 데이터가 배열의 맨 끝에 존재할 수 있기 때문에 배열의 길이가 늘어날수록 검색 시간이 느려진다.

  • 이진 검색(binary search) : 데이터가 정렬이 되어있는 상태의 특정 자료구조에서만 사용한다. 중앙값을 지정하여 찾는 데이터와의 크기를 비교하여 좌,우 중 후보군을 새로 지정하고, 다시 중앙값을 지정해가며 데이터를 찾는다. 단계가 지날수록 배열의 크기가 반 씩 줄어들기 때문에 데이터의 크기가 늘어나도 검색 속도가 크게 증가하지 않는다.

오늘 읽은 소감은? 떠오르는 생각을 가볍게 적어보세요

  • 처음 배울 때도 너무 어려워서 잘 이해가 되지 않아도 그냥 넘기곤 했던 내용들이라 눈물 찔끔 흘리며 새로운 마당을 맞이했다. 여전히 읽으면서도 잠시 동안 버퍼링이 걸리지만 이해가 훨씬 수월한 느낌🥲

궁금한 내용이 있거나, 잘 이해되지 않는 내용이 있다면 적어보세요.

오늘 읽은 다른사람의 TIL

  • 👇👇

나의 최애 북틸

  • SHONG님의 TIL 👀보러가기

    간결하게 핵심만 짚어서 한번 더 요약을 잘해주심
  • iserendi님의 TIL 👀보러가기

    현업에서의 경험도 남겨주시고, follow up으로 실천하고자 하는 모습 ...짱!
  • hwayoon님의 TIL 👀보러가기

    설명과 예시를 덧붙여주셔서 더 확실하게 이해할 수 있음

다들 요약도 잘하시고 추가로 이해하고자 하는 부분을 찾아서 설명하시는 모습이 대단하다..! 책에 있는 지식을 잘 이해하는 것도 중요하지만 더 알고싶고 이해가 부족하다고 생각되는 부분은 더 적극적으로 찾아봐야겠다.