#6. IT 5분 잡학사전 - 자료구조와 알고리즘 필요성과 이해

• Day.6
• 오늘 읽은 범위: 챕터 22 ~ 챕터 25
• 오늘의 TIL 3줄 요약

1.  자료구조와 알고리즘-> 필요하면 공부 시작하자
2.  자료구조는 데이터의 정리(선반정리랑 비슷함)
3.  알고리즘은 효율적 방법 선택(지름길 찾기랑 비슷함)

---

책에서 기억하고 싶은 내용을 써보자

• 코딩 공부를 시작할 때부터 자료구조와 알고리즘을 공부할 필요는 없다고 생각해(132p)

---

오늘 읽은 소감은? 떠오르는 생각을 가볍게 적기

[ 자료구조와 알고리즘, 백준 풀기 전에 봤어야지 ]

취업 준비를 한다고 하면 무작정 하듯 나 역시 코테를 준비하기 위해 무작정 백문 문제풀이를 준비했었고, 이해되지 않은 상태에서의 백준 문제 풀이가 그다지 도움이 되지 않는다는 것을 절실히 느꼈다.

자료구조와 알고리즘이 무엇인지 간단하고 쉬운 예시로 돕고 실제로 어떻게 활용될 수 있을지 간단한 사례를 덧붙여 설명하는 방식이 매우 좋았다. 알고리즘 책들을 보면 대학 수학 교재처럼 수식으로 표현하고 수식으로만 설명하는 경우가 많아서 알고리즘을 책을 봐도 이해되지 않는 경우도 있었기 때문이다.

자료구조와 알고리즘을 지금 당장 적용하는 방안까지는 모르겠지만, 어떠한 것이다하는 것을 이해하는데에 큰 도움이 된 것은 분명하다.

---

ep22. 자료구조와 알고리즘은 필수라고?

 "알고리즘이....", "자료구조는...", "회사 면접 볼때 꼭...."  

근데 왜 배워야 되는가? 몰라도 만드는 거 자체에는 문제는 없는데? 언제 필요한가?

코드를 효율적으로

코드가 돌아가는 수준 -> 코드 정리 [이때 자료구조와 알고리즘이 필요]

알고리즘: 컴퓨터에게 내리는 지시 사항을 나열한 것

등교 알고리즘
1. 일어나기->2. 가방 챙기기->3. 교복 입기->4. 출발

이러한 알고리즘 중에는 더 효율성이 좋은 것도 있음

대표적인 예시가 길찾기 알고리즘인 패스파인더pathfinder 알고리즘

목적지까지의 최단 경로를 안내해줌.

또 다른 알고리즘은 압축compression 알고리즘. 이미지를 최대한 보존하면서 효율적으로 용량을 줄이는 알고리즘

자료구조: 데이터를 효율적으로 보관하고 찾기

만약 FE라면 BE에서 JSON 데이터를 가져와서 화면에 보기 좋게 띄워야 할텐데, 데이터가 정돈되지 않았다면? 

택배 회사로 예를 들어서 짐이 아무렇게나 쌓여 있으면?

=> 이래서 필요한 게 자료구조

데이터를 작은 것 - 큰 것 순으로 정리할 것인가?

이름을 붙여서 정리할 것인가?

데이터가 들어온 순서대로 정리할 것인가?

프로그램의 목적만큼 자료구조 역시 다양하게 적용될 수 있음

 

ep23. 배열이 뭐죠?

가장 먼저 볼 수 있는 자료구조인 배열array.

읽기read, 검색search, 추가add, 삭제delete. 그리고 그 과정에서의 시간 복잡도 timecomplexity

시간복잡도? 작업 속도. 프로그램의 작업 속도를 측정하는 방법. 시간을 측정하는 것이 아니라 얼마나 많은 단계를 거치는 것인지를 측정함. 어떤 코드는 5단계, 어떤 코드는 20단계가 필요하면 5단계가 더 작업 속도가 빠르다고 하는 것

메모리(컴퓨터의 기억 공간)는 휘발성/비휘발성으로 나뉨.

비휘발성 메모리는 컴퓨터의 하드디스크와 같은 것. 휘발성 메모리는 램(RAM)

하드디스크는 껐다 켜도 되지만 RAM은 껐다 켜면 사라지는 데이터.

RAM에는 프로그램에 필요한 데이터-변수, 함수-가 저장되고 위치 상관 없이 일정한 접근 속도를 보장함.

램은 주소가 각각 있고 그를 이용해서 빠르게 데이터를 찾을 수 있음. 예를 들어 배열 4개짜리?

	0번	1번	2번	3번

이런 식으로 4개의 배열이라고 램은 생각할 것임

 

배열의 구체적인 특징

특징1. 배열을 읽는 방법과 속도. 배열은 박스를 위 그림처럼 0부터 계산함. 즉 숫자를 0부터 셈. 3번 박스를 열어봐! 라고 하면? 시간 복잡도는 1단계 == 매우빠르다~

특징2. 배열을 검색하는 원리와 속도. 만약 피자가 들어있는 박스를 찾아줘! 라고 한다면? 0번 확인-1번 확인....이렇게 검색하게 됨. (선형 검색linear search)

특징3. 배열에 데이터를 삽입하는 원리와 속도. 만약 5칸 배열에 4칸 아이템이 차있는 상태에서 새로운 아이템을 추가하고 싶다면?

    a. 맨 마지막에 추가하는 경우: 그냥 추가하면 된다.

    b. 중간에 추가하려는 경우: 기존 아이템을 뒤로 한 칸씩 옮기고 나서 중간에 넣어야 됨. 맨 처음에 넣어야 한다면? 하나씩 다 뒤로 옮겨야 하는 복잡도가 생겨버림

    c. 꽉 차 있는 array에 새로운 걸 추가하려는 경우: 더 큰 array를 새로 만든다-> 기존 array 아이템을 옮긴다. 새로운 데이터를 추가한다. 매우 시간복잡도가 어려운 경우가 되어버림

특징4. 배열에서 데이터를 삭제하는 원리와 속도: 삽입과 유사함. 맨 뒤는 삭제하기 쉬움. 중간이나 맨 앞 데이터의 경우가 복잡한데, 처음이나 중간의 데이터를 삭제하면 빈칸을 채우기 위해서 땡겨와야 되기 때문임.

*배열은 줄줄이 붙어서 이어진 형태

*배열의 주소(index)와 길이를 알고 있어서 읽기가 매우 빠름

*배열은 맨 앞부터 차곡차곡 채워져 있음=>삽입과 삭제가 느림

 

ep24. 알고리즘의 속도는 어떻게 표현할까?

시간복잡도: 알고리즘으로 작업을 완료할 때까지 걸리는 절차수 N을 이용해서 O(N), O(log N)으로 표현

= 빅오(Big-O)표기법

선형검색linear-search의 예로 보자면 앞에서부터 하나씩 찾아보는 방식인데 배열의 크기가 커지면 커질수록 시간도 오래 걸릴 것임 = 배열의 길이 N=검색횟수 최대 N ==> 시간복잡도 O(N): 선형 검색 알고리즘은 길이가 N이면 N번 검색과정이 필요하다는 뜻

Big-O는 표기만? NO! 알고리즘 선택에 도움도 줌. 

def print_first(arr):
	print(arr[0])

위 코드는 배열 길이랑 상관 없이 무조건 한 번만 실행됨 => 시간복잡도 O(1)

이렇게 아예 고정 된 시간: 상수 시간constant time 내에 실행된다.

여기서 실행되는 횟수를 늘리더라도print(arr[0])을 몇 번이고 수행하더라도, 실행 단계는 하나니까 시간 복잡도는 같음!!

def pring_all(arr):
	for n in arr:
    	print(n)

for문으로 배열을 돌면서 모든 데이터를 출력하는 함수인데, 이렇게 되면 배열이 길수록 실행 시간이 달라짐!

이때 시간 복잡도 O(N)

def print_twice(arr):
	for n in arr:
    		for x in arr:
        			print(x, n)

이렇게 for문을 두 개 겹쳤다면? 당연히 O(N^) N제곱배일 것임

 

ep25. 검색 알고리즘이 뭐죠? (선형 검색linear search, 이진 검색binary search)

선형 검색은 쉽게 생각해서 맨 앞부터 차례대로 살펴보는 방법임 O(N)

이진 검색은 배열이 클 때 더 좋은 방법. // 대신 데이터 정렬이 끝난 배열에만 사용할 수 있음. sort 끝난 거 말함

이진 검색 방법. 배열 중간부터 시작, 그 값이 우리가 찾으려는 값보다 작냐/크냐? 그러면 한 쪽 선택 -> 다시 그 수보다 크냐 작냐? -> 찾을때까지 반복

예시) 1,2,3,4,5,6,7,8,9,10  =>찾으려는 값 8

1) 5부터 시작 : 5는 찾으려는 값(8)보다 작다 5 기준 왼쪽은 볼 필요 없네. 오른쪽 보자

2) 6~10의 가운데 7이랑 찾으려는 값 비교. 찾으려는 값이 더 크다 왼쪽 버려 오른쪽 보자

3) 8~10의 가운데 9랑 찾으려는 값 비교. 작다 왼쪽이다 오른쪽 버려

4) 답 8

==> 1~10짜리에서 8 찾는데 4번 걸림

==> 선형탐색이면? 1,2,3,4,5,6,7,8... 8번 걸림

배열이 더 크면? 더 빨리 찾을 것임 계속 절반씩 잘라서 보기 때문.

*대신 정렬된 상태여야 한다는 단점은 있지만 배열이 클 때 훨씬 빠르게 찾을 수 있음.

---

궁금한 내용, 잘 이해되지 않는 내용

• 숫자 데이터로 예시를 들어 이진 검색을 이해하기 쉬웠다. 문자 데이터의 이진 검색은 어떻게 진행되는 걸까?