[IT 5분 잡학사전 - 컴퓨터 공학 편] DAY9, EP.26 ~ EP.29

✔ 오늘의 3줄 요약

• 알고리즘 3가지, 버블정렬, 선택정렬, 삽입정렬
• 스택 큐는 문법이 존재 하지 않으며 규칙을 지키는 것이다
• 해시 테이블은 빠르다.

✔ 오늘 읽은 범위

EP.26 정렬 알고리즘이 뭐죠?

EP.27 스택, 큐가 뭐죠?

EP.28 해시 테이블이 뭐죠?

EP.29 개발자 필수 소양, 클린 코드!

 

 

✔ 기억하고 싶은 내용

- 정렬알고리즘

1. 버블정렬

버블정렬은 좋은 알고리즘이라 할 수 없다. 실제로 많이 사용하지도 않는다. 정렬 공부용으로는 좋다.

8 1 2 6 3 4 9 5 7 을 버블정렬 시 8과 1을 비교

1 8 2 6 3 4 9 5 7 이런식으로 왼쪽이 크면 오른쪽과 자리를 바꿈

 

1 2 6 3 4 8 5 7 9 - 한 싸이클 종료

1 2 3 4 6 5 7 8 9 - 두번 째 싸이클 종료

 

버블정렬의 시간 복잡도는 비교횟수, 교환 횟수 등을 고려하면 O(N^2)이다.

시간복잡도가 O(N^2)인 알고리즘은 좋은 알고리즘이라고 하지 않는다. 그래서 버블정렬은 잘 안 쓴다.

 

2. 선택정렬(selection sort)

다음 배열에서 선택 정렬은 전체 데이터 중에 가장 작은 데이터 또는 가장 큰 데이터의 위치를 따로 기억하는 방식으로 작업한다.

8 6 2 1 3 4 9 5 7

위 배열에서 8은 0으로 보관 6은 1로 보관

이런 방식으로 0번째부터 9번째까지 보며 가장 작은 데이터인 1의 위치 3이 저장

 

가장 작은 데이터를 알게 되었으니 0번째와 3번째 위치와 데이터를 교환한다.

1 6 2 8 3 4 9 5 7 - 한 사이클 종료

 

0번째 위치는 신경 쓸 필요가 없어지고 1번째 위치부터 사이클이 시작되며 다시 교환

1 2 6 8 3 4 9 5 7 - 두 번째 싸이클 종료

 

선택 정렬의 시간 복잡도는 O(N^2)이다. 하지만 버블 정렬보다는 훨씬 효율적이다.

이유는 자리를 바꾸는 연산은 사이클당 1번씩만 한다.

 

3. 삽입 정렬(insertion sort)

앞에 있는 데이터를 보면서 배차하는 특징이 있다.

8 6 2 1 3 4 9 5 7

 

6 8 2 1 3 4 9 5 7 - 한 싸이클 종료

6 배치할 위치를 앞쪽과 1개씩 비교하면서 확인한다.

6은 8보다 작으니까 8을 뒤로 밀고 6을 배치시킨다.

 

그다음 싸이클은 두 번째 데이터부터 비교를 시작한다.

2 6 8 1 3 4 9 5 7 - 두 번째 싸이클 종료

앞의 8과 비교해서 2가 작기에 앞으로 밀어 넣고 또 앞의 6과 비교해서 작으니 앞으로 또 밀어 넣는다.

 

1 2 6 8 3 4 9 5 7 - 세 번째 싸이클 종료

1 2 3 6 8 4 9 5 7 - 네 번째 싸이클 종료

 

삽입 정렬은 선택정렬, 버블 정렬보다 빠르다. 그런데 시간 복잡도는 O(N^2)이다.

 

시간 복잡도는 같은데 속도 차이가 나는 이유

시간 복잡도를 단순히 측정했을 때 그렇다.

알고리즘은 초기 데이터 상태에 따라 처리 속도가 달라지는 특징이 있다.

기계적으로 측정한 시간 복잡도는 같아도 평균적으로 빠른 알고리즘은 있을 수 있다.

 

 

- 스택, 큐

큐나 스택은 문법이 존재하지 않다. 배열에 큐의 규칙을 부여하면 그 배열은 큐라고 할 수 있다.

이런 개념을 추상 자료구조(abstract data type, ADT)라고 부른다.

 

스택의 규칙 (LIFO, last in, first out)

• 규칙 1 : 위에서 데이터를 쌓는다.
• 규칙 2 : 위에서부터 데이터를 뺀다.

스택은 뭘로 구현해도 상관이 없고 규칙만 지키면 된다.

 

큐의 규칙

• 규칙 1 : 위로 데이터를 쌓는다.
• 규칙 2 : 아래에서부터 데이터를 뺀다.

먼저 줄에 서있는 사람이 먼저 타는 버스 정류장과 같다.

큐 또한 뭘로 구현해도 상관없고 배열을 예로 든 것일 뿐 규칙만 지키면 된다.

 

스택, 큐는 언제 사용하는지

 

웹브라우저 뒤로 가기 버튼 - 스택

맨 마지막 방문한 곳을 빼는 규칙이 있는 스택으로 구현

 

되돌리기 단축키 컨트롤+Z - 스택

 

쇼핑몰 주문 처리 - 큐

주문이 들어온 순서대로 데이터를 쌓고, 가장 먼저 온 주문부터 처리

 

 

- 해시 테이블

개발을 할 때 프로그램 속도를 어떻게 하면 더 빠르게 할지 고민하는데 자료구조와 알고리즘을 공부하면 도움이 된다.

해시 테이블을 통해 프로그램을 더 빠르게 만들 수 있다.

menu = {
	{ name: '아메리카노', price: 10 },
	{ name: '라떼', price: 15 }
}

 

배열의 데이터를 모두 확인(선형 검색) 해야 한다.

이 방법은 오래 걸린다. 이런 경우 해시테이블이 등장하여 선형 검색할 때보다 빠르게 알아낼 수 있다.

 

해시 테이블로 저장한 메뉴

menu = {
	아메리카노: 10,
	라떼: 15
}

라떼 가격을 알고 싶다면 모든 데이터를 다 찾는 게 아니라 '라떼' 를 검색하면 된다. 그러면 15가 값으로 나옴

 

배열을 전체 검색할 때와 비교하면 해시 테이블의 시간 복잡도는 얼마나 차이는?

선형 검색의 시간 복잡도는 O(N^2)

해시 테이블의 시간 복잡도는 O(1)이다. Big-O 표기법으로 표현할 수 있는 가장 빠른 상수 시간이다.

어떤 값을 찾더라도 딱 한 단계만 거친다. 데이터를 추가, 삭제할 때도 O(1)이라 검색 외 다른 작업의 효율이 좋다.

 

ex) 대한민국 찾기

contries = {'태국', '그리스', '대한민국'}

태국부터 선행으로 검색

 

해시 테이블로 변화하면

contries = {
	'태국': true,
	'그리스': true,
	'대한민국': true
}

대한민국 바로 검색

 

contries['대한민국'] // true

contries['러시아'] // undefined

 

해시 테이블은 배열 형태 + 해시 함수로 구성되어 있다.

해시 함수는 검색할 때 쓰는 key를 index 0 1 2 3 4 ''' 로 바꿔주는 역할을 한다.

 

해시 충돌의 대처 방법에는 여러 가지가 있는데

그중 한 가지는 같은 인덱스에 또 다른 배열을 넣는 방법이 있다.

 

 

✔ 소감 및 떠오르는 생각

충돌은 언제나 어렵다. 그것을 해결하면 아무것도 아니었다고 느끼게 된다.

 

 

✔ 과제 : 내가 번아웃을 극복하는 방법은?