[북클럽][TIL] <IT 5분 잡학사전> - Day 7. 컴퓨터 공학 지식 (1)

오늘 읽은 범위

• 마당 3. 컴퓨터 공학편 ep22 ~ 25

 

책에서 기억하고 싶은 내용

• ep22 : 자료구조, 알고리즘
  • 코드를 관리/협업하기 편하고, 속도가 빠르고, 효율적으로 만들기 위해 필요함
  • 알고리즘은 컴퓨터에게 내리는 지시 사항을 나열한 것
  • 생활 속 알고리즘 종류
    • 지도 앱의 핵심 기능 구현을 위한 패스파인더(pathfinder) 알고리즘
    • 이미지/파일 압축(compression) 알고리즘
  • 자료구조는 데이터를 효율적으로 보관하고 찾기 위한 방식이고, 사용되는 프로그램의 목적에 따라 다양함
  • 컴퓨터의 기억 공간인 메모리와 연관 깊음. 휘발성에 따라 휘발성 메모리, 비휘발성 메모리로 나뉨.
    • 비휘발성 메모리: 컴퓨터 하드 드라이브
    • 휘발성 메모리: 램(RAM, random access memory) - 컴퓨터 종료 시 사라짐.
      cf. 램 메모리: 주소지가 적힌 박스가 많이 있는 창고와 비슷한 개념. 
      프로그램에 필요한 데이터들이 저장되고, 주소로 데이터를 찾기 때문에 항상 일정한 접근 속도로 데이터에 접근 가능.

 

• ep23 : 배열
  • 자료구조 중 배열(array) - 읽기, 검색, 추가, 삭제 과정이 자주 발생
  • 배열 생성 시, 램에 배열의 길이가 몇인지 알려줘야 램에서 그만큼 공간을 할당해줌
    -> 연이어 붙은 모양으로 N개의 배열 공간 생김. 컴퓨터는 배열의 시작 주소 & 길이 를 안다!
  • 읽기
    • 배열의 첫번째 박스는 0번 숫자가 매겨짐
    • 세번째 박스를 찾으려면 2번 숫자로 접근
    • 배열에서는 위치를 정확하게 지정하기 때문에 데이터를 찾는 속도 매우 빠름
  • 검색
    • 박스의 순서를 지정하는 것이 아닌 박스 안에 내용물을 찾는 과정이므로 데이터를 확인해야하니, 검색은 읽기보다 시간 더 많이 소요됨
    • 검색하는 방식에는 시간 복잡도를 줄이기 위한 여러 알고리즘 있음
  • 삽입
    • 빈 박스가 더 있는 상태에서 맨 마지막 박스에 내용물 추가
    • 중간에 내용물을 추가하려면 그 뒤쪽으로 내용물을 한칸씩 이동시켜야함. 배열이 길면 많은 작업이 필요해짐
    • 모든 박스가 꽉 차있는 상태라면, 더 큰 배열을 새로 만들고 -> 이전 배열을 복사해서 -> 옮긴 다음 새 데이터 추가.. 가장 느린 경우!
  • 삭제
    • 맨 마지막 데이터를 삭제하는 경우 내용물 꺼내서 삭제
    • 중간 또는 맨 앞 데이터를 삭제하는 경우 뒤쪽 데이터를 모두 다 앞으로 이동시켜야함. (배열은 맨 앞부터 채워져야함)

 

• ep24 : 알고리즘 속도
  • 알고리즘 속도는 수행하는 작업을 몇 단계로 하느냐로 결정됨. 즉, 프로그램의 속도가 얼마나 빠른지 측정하는 방법인 시간 복잡도 가 핵심. 
  • 시간 복잡도: 알고리즘으로 작업을 완료할 때까지 걸리는 절차 수 N을 이용해 O(N), O(log N) 으로 표현. 빅오(Big-O) 표기법
  • Big-O는 실행 단계에 영향을 주는 요소만 고려함
    • 이미 실행 횟수가 고정으로 정해졌다면 상수 시간(constant time) 내에 실행된다 -> 시간 복잡도 = O(1)
    • 배열의 길이에 따라 실행 횟수가 달라진다면 배열의 길이가 N일 때 N번 실행되는 것 -> 시간 복잡도 = O(N)
    • 중첩 반복문이 있다면 작업 속도는 제곱배로 느려짐. 배열의 길이가 N일 때 N^2(quadratic time) 번 실행되는 것 -> 시간 복잡도 = O(N^2)

 

• ep25 : 검색 알고리즘
  • 선형 검색(linear search) 알고리즘 : 배열의 맨 앞/뒤 요소부터 검색해나가는 가장 자연스러운 검색 방법. 
  • 이진 검색(binary search) 알고리즘 : 데이터 순서 정렬이 된 배열에서 중앙에 위치한 요소부터 검색하여 찾으려는 값보다 작은지 큰지 확인. 중앙값 기준으로 작으면 왼쪽 배열 요소에서, 크면 오른쪽 배열 요소에서 다시 중앙값과 비교하며 찾아가는 검색 방법
  • 배열의 크기가 매우 클 때, 이진 검색 알고리즘을 사용하면 탐색 속도가 매우 빨라짐.
    이진 검색 알고리즘은 단계마다 배열의 절반을 제외할 수 있기 때문에 y = log x (x: 배열길이, y:검색시간) 그래프 형태를 보임.
    단, 항상 정렬이 되어있어야만 대소비교가 가능하므로 정렬된 배열에서만 이진 검색 알고리즘 사용 가능! 

 

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

• 다시 옛 기억들이 떠오르며,, 재밌게 정리했다
• 잘 모르는 입문자에게 알려줘야한다면 이렇게 설명하면 되겠다- 더 쉽게 설명하기 위한 방법이 뭐가 있을까? 하는 생각이 들었다
• 이 책을 만들 때도 언급할 개념들의 순서를 어떻게 배치하면 좋을 지 많이 고민하신 것 같다. A를 설명하기 위해서는 B를 얘기해야되는데, B라는 개념도 설명해야하니,, ㅎㅎ 새삼 책 하나를 쓰는데 얼마나 많은 고민이 있을까 까지도 느껴버렸다.

 

3줄 요약

- 배열은 시작 주소와 길이를 알 수 있어 읽기는 매우 빠르지만, 삽입과 삭제는 느리다

- 알고리즘의 속도인 시간 복잡도를 표현하는 Big-O 표기법

- 정렬이 된 배열에서 검색을 하려면 이진 검색 알고리즘을 사용하자

 

오늘의 2번째 과제 : 다른 사람의 최애 북틸

https://nomadcoders.co/users/inalee

이렇게 프로필을 가져오는 것이 실례일 수도 있지만, 작성하신 TIL 글을 한번에 보기에 편해서 링크를 가져와봤다.
커뮤니티 채널에 느낀 생각들을 쭉 써내려가셔서 가독성이 좋지는 않지만 대부분 재미있게 읽었다! 자주 들어가서 보고싶은 최애 TIL 이다

 

 

https://let-d0-study.tistory.com/category/스터디/노마드코더%20북클럽

내용 정리가 꼼꼼하고, 항목별로 본인의 생각까지 작성해놓으신 부분이 좋았다!

 

- 커뮤니티 채널에 좋은 TIL이 되게 많다! 시간나면 다른 사람 북틸도 읽어봐야지,, 일단 오늘은 2명