2021.06.12 AM 8 : 51 ~ PM 11: 40
혼자보기 위해서 만든거임.
내가 이해한대로 쓴거기 때문에 그리고 강의자료를 양쪽에 나누어 저장중임
모르겠으면 다른 노트를 더 찾아볼 것
정렬 데이터를 순서대로 나열하는 방법
이진 탐색을 가능하게도 하고 데이터를 조금 더 효율적으로 탐색할 수 있게 만듦!
▶ 버블 정렬(Bubble Sort) : 첫번째 자료와 두번째 자료, 두번째 자료와 세번째 자료 이런식으로
마지막 자료와 마지막 자료를 비교 교환하는 정렬방식
파이썬에서 Swap 두변수 값 교체 하는 방법 a, b = b, a 이렇게만 하면됨.
▶ 선택 정렬 : 말그대로 선택해서 정렬
내부적으로 차례차례 비교하면 이중반복문의 구조를 가지게 됨.
-> -> -> -> ->
1. [4, 6, 2, 9, 1] 1단계에서 최소값을 찾기 위해 모든값을 봐야함
-> -> -> ->
2. [1, 6, 2, 9, 4] 1은 이미 최소값으로 정렬해서 1빼고 봄
-> -> ->
3. [1, 2, 6, 9, 4]
-> -> ->
4. [1, 2, 4, 9, 6]
-> ->
즉 앞에서부터 한개씩 줄어들면서 반복하는 구조를 말함
▶ 삽입 정렬 : 전체에서 하나씩 올바른 위치에 삽입.
필요할 때만 위치를 변경하므로 선택 정렬에 비해 효율적임.
▶ 병합 정렬 : 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 것
즉 두 집합을 합쳐서 정렬
분할 정복(Divide and Conquer) : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
▶ 스택 : 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조.
처음에 넣은건 가장 늦게 가장 나중에 넣은건 가장 빨리 나옴
이런 자료구조를 Last In First Out 이라고 해서 LIFO 라고 부름.
넣은 순서를 쌓아 둠. ex) 컴퓨터 되돌리기 (ctrl + z) 직전 행동을 되돌리고 싶을때 사용하는 기능처럼 사용.
- 스택의 구현
push(data) : 맨 위에 데이터 넣기
pop() : 맨 위의 데이터 뽑기
peek() : 맨 위의 데이터 보기
isEmpty() : 스택이 비었는지 안 비었는지 여부 반환해주기
스택은 데이터를 삭제 삽입을 자주한다. linked list와 유사하게 구현가능
▶ 큐 : 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조
순서대로 처리되어야 하는 일에 필요
ex) 식당 주문에서 먼저 들어온 순서대로 주문 처리 등등
큐는 스택과 다르게 시작과 끝의 노드를 전부 가지고 있어야 하므로
self.head와 self.tail을 가지고 시작함.
▶ 해쉬테이블: 해쉬함수를 사용하여 색인을 버킷이나 슬롯의 배열로 계산
데이터를 다루는 기법중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행
만약, 해쉬 값 혹은 인덱스가 중복되어 충돌이 일어나게 되면 체이닝과 개방 주소법을 통해 해결가능
딕셔너리와 해쉬 테이블이 같다고 보면 됨.
해쉬함수 : 임의의 길이를 갖는 메세지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수.
해쉬테이블의 내부구현은 키를 해쉬 함수를 통해 임의의 값으로 변경한 뒤 배열의 인덱스로 변환하여 해당하는 값데 데이터를 저장
트리 : 우리가 쓰는 컴퓨터 폴더 구조를 트리구조라고 한다
맨 위에 있는 노드를 root라고 함.
▶ 힙 - 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진트리.
항상 최대의 값들이 필요한 연산이 있을 경우 힙을 쓰면됨 !!
힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조.
부모노드의 값이 자식 노드의 값보다 항상 크거나 작도록 해야한다~~
최대의 값을 빠르게 구할 수 있음.
힙은 부모랑 자식만 봅시다 !! 부모가 자식노드보다 모두커야함
힙 개념 강의노트 다시 한번 찾아볼 것 !!!
자료가 방대함 week_4에 있음.
▶ 그래프
1) 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현
2) 인접 리스트(Adjacnecy List) : 링크드 리스트로 그래프의 연결 관계를 표현
노드(Node) : 연결 관계를 가진 각 데이터. 정점(Vertex)라고도 함.
간선(Edge) : 노드 간의 관계를 표시한 선
인접 노드(Adjacent Node) : 간선으로 직접 연결된 노드(또는 정점)
DFS & BFS
DFS : 끝까지 파고드는 것이라, 그래프의 최대 깊이 만큼의 공간을 요구.
따라서 공간을 적게 씀, 그러나 최단 경로 탐색하기가 쉽지 않음
스택을 이용하면 DFS를 재귀 없이 구현 가능.
BFS : 최단경로를 쉽게 찾을 수 있음. 모든 분기되는 수를 다 보고 올 수 있으나
모든 분기되는 수를 다 저장하다보니 공간을 많이 써야하고 모든걸 다 보고 오다보니
시간이 더 오래걸릴 수 있음. 큐 이용
피보나치 수열 - 재귀함수
수학에서 피보나치수는 첫째 및 둘째항이 1이며 그 뒤의 모든 항은 바로 앞 두항의 합인 수열.
ex) Fibo(6) = Fibo(5) + Fibo(4) = 5 + 3 = 8
Fibo(n) = Fibo(n-1) + Fibo(n-2)
'study' 카테고리의 다른 글
| [Python] 기본 개념정리 (0) | 2021.06.21 |
|---|---|
| [항해99] 혼자 알고리즘 공부 끄적끄적 Day 1 (0) | 2021.06.12 |
댓글