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

2024. 2. 17. 19:24· Book/IT 5분 잡학사전
목차
  1. ✔ 오늘의 3줄 요약
  2. ✔ 오늘 읽은 범위
  3. ✔ 기억하고 싶은 내용
  4. ✔ 소감 및 떠오르는 생각
  5. ✔ 과제 : 내가 번아웃을 극복하는 방법은?

✔ 오늘의 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 ''' 로 바꿔주는 역할을 한다.

 

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

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

 

 

✔ 소감 및 떠오르는 생각

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

 

 

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

 

반응형

'Book > IT 5분 잡학사전' 카테고리의 다른 글

[IT 5분 잡학사전] Day11, github 업로드  (0) 2024.02.19
[IT 5분 잡학사전 - 컴퓨터 공학 편 2] DAY 10, EP.30 ~ EP.34  (2) 2024.02.18
[IT 5분 잡학사전] Day8, Quiz 2  (1) 2024.02.16
[IT 5분 잡학사전 - 컴퓨터 공학 편] DAY7, EP.22 ~ EP.25  (2) 2024.02.16
[IT 5분 잡학사전 - 웹 기술 편] DAY6, EP.16 ~ EP.21  (5) 2024.02.15
  1. ✔ 오늘의 3줄 요약
  2. ✔ 오늘 읽은 범위
  3. ✔ 기억하고 싶은 내용
  4. ✔ 소감 및 떠오르는 생각
  5. ✔ 과제 : 내가 번아웃을 극복하는 방법은?
'Book/IT 5분 잡학사전' 카테고리의 다른 글
  • [IT 5분 잡학사전] Day11, github 업로드
  • [IT 5분 잡학사전 - 컴퓨터 공학 편 2] DAY 10, EP.30 ~ EP.34
  • [IT 5분 잡학사전] Day8, Quiz 2
  • [IT 5분 잡학사전 - 컴퓨터 공학 편] DAY7, EP.22 ~ EP.25
South Dev
South Dev
개발이 그대를 속일지라도 Get Shit Done.
South Dev
개발이 그대를 속일지라도
South Dev
전체
오늘
어제
  • 전체보기 (38)
    • 작업 🎢 (5)
      • 웹 프로젝트 (5)
      • 영상음악 (0)
      • 100억 이상의 정보 (0)
    • STUDY 📒 (17)
      • React (3)
      • Javascript (5)
      • CSS & SCSS & SASS (3)
      • Web Design (0)
      • git & github (4)
      • 정보처리기사 (0)
      • npm (2)
    • Book (13)
      • IT 5분 잡학사전 (13)
    • MUSIC 🎶 (1)
      • Bossa nova (1)
    • 기타 🎠 (1)
      • YOUTUBE (1)

블로그 메뉴

  • ⚪깃허브
  • ✏ 글 작성
  • ⚙ 관리자 페이지
  • 서치 콘솔
  • 방명록
  • 태그

인기 글

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
South Dev
[IT 5분 잡학사전 - 컴퓨터 공학 편] DAY9, EP.26 ~ EP.29
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.