2023 상반기/바이오 컴퓨팅

Review of Algorithms2

concho 2023. 3. 22. 16:04

Selection Sort

선택 정렬(Selection Sort)은 간단한 정렬 알고리즘으로, 주어진 배열에서 최소값을 찾아서 정렬된 부분과 교환하는 방식을 이용합니다. 배열에서 최소값을 찾고 시작 위치와 교환하는 과정을 반복하여 전체 배열이 정렬됩니다.

 

선택 정렬 알고리즘의 동작 방식은 다음과 같습니다:

  1. 배열에서 최소값을 찾아 시작 위치와 교환합니다.
  2. 시작 위치를 한 칸씩 오른쪽으로 이동하면서 이전 과정을 반복합니다.

예시:

주어진 배열: [64, 34, 25, 12, 22, 11, 90]

  1. 첫 번째 반복에서 최소값은 11이며, 시작 위치인 64와 교환됩니다. 정렬된 배열: [11, 34, 25, 12, 22, 64, 90]
  2. 두 번째 반복에서 최소값은 12이며, 시작 위치인 34와 교환됩니다. 정렬된 배열: [11, 12, 25, 34, 22, 64, 90]
  3. 세 번째 반복에서 최소값은 22이며, 시작 위치인 25와 교환됩니다. 정렬된 배열: [11, 12, 22, 34, 25, 64, 90]

이런 식으로 계속 반복하면 최종적으로 전체 배열이 오름차순으로 정렬됩니다.

선택 정렬의 시간 복잡도는 O(n^2)입니다. 이는 최악, 평균, 최선의 경우 모두 동일한 복잡도를 갖습니다. 따라서, 큰 데이터셋의 정렬에 사용하기에는 비효율적이지만, 코드가 단순하고 작은 데이터셋의 정렬에는 사용할 수 있습니다.

 

Anti-monotonic Property

Anti-monotonic 속성은 특정 조건에 대한 속성으로, 이 속성을 따르는 경우 일반적인 케이스가 특정 조건을 만족하면, 더 구체적인 케이스도 항상 그 조건을 만족합니다. 반대로, 일반적인 케이스가 특정 조건을 위반하면, 더 구체적인 케이스도 항상 그 조건을 위반합니다.

예시로 "최대 크기의 유전자 집합을 찾아야 하는데, 이 집합은 최소한 두 가지 기능에서 함께 발생해야 한다"고 가정해봅시다. 이 경우, anti-monotonic 속성이 적용되는 이유는 다음과 같습니다.

  1. 만약 일반적인 유전자 집합(예: 유전자 A와 B)이 두 가지 기능에서 함께 발생한다면, 더 구체적인 유전자 집합(예: 유전자 A, B, C)도 항상 두 가지 기능에서 함께 발생합니다. 왜냐하면 구체적인 집합은 일반적인 집합의 모든 요소를 포함하기 때문입니다.
  2. 반대로, 일반적인 유전자 집합이 두 가지 기능에서 함께 발생하지 않는다면, 더 구체적인 유전자 집합도 항상 두 가지 기능에서 함께 발생하지 않습니다. 왜냐하면 더 구체적인 집합이 일반적인 집합의 요소를 포함하므로, 만약 일반적인 집합이 조건을 만족하지 못한다면 구체적인 집합도 만족하지 못할 것이기 때문입니다.

이러한 anti-monotonic 속성은 데이터 마이닝, 패턴 인식, 그래프 이론 등 다양한 분야에서 적용되며, 문제를 효율적으로 해결하는 데 도움이 됩니다.

 

Dynamic Programming

동적 프로그래밍(Dynamic Programming)은 복잡한 문제를 작은 부분 문제로 분해하고, 부분 문제의 해결 결과를 활용하여 최적의 해결책을 찾는 알고리즘 설계 기법입니다. 이 방법은 다음 과정을 포함합니다:

  1. 문제를 재귀적으로 정의하여 부분 문제로 나눕니다.
  2. 선형적 방식으로 해결책을 구축합니다. (부분 문제의 결과를 반복적으로 사용하여 다음 부분 문제를 해결합니다)

동적 프로그래밍의 주요 특징은 다음과 같습니다:

  ▪ 최적화(Optimization): 동적 프로그래밍은 문제의 최적 해결책을 찾는 데 사용됩니다. 문제를 작은 부분 문제로 분해하        고, 이를 조합하여 최적의 결과를 도출할 수 있습니다.

  ▪ 메모이제이션(Memoization): 중간 단계의 부분 문제 결과를 저장하는 기법입니다. 이를 통해 동일한 부분 문제를 반복        적으로 해결하는 것을 방지하여 알고리즘의 효율성을 높입니다.

    동적 프로그래밍의 예시는 다음과 같습니다:

  ▪ 시퀀스 정렬(Sequence Alignment): 두 개 이상의 서열(예: DNA, RNA, 단백질 서열)을 정렬하는 과정에서, 서열의 유사        성을 최대화하기 위해 누락, 삽입, 대체 등의 작업을 수행합니다. 동적 프로그래밍은 이러한 작업을 최소화하여 최적의        정렬을 찾습니다.

  ▪ 이진 탐색 트리(Binary Search Tree): 동적 프로그래밍은 평균 검색 시간을 최소화하는 최적의 이진 탐색 트리를 구축하      는 데 사용됩니다. 부분 문제를 통해 각 노드를 최적의 위치에 배치하여 트리의 균형을 유지하고, 검색 속도를 높입니다.

    이 외에도 동적 프로그래밍은 피보나치 수열, 최장 공통 부분 수열(Longest Common Subsequence), 0-1 배낭 문제            (Knapsack Problem) 등 다양한 문제에서 효율적으로 최적의 해결책을 찾는 데 사용됩니다.

 

ex1)

이 게임은 2개의 돌 더미로 구성되어 있으며, 두 명의 플레이어가 차례로 돌을 가져가는 방식으로 진행됩니다. 간단한 규칙은 다음과 같습니다:

  1. 게임에는 2개의 돌 더미가 있습니다.
  2. 플레이어는 한 번에 다음 중 하나의 동작을 선택하여 수행할 수 있습니다: a) 양 더미 중 하나에서 1개의 돌을 가져옵니다. b) 각 더미에서 1개씩 총 2개의 돌을 가져옵니다.
  3. 마지막 돌을 가져간 플레이어가 게임에서 승리합니다.

위 좌표평면은 시작하는 플레이어가 이기는지 지는지를 표현한 것이다.(만약 돌이(6,5)만큼 있으면 첫번째 플레이어는 y축 돌을 하나 가져가야 이길 수 있다. ) (6,5)에서 (6,4)로의 이동을 의미

 

ex2)