알고리즘

컴퓨터 공학에서 알고리즘은 문제를 해결하기 위한 절차 또는 계산 과정을 설명하는 단계적인 방법이다. 알고리즘은 주어진 입력에 대해 원하는 출력을 생성하는 명확하고 효율적인 방법을 제공한다. 이 알고리즘은 프로그래밍 언어로 구현되어 컴퓨터에서 실행 될 수 있다.

 

1. 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)👉

• 알고리즘의 성능을 분석하는 데 사용되는 두 가지 주요 개념이다.
• 시간복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간을 분석한다. 일반적으로 Bing O표기법을 사용하여 표현된다. 예를 들어, O(n)은 입력 크기n에 대해 선형 시간 복잡도를 나타낸다.
• 공간 복잡도는 알고리즘이 필요로 하는 메모리 공간의 양을 분석한다. 마찬가지로 Bing O표기법을 사용하여 표현한다.

2. 정렬 알고리즘👉

• 정렬은 주어진 데이터를 특정한 기준에 따라 순서대로 재배열하는 알고리즘이다.
  대표적으로 정렬 알고리즘으로 버블 정렬, 삽입 정렬, 선택 정렬, 퀵 정렬, 병합 정렬, 힙정렬 등이 있다. 각 알고리즘의 동작 원리와 시간 복잡도, 공간 복잡도 등을 알수 있다.
• 버블정렬(Bubble Sort)
  인접한 두 요소를 비교하고 필요한 경우 위치를 교환하는 방식으로 정렬하는 알고리즘
• 삽입정렬(Insertion Sort)
  요소를 하나씩 적절한 위치에 삽입하며 정렬하는 알고리즘
• 선택정렬(Selection Sort)
  주어진 배열에서 최소값을 선택하여 순서대로 정렬하는 알고리즘
• 퀵 정렬(Quick Sort)
  분할 정복 방식으로 작동하는 알고리즘으로 피벗(pivot)을 기준으로 배열을 분할하고 정렬한다.
• 병합 정렬(Merge Sort)
  분할 정복 방식으로 작동하는 알고리즘으로, 배열을 반씩 분할하고 분할된 배열을 합병하여 정렬한다.

3. 그래프 알고리즘👉

• 그래프는 정점과 간선으로 구성도니 자료 구조이다. 그래프 알고리즘은 그래프에서 탐색, 최단 경로, 신장 트리 등을 다룬다. 대표적으로 그래프 알고리즘으로는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS), 다익스트라 알고리즘, 크루스칼 알고리즘, 프림 알고리즘 등이 있다.
• 너비우선탐색(BFS, Breadth-First Search)
  그래프의 넓은 부분을 우선으로 탐색하는 알고리즘
• 최단 경로 알고리즘
  -다익스트라 알고리즘(Dijkstra Algorithm)
  시작 정점부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘
  -벨만-포드 알고리즘(Bellman-Ford Algorithm)
  음의 가중치가 포함된 그래프에서도 동작하는 최단 경로 알고리즘
  -플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)
  모든 정점 쌍 사이의 최단 경로를 찾는 알고리즘
• 최소 신장 트리 알고리즘
  -프림 알고리즘(Prim's Algorithm)
  가중치가 있는 그래프에서 최소 신장 트리를 찾는 알고리즘
  -크루스칼 알고리즘(Kruskal's Algorithm)
  가중치가 있는 그래프에서 최소 신장 트리를 찾는 알고리즘

4. 동적 계획법(Dynamic Programming)👉

• 동적 계획법은 복잡한 문제를 여러 하위 문제로 나누어 해결하는 기법이다. 이전에 해결한 하위 문제의 결과를 저장하고 재사용함으로써 중복 계산을 피한다. 동적 계획법은 최적 부분 구조와 중복 부분 문제 성질을 가진 문제에 효과적이다.
• 피보나치 수열(Fibonacci Sequence)
  이전의 두 수를 더하여 다음 수를 만들어내는 수열을 재귀적으로 구현한 알고리즘
• 배낭 문제(Knapsack Problem)
  제한된 용량을 가진 배낭에 가치가 있는 물건을 최대한으로 담는 문제를 해결하는 알고리즘
• 최장 공통 부분 수열(LCS, Longest Common Subsequence)
  두 개의 문자열에서 가장 긴 공통 부분 수열을 찾는 알고리즘

5. 탐욕 알고리즘(Greedy Algorithm)👉

• 최적해를 찾기 위해 매 단계에서 가장 좋아보이는 선택을 하는 알고리즘이다. 각 단계에서의 선택은 지역적으로 최적이지만 전체적으로 최적해를 보장하지는 않을 수 있다. 탐욕알고리즘은 일반적으로 다음과 같은 단계를 따른다.
  
  1. 문제를 부분 문제로 분할
  2. 각 부분 문제에 대해 가장 좋아보이는 선택을 한다.
  3. 선택한 해를 현재 해에 추가한다.
  4. 제약 조건을 확인하고, 만족하지 않는 경우 해당 선택을 취소하고 다른 선택을 시도
  5. 모든 부분 문제가 해결될 때까지 위 과정을 반복
• 탐욕 알고리즘은 단계별로 최적의 선택을 하는 경향이 있기 때문에 구현이 비교적 간단하며 실행 속도가 빠를 수 있다. 그러나 최적해를 보장하지 않기 때문에 문제에 따라 올바른 결과를 얻지 못할 수도 있다.