[IT 5분 잡학사전] - TIL (2023.01.19)

📚 Assignment #07

• 오늘 읽은 범위 : ep.22 자료구조와 알고리즘은 필수라고? ~ ep.25 검색 알고리즘이 뭐죠?
• 기억하고 싶은 내용 (간단하게 내용 정리):
  • ep.22 자료구조와 알고리즘은 필수라고?
    • 자료구조와 알고리즘을 공부하면 코드를 더 효율적으로 만들 수 있기 때문에 개발자가 되고 싶다면 결국에는 자료구조와 알고리즘을 공부하고 자신의 코드에 적용할 수 있어야 한다.
    • 알고리즘이란 컴퓨터에게 내리는 지시 사항을 나열한 것이다. 
      e.g. 지도 앱에서는 목적지까지 최단거리를 알려주는 기능을 구현하기 위해 패스파인더(pathfinder) 알고리즘을 사용한다.
      e.g. PNG, JPG 파일은 이미지를 최대한 덜 손상하면서도 용량을 효율적으로 줄일 수 있는 압축(compression) 알고리즘으로 만들어졌다.
    • 자료구조는 자료를 뜻하는 데이터를 효율적으로 보관하고 찾기 위한 구조이다.
      - 어떤 자료구조를 사용하는지에 따라 프로그램 속도가 빨라지거나 느려진다.
      - 자료구조는 프로그램의 다양한 목적에 맞게 데이터를 작은 것부터 큰 순서로 정리하는 자료구조(데이터 크기 기준), 이름표를 붙여서 정리하는 자료구조(검색을 위한 인덱스 기준), 데이터가 들어오는 순서로 정리하는 자료구조(생성 시간 기준) 등 여러 가지 방식을 가진다.
  • ep.23 배열이 뭐죠?
    
    • 시간 복잡도는 프로그램의 작업 속도가 얼마나 빠른지(작업이 얼마나 많은 단계를 거치는지) 측정하는 방법이다.
      -> 시간 복잡도는 자료구조, 알고리즘을 공부할 때 꼭 알아야 하는 개념!
    • 메모리는 컴퓨터의 기억 공간을 말한다. 메모리는 휘발성 유무에 따라 2가지로 나눌 수 있다.
      
      • 비휘발성 메모리
        - 컴퓨터 전원을 꺼도 저장한 데이터가 남아있으며 컴퓨터의 하드 드라이브와 같다. 
      • 휘발성 메모리
        - 대표적으로 램(RAM, random access memory)을 들 수 있으며 컴퓨터를 끄면 데이터가 모두 사라진다.
        - 램에는 프로그램의 변수, 함수 등 프로그램에 필요한 데이터가 저장된다.
        - 램은 주소를 가지고 데이터를 찾기 때문에 데이터에 접근하는 속도가 매우 안정되고 빠르다.
    • 배열을 만들 때는 배열의 길이를 지정해 주어야 하며, 배열은 램에 줄줄이 이어진 형태로 공간을 차지하고 있다.
    • 배열의 특징
      -> 배열을 특징을 이야기하려면 배열에서 읽기(read), 검색(search), 추가(add), 삭제(delete) 과정에서의 시간 복잡도(time complexity)를 알아야 한다.
      
      • 특징 1. 배열을 읽는 방법과 속도
        - 컴퓨터는 0부터 숫자를 센다. 배열은 1단계 알고리즘(몇 번째 데이터를 보라고 지정함)을 가졌기 때문에 배열을 읽는 속도는 매우 빠르다.
        - 컴퓨터는 배열의 시작 주소와 길이를 알고 있다. 그래서 배열은 읽는 속도가 아주 빠르다.
      • 특징 2. 배열을 검색하는 원리와 속도
        - 배열에서 검색은 빠르지 않다. 검색은 읽기보다 많은 시간이 필요하다.
        - 배열에서 검색하는 방식은 많지만 선형 검색(linear search)을 예로 들면 배열 검색은 특정 데이터를 검색하기 위해 배열의 박스를 모두 열어보고 데이터를 확인하는 방식으로 진행되기 때문에 비효율적이다.
      • 특징 3. 배열에 데이터를 삽입하는 원리와 속도
        - 배열에 빈 여유 공간이 있다면 배열의 길이만큼 뒤로 가서 맨 끝에 데이터를 삽입한다.
        - 배열 중간에 데이터를 추가하려면 다른 데이터들을 뒤로 옮겨야 한다.
        - 배열에 데이터가 꽉 차있다면 더 큰 배열을 새로 만들고 이전 배열을 복사한 후 새 데이터를 추가한다.
      • 특징 4. 배열에서 데이터를 삭제하는 원리와 속도
        - 배열에서 데이터를 삭제하는 원리는 삽입하는 원리와 비슷하다.
        - 배열은 맨 앞부터 차곡차곡 채워져 있어야 하므로 마지막 데이터 삭제가 가장 쉽고, 맨 앞에 있는 데이터 삭제하기가 가장 어렵다. 중간 데이터를 삭제하면 뒤쪽 데이터를 다 끌어당겨야 한다.
        - 그래서 배열은 삽입과 삭제가 느리다.
  • ep.24 알고리즘의 속도는 어떻게 표현할까?
    • 시간 복잡도를 이야기할 때는 알고리즘으로 작업을 완료할 때까지 걸리는 절차 수 N을 이용해서 O(N), O(log N)과 같이 표현하며, 이것을 빅오(Big-O) 표기법이라고 한다.
    • "선형 검색 알고리즘의 시간 복잡도는 O(N)이다." == "선형 검색 알고리즘은 배열의 길이가 N일 때 총 N번 검색하는 과정이 필요하다."
    • Big-O 표기법은 시간 복잡도를 표현하는 방법(알고리즘의 속도를 표현하는 방법)이며, 설명을 간단하게 만들어 주고 알고리즘 분석을 빠르게 할 수 있게 해준다.
      -> Big-O 표기법은 개발자가 될 거라면 꼭 알아야 할 중요한 개념이다!
    • 시간 복잡도가 O(1)인 함수는 배열의 길이와 상관없이 딱 한 번만 실행하고 끝난다. 그리고 이것을 이미 실행 횟수가 고정으로 정해진 '상수 시간(constant time) 내에 실행된다'라고 말한다.
      - Big-O는 실행 단계에 영향을 주는 요소만 보기 때문에 시간 복잡도가 O(1)인 함수를 두 번 썼다고해서 시간 복잡도가 O(2)가 되지는 않는다. 이때 시간 복잡도는 O(1)이다.
      - 배열 길이가 길어져도 시간은 항상 같으니까 O(1)
      Big-O로서 해당 함수는 배열 길이와 상관 없이 늘 실행 횟수(검색 시간)가 같으니까 같다는 의미로 1을 사용한다.
    • 시간 복잡도가 O(N)인 함수는 배열의 모든 데이터를 출력하는 함수이다. 이 경우 배열의 길이에 따라 실행 시간이 달라진다.
      - 배열 길이가 길어지면 시간은 그만큼 늘어나니까 O(N)
    • 또 다른 시간 복잡도로 중첩 반복문이 있을 때 발생하는 이차 시간(quadratic time)이 있다. 이 경우 배열 길이가 길어질수록 작업 속도(시간)는 제곱배로 느려진다. Big-O로 나타내면 O(N^2)이다.
      - 배열 길이가 길어지면 시간은 제곱배로 느려지니까 O(N^2)
  • ep.25 검색 알고리즘이 뭐죠?
    • 배열 안에 있는 숫자 찾는 과정예시로 검색 알고리즘 이해하기.
      어떤 알고리즘을 선택했는지에 따라 작업 속도에 차이가 생긴다.
    • 선형 검색(linear search) 알고리즘 [ y = x 형태의 우상향 직선 그래프 ]
      - 가장 자연스러운 검색 방법. 맨 처음 배열부터 데이터를 비교하며 검색을 시작한다.
      - 찾는 데이터가 가장 마지막에 있는 경우라면 비효율적이다. 배열의 길이가 길어지는 만큼 검색 시간도 길어진다.
    • 이진 검색(binary search) 알고리즘 [ y = log x 형태의 우상향 곡선 그래프 ]
      - 이진 검색은 단계 마다 배열의 절반을 제외할 수 있어 속도가 빠르며, 특히 데이터가 많을 때(배열의 크기가 클 때) 선형 검색보다 더 좋은 알고리즘이다.
      - 데이터가 순서대로 정렬되어 있는 데이터의 정렬이 끝난 배열에서만 사용할 수 있다. (특정 알고리즘은 특정 자료구조에서만 사용할 수 있다!)
      - 이진 검색은 데이터의 정렬이 끝난 배열의 중앙에서 검색을 시작한다. 배열의 중앙값을 기준으로 찾으려는 값과 비교하며 왼쪽 또는 오른쪽으로 이동하고 다시 중앙값을 정하고, 찾으려는 값과 비교하는 것을 반복하여 탐색해 원하는 값을 찾아낸다.
      • 이진 검색 정리
        - 이진 검색 알고리즘은 거대한 배열을 다룰 때 효과적이다.
        - 이진 검색 알고리즘을 사용하고 싶다면 배열은 항상 정렬되어 있어야 한다.
• 오늘의 파트에 대한 소감 (떠오르는 생각) :
  
  • 자료구조와 알고리즘이 중요하다는 건 알았지만 간단한 개념이나 종류 정도만 들어보았다. 특히 시간 복잡도와 Big-O 표기법에 대한 내용은 처음 알게 되었다. 뭔가 잘 읽어보면 어려운 개념은 아닌 것 같으면서도 아직 알쏭달쏭한 느낌이다. 오늘 파트부터 컴퓨터과학 전공 내용들이 나와서 난이도가 훅 올라간 느낌. 단번에 이해하기는 쉽지 않아서 내용을 반복해서 읽고 정리하느라 시간이 평소보다 좀 더 걸렸다.
    코딩테스트 알고리즘 문제를 풀이 대비로도 공부를 깊게 해야할 것 같다는 생각이 들었다. 자료구조와 알고리즘은 특히나 전공수업 들을 때 정말 빡집중해서 공부해야겠다. 각오를 단단히하자.
• 추가로 알게된 것 (책내용+a 로 궁금한 것, 이해가 가지 않는 것 등)
  • 알고리즘의 시간 복잡도, Big-O 표기법에 대한 내용은 깊은 공부가 필요할 듯!
• 소감 3줄 요약 (오늘 TIL 3줄 요약) :
  
  • 알고리즘은 컴퓨터에게 내리는 지시사항, 자료구조는 데이터를 효율적으로 보관하고 찾기 위한 구조!
  • 배열은 컴퓨터가 배열의 시작 주소와 길이를 알고 있기 때문에 데이터를 읽는 속도는 빠르지만, 맨 앞부터 차곡차곡 채워져있는 구조로 인해 데이터의 삽입과 삭제는 느리다.
  • Big-O 표기법으로 알고리즘의 시간 복잡도(알고리즘의 속도)를 표현할 수 있다.