• 깊이 우선 탐색(Depth First Search)
  • 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
  • 재귀함수를 기반으로 순환 알고리즘의 형태를 지님.
    
• 너비 우선 탐색(Breath First Search)
  • 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
  • 재귀함수로 동작하지 않는다.
  • 큐를 사용하여 효율적으로 구현 가능하다.

스택과 큐는 선형구조로 분류되는 자료구조 중 대표적인 예시이다.

처음엔 무식하게 2중 for문으로 돌려보았다.
맞겠지 싶었는데 시간초과가 떴다.

최대 힙 트리나 최소 힙 트리를 구현해 정렬하는 방법이다.

트리 구조로 보여주는 움짤을 찾아보려 했으나 귀찮았다.

퀵소트와 마찬가지로 분할정복 알고리즘이다.
재귀함수를 이용해 배열을 절반으로 잘라가며 분할하고 정복한다.

분할 정복 알고리즘의 대표적인 예시이며 피봇을 기준으로 정렬해 나가는 정렬 방법이다.

배열의 모든 요소를 앞에서부터 이미 정렬된 배열과 비교하여 적절한 위치를 찾는 정렬 방법이다.

인접한 두 원소를 비교하며 정렬하는 방법이다.
학기 초에 자주 접해서 익숙하다.

위 움짤은 마약같다.

주어진 배열에서 가장 작은 숫자를 앞으로 옮겨가며 정렬하는 방법이다.

이전의 반도체 설계 문제와 동일하게 최장 증가 수열을 구하는 문제다.

2020년 4원 7일 포스트 수정

저 문제 풀 때는 dp가 뭔지도 몰랐다.
이번엔 동적 계획법으로 풀어봤다.
dp[i]에 arr[i]이전의 값들을 비교하며 arr[i]보다 작은 값이 있다면 그 때의 dp[]에 담겨있는 값 + 1을 dp[i]에 넣는다. arr[i]이전의 모든 수에 위 과정을 반복했을 때 가장 큰 수가 dp[i]가 된다.
마지막으로 dp[]에 담겨있는 값 중 가장 큰 값이 최장증가수열의 길이가 된다.