CS스터디-1

전재우·2021년 2월 3일

computer science

2021-02-03 첫스터디

이번에 첫스터디로 조원들을 만나서 일주일간 공부 했던 내용을 복습한다는 생각으로 발표를 하였습니다. 첫 스터디라 서로 어색한 분위기가 흘렀지만 서로 발표를 하고 난뒤에 말도 많이하고 좋은 분위기로 흘러갔습니다. 오늘 cs스터디의 진행 방향을 잡아서 다음주는 더 알차게 스터디 시간을 보낼 수 있을것 같습니다. 다음주 주제는 자료구조 입니다.

정렬 알고리즘

알고리즘의 개요

알고리즘이란 "문제를 해결하는 절차"

정렬 알고리즘은 알고리즘 선택의 효울성 차이를 극명하게 보여주는 예이다.

선택 정렬

핵심 아이디어

가장 작은 것을 선택해서 제일 앞으로 보낸다.
문제
1. [ 1 10 5 8 7 6 4 3 2 9 ]
2. [ 1 2 5 8 7 6 4 3 10 9 ] → 2 와 10 교체
3. .........
4. [1 2 3 4 5 6 7 8 9 10 ]
수행시간(시간 복잡도 : O(n^2))
code

버블 정렬

핵심 아이디어

옆에 있는 값과 비교해서 더 작은 값을 앞으로 보낸다.

1번 반복했을때 가장 큰 값이 맨뒤로 가는 결과가 나옴.
문제
1. [ 1 10 5 8 7 6 4 3 2 9 ] → index 1번부터 10까지 탐색
2. [ 1 5 10 8 7 6 4 3 2 9 ]
3. [1 5 8 10 7 6 4 3 2 9 ]
4. [1 5 8 7 6 4 3 2 9 10 ] → 1회 수행 되었을 때의 상태
5. .........
6. [1 2 3 4 5 6 7 8 9 10 ]
수행시간(시간 복잡도 : O(n^2))

등차수열→ N*(N+1) /2

→O(n^2)

선택 정렬보다 느린 이유는 매번 자리수를 교체해줘야해서 선택 정렬보다 실제 실행시간은 더 느리다.
code

삽입 정렬

삽입 정렬은 선택정렬과 버블 정렬 과 다르게 필요할 때만 위치를 바꾼다.

→ O(n^2)중 빠름 선택, 버블 보다 더 빠르다.

→ 데이터가 거의 정렬이 된 경우 어떤 알고리즘보다 더 빠르게 수행된다.
핵심 아이디어

적절한 위치에 삽입 하는 방법, 앞에 있는 원소들이 이미 정렬이 되어 있다고 가정을 하고 진행한다.

정렬이 필요 할 때만 삽입하는 방법
문제
1. [ 1 10 5 8 7 6 4 3 2 9 ] 1, 10은 변경 x
2. [ 1 5 10 8 7 6 4 3 2 9 ] 1, 10 사이에 5가 들어간다.
3. [1 5 8 10 7 6 4 3 2 9 ] 5, 10 사이에 8이 들어간다.
4. [1 5 8 7 10 6 4 3 2 9 ]
5. .........
6. [1 2 3 4 5 6 7 8 9 10 ]
수행시간(시간 복잡도 : O(n^2))
code

퀵 정렬

대표적인 "분할 정복"알고리즘으로 평균 속도가다른 O(N*log N) 정도로 빠르다.
시간 복잡도가 O(nlog n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
추가 메모리 공간을 필요로 하지 않는다.
핵심 아이디어

하나의 큰 문제를 두개의 작은 문제로 분할하는 식으로 빠르게 정렬하는 방식

특정한 값을 기준(피벗(Pivot))으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다.

최악의 경우

→리스트가 계속 불균형하게 나누어 지는 경우 O(n^2) → 이미 정렬된 리스트에 대하여 퀵정렬을 실행했을 경우
문제

[ 3 7 8 1 5 9 6 10 2 4 ][3을 pivot으로 설정] → [왼쪽→ 오른쪽 3보다 큰값을 선택][오른쪽→ 왼쪽 3보다 작은 값을 찾는다] → 찾은 값들을 서로 바꾸어준다.

→[ 3 2 8 1 5 9 6 10 7 4 ] pivot은 3 ,

[ 3 2 1 8 5 9 6 10 7 4 ] 작은 값의 인덱스가 큰 값의 인덱스보다 커서 엇갈린 경우 왼쪽에서 탐색해서온 작은 값과 pivot을 서로 교체 → 즉 pivot이 1이 됨

[1 2 3 8 5 9 6 10 7 4 ] → 3은 정렬이 이루어 졌다고 생각 할 수 있다 이렇게 한번 교체가 되었을때 이전 피벗을 기준으로 좌측은 피벗보다 작고 우측은 피벗보다 크다는 특징이 있다

[1 2 3 8 5 9 6 10 7 4 ] → 1을 피벗값으로 (3보다 작은) 왼쪽과 오른쪽으로 작은 수 큰수를 찾는다 이때 1 ,2로 엇갈린다. →피벗 1 에 1이 교환된다.

[1 2 3 8 5 9 6 10 7 4 ] → 2를 기준으로 또 실행

[1 2 3 8 5 9 6 10 7 4 ]

[1 2 3 8 5 4 6 10 7 9 ] 8보다 큰 9 , 8보다 작은 4

[1 2 3 8 5 4 6 7 10 9 ] 8보다 큰 10 , 8보다 작은 7

[1 2 3 7 5 4 6 8 10 9 ] 7,10으로 엇갈림 발생 → 피벗과 작은값 7 교환

[1 2 3 7 5 4 6 8 10 9 ] 7은 자기보다 큰값을 찾지 못해서 6 이 들어있는 index 다음 값에 포인터가 가있다 → 엇갈려잇다.

[1 2 3 6 5 4 7 8 10 9 ]

.......

[ 1 2 3 4 5 6 7 8 9 10 ]
- 수행시간
- code(중위법)
  
  병합 정렬
  
  대표 적인 분할 정복 방법을 택한 알고리즘 퀵정렬과 동일한 O(nlogn)의 시간 복잡도를 가진다.
  
  다만 퀵정렬은 피벗 값에 따라서 편향되게 분할할 가능성이 있다는 점에서 최악의 경우 O(n^2)이지만
  
  병합 정렬은 정확히 반절씩 나눈다는 점에서 최악의 경우에도 O(nlogn)을 보장한다.
  
  병합 정렬은 퀵정렬과 다르게 피벗 값이 없고 항상 반으로 나눈다는 특징 → logN이 되도록 만들어준다.
- 핵심 아이디어
  
  일단 반으로 나누고 나중에 합쳐서 정렬하자
- 문제
```
[7 6 5 8 3 5 9 1 ]

[6 7 / 5 8  / 3  5 / 1 9 ] → 짝수개로 합치면서 정렬을 해준다.

[5 6  7 8  / 1 3  5 9 ] 

[1 3  5 5 6 7 8 9]

이미 정렬이 되어 있는 상태를 가정하기 때문에 다시 정렬할때 포인터를 이용해 단순 비교를 하면 되기때문에 N의 수행시간밖에 들지 않고 병합을 logN번만 수행 하면 되기 때문에 nlogN의 수행시간이  걸리게 된다.
```
  탐색 알고리즘
  
  BFS(Breath First Search)
  
  너비 우선 탐색은 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘 입니다. 특히나 "맹목적인 탐색"을 하고자 할 때 사용할 수 있는 탐색 기법 입니다. 너비 우선 탐색은 최단 경로를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용한다.
- 핵심 아이디어
  
  루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법
  
  → 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회방법
- BFS가 필요한 경우
  
  두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다
  
  Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 알고자 하는 친구 사이에 존재하는 경로를 찾는 경우
  깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
  너비 우선 탐색의 경우 - 찾고자 하는 친구와 가까운 관계부터 탐색
- 너비 우선 탐색(BFS)의 특징
  직관적이지 않은 면이 있다.
  →BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.
```
BFS는 재귀적으로 동작하지 않는다.
→이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시           검사 해야 한다는 것이다.
→이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.

BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 **큐(Queue)**를 사용한다.
→즉, 선입선출(FIFO) 원칙으로 탐색
→일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.
```
- 시간 복잡도
```
너비 우선 탐색(BFS)의 시간 복잡도

인접 리스트로 표현된 그래프: O(N+E)

인접 행렬로 표현된 그래프: O(N^2)

깊이 우선 탐색(DFS)과 마찬가지로 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph) 의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.
```
  깊이 우선 탐색(DFS, Depth-First Search)
  
  깊이 우선 탐색은 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 특히나 "맹목적인 탐색"을 하고자 할 때 사용할 수 있는 탐색 기법 입니다
- 핵심 아이디어
  
  미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
  
  →즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
- 사용하는 경우
  
  모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
- 구현아이디어
  1. 스택의 최상단 노드를 확인
  2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리, 방문하지 않은 인접 노드가 없으면 최상단 노드를 스택에서 뺀다.
- 깊이 우선 탐색(DFS)의 특징
  자기 자신을 호출하는 순환 알고리즘의 형태 를 가지고 있다.
  전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
  이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다.
  이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
  
  크루스칼 알고리즘(Kruskal Algorithm)
  
  가장 적은 비용으로 모든 노드를 연결 하기 위해 사용하는 알고리즘
  
  → 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘입니다.
  
  →예를 들어 여러개의 도시가 있을 떄 각 도시르 도로로 이용해 연결 하고자 할 때 들어가는 비용을 최소화 하기 위한 알고리즘입니다.
- 그래프 용어
  
  노드 = 정점 = 도시: 그래프에서 동그라미에 해당하는 부분
  
  간선 =거리 = 비용 : 그래프에서 선에 해당하는 부분
  - 그래프 (노드 : 7 , 간선 11)
- 핵심 개념