[엘리스 AI 트랙 2기] Day 6 - 자료구조, 알고리즘

1. 실시간 이론 강의

자료구조란?

컴퓨터 공학 전공 필수 과목이다. 학문으로서도 취업을 위해서도 중요한데, 한번에 이해하는 건 불가능하니 이후에도 꾸준히 시간을 내서 공부해야 한다.

컴퓨터는 데이터를 다양한 자료형으로 다루지만 그 속은 모두 2진수로 구성되어 있다... 등등

각 언어에 대한 비교도 해주셨다. 자바... 언젠가 배워야겠죠 선생님? ㅠ (배우기 무섭다)

그래서 자료구조는

데이터를 다루기 위한 학문이다. 어떻게 효율적이고 빠르게 삽입, 삭제, 정렬, 검색을 할 것인가...
그리고 이 때 비교를 위한 방법이 Big-O Notation이다.(빅-오 표기법)

배열

배열은 그냥 우리가 평소에 보는 리스트를 생각하면 될 것 같다.
삽입: O(1) - 맨 뒤에 추가 / O(n) - 중간에 삽입
접근: O(1) - 위치를 아는 경우의 접근
탐색: O(n) - 위치를 모를 때의 접근 (처음부터 끝까지 다 찾아봐야 한다)
삭제: O(n)

스택(LIFO) - 프링글스, 쌓여있는 접시

스택도 파이썬 리스트를 생각하면 되는데, 우리가 사용할 수 있는 메소드가 pop과 append(push) 밖에 없는 것이다.
구현을 할 때는 stack의 용량이 비어있나 꽉 차있나 판단하는 함수도 필요하다. 꽉차면 받으면 안 되고, 비어있으면 뽑지 못하게 한다.
추가: O(1)
접근: O(n) - 하나씩 뽑아야 하니까
탐색: O(n) - 하나씩 꺼내서 봐야하니까
삭제: O(2n) - 다 뺐다가 다시 넣어야 되는 경우

큐(FIFO) - 놀이공원의 대기열 

먼저 온 사람이 먼저 들어가는 대기열을 생각하면 된다. 예로 든 상황처럼 스케줄링이 필요할 때 사용한다고 한다. 운영체제나 백엔드 단에서도 쓰이나 보다.

front와 rear가 대기열의 머리와 꼬리를 지키는 보디가드인데, 맨 앞사람의 일이 끝나면(입장을 완료하면) front가 다음 사람에게 붙는다. 그리고 새로운 사람이 대기열 뒤에 서면 보디가드는 새로 온 사람에게 붙는다. 이런식으로 front가 rear를 따라잡는 듯한 모습이 나오는데, 이렇게 되면 입장을 이미 완료해서 빈자리가 생겼는데도 줄이 뒤에 있는 우스꽝스러운 모습이 연출되어 메모리 낭비가 발생한다. 이래서 모듈러 연산을 통해 원형큐를 사용해 공간을 좀 더 효율적으로 사용할 수 있다.

추가: O(1)
접근: O(n)
탐색: O(n) 강의에선 N^2이라고 하셨던 거 같은데, 나중에 질문해봐야겠다.
삭제: O(1)

링크드 리스트(단순 연결 리스트)

배열과 다른 점은,
1. index를 통한 access가 불가능하다
2. 배열은 맨 앞에 삽입하면 모든 원소를 한칸씩 뒤로 물려야 하는데, 링크드는 그냥 새로운 front가 이전 front를 가리키기만 하면  된다.

해시테이블

해시함수로 해시값(해시주소)를 만들어 해당하는 주소에 자료를 넣어주는 것이다. 빠르게 접근할 수 있는 게 큰 장점이다. 해시함수로는 나머지 연산을 쓸 수 있는데, 이럴 때는 나머지의 값으로 같은 숫자가 나올 수 있다. (9 나누기 7, 16 나누기 7) 이러면 충돌이 발생하는데, 개방주소방식이나 폐쇄주소방식을 쓸 수 있다. 열린 주소는 그냥 비어있는 주소를 찾아 원래의 주소가 아닌 다른 곳에 저장하는 방식이고, 폐쇄주소방식은 그 안에다 단순연결리스틀 만들어 반드시 원래 주소에 저장하는 것이다.

트리

큰 값은 부모노드의 오른쪽 자식으로, 작은 값은 부모노드의 왼쪽 자식으로 두는 방식의 자료구조이다. 가장 흔한 자료구조이고 다양한 방식이 있다. 다양한 용어, 다양한 종류의 트리가 있다.

2. 실시간 실습 강의

오늘 강의는 너무 유용해서 쓸 글이 없다...
나만..몰래..봐야지...

선생님께서 우리 반의 누군가의 블로그를 보셨다던데, 내 블로그 일 수도 있겠다 ㅎㅎ
선생님 강의 잘 듣고 있습니다!
앞으로도 잘 부탁드립니다 ㅎㅎ

 

출처: 엘리스 AI 트랙 2기 aitrack.elice.io

내일 강의 - 스택, 큐, 트리, 우선순위 큐, 힙

생각보다 얼마 없네... 라고 생각했다.
물론 실시간 강의가 알차니까 괜찮다.

내일도 화이팅!