minari1505 / codingtest

Greedy

greedy : 현재 상황에서 지금 당장 좋은 것만 고르는 방법

• 매 순간 가장 좋아보이는 것을 선택. 나중에 끼칠 영향에 대해서는 생각하지 않음 ⇒ 단순히 현재 상황에서 가장 좋아보이는 것만 선택해도 문제가 풀릴 지 생각해야 함 ⇒ HINT : 가장 큰 순서대로, 가장 작은 순서대로
• 정렬 알고리즘과 짝을 이뤄 출제되는 경우가 많음
• 풀이를 위한 최소한의 아이디어를 떠올리고, 그것이 정당한 지 검토할 수 있어야 함.
• 문제 유형을 파악하기 어렵다면, 그리디 알고리즘 의심 ⇒ 해결방법이 없다면, DP or graph 고민해보기

DFS, BFS

DFS : 스택, 재귀 함수 이용

• Depth-First Search, 깊이 우선 탐색
• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로를 탐색하는 알고리즘

동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 스택에 넣고 방문처리
   1. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복 번호가 낮은 순서부터 처리하도록 구현하는 편

BFS : 큐, 큐 자료구조 이용

• 너비 우선 탐색, 큐 자료구조에 기초함
• 가까운 노드부터 탐색하는 알고리즘
• deque 라이브러리를 사용하는 것이 좋음
• 실제 수행시간은 DFS보다 좋음

동작 과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 삽입하고 방문처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 코테에서 탐색문제를 만나면 그래프 형태로 표현한 다음 풀이법을 고민하기

Sorting

정렬

• 데이터를 특정 기준에 따라 순서대로 나열하는 것

선택 정렬(O(N^))

• 데이터가 무작위로 여러 개 있을 때, 가장 작은 데이터를 맨 앞의 데이터와 바꾸고 두번째로 작은 데이터를 앞에서 두번째 데이터와 바꾸는 과정을 반복하는 것.
• ‘가장 작은 것을 선택’한다는 의미에서 선택 정렬

삽입 정렬(O(N^))

• 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 효율적
• 첫 번째 데이터는 그 자리가 맞다고 보고, 두 번째 데이터부터 시작
• 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있음 ⇒ 자기자신보다 작은 데이터를 만나면 그 자리에 삽입되면 됨

퀵 정렬 (평균 : O(NlogN), 최악의 경우 : O(N^))

sorted() : 퀵정렬과 비슷한 병합 정렬을 기반으로 만들어짐 (최악의 경우에도 O(NlogN))

• 선택, 삽입, 퀵 중 제일 많이 사용되는 알고리즘
• pivot이 사용됨 - ‘기준’

1. 피벗 설정
2. 왼쪽에서부터 피벗보다 큰 데이터를 찾음, 오른쪽에서부터 피벗보다 작은 데이터를 찾음
3. 큰 데이터와 작은 데이터의 위치 교환 호어 분할(Hoare Partition)

• 리스트에서 첫번째 데이터를 피벗으로 정함

계수 정렬(평균 O(N), 최악의 경우 O(N+K))

• 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능
  • 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합
  • 실수형 데이터면 계수정렬 x
  • 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효율적
  • 모든 범위를 담을 수 있는 크기의 리스트를 선언해야하기 때문
• 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담음

1. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킴
2. 정렬된 결과를 직접 눈으로 확인하고 싶다면, 리스트의 첫번째 데이터부터 하나씩 그 값만큼 인덱스를 출력하기

이진탐색 (Binary Search)

• 리스트 내에서 데이터를 매우 빠르게 탐색하는 알고리즘
• 배열 내부의 데이터가 정렬되어있어야만 사용할 수 있는 알고리즘
• 탐색 범위를 절반씩 좁혀가며 데이터를 탐색
• 시간복잡도 : O(logN), 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어드므로
• 사용하는 변수 : 시작점, 끝점, 중간점
• ex) 정렬된 10개의 데이터 중 값이 4인 원소 찾기

1. 시작점, 끝점, 중간점 확인 (0, 18, 8), 중간점이 이미 4보다 크므로, 중간점 이후의 값은 확인하지 않음 ⇒ 끝점을 중간점 이전 원소로 옮김 (6), 중간점을 옮김 (2)
2. 중간점보다 찾으려는 값이 크므로, 중간점 이하를 버림 ⇒ 시작점을 [2] (4)로 변경, 중간점을 [2]로 변경(2~3 사이 = 2.5, 소수점 이하를 버림 ⇒ [2])
3. 중간점에 위치한 데이터 4는 찾으려는 데이터와 동일. 탐색 종료