Algorithm(알고리즘) - 2

◎ Greedy Algorithm(탐욕 알고리즘)

• Greedy Algorithm(탐욕 알고리즘)

  • 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법
  • 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식

• 예시

  • 도둑이 다양한 무게와 다양한 가치를 지는 물건들을 훔치는 상황이라 가장
  • 옮길 수 있는 것 중에 가장 비싼 것을 짚고(현재 최적 상황), 이를 n번 반복

• 해결 방법

  • 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택
  • 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사
  • 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복

• 특징

  • 두 가지의 조건을 만족하는 "특정한 상황" 에서만 "최적의 해"를 보장
    • 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않음
    • 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성
  • 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있다.

◎ Implementation(구현)

• 알고리즘 문제를 푼다는 것 == 내가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환하여 코드로 구현한다는 것
• 수많은 문제 해결 과정은 대부분 여러 개의 카테고리로 묶임, 각 카테고리는 원하는 의도가 분명하게 있고, 그것을 해결하는 것이 목표이다.
• 공통적인 사항 : 내가 생각한 로직을 '코드로 구현'한다. 문제 해결을 코드로 풀어낼 때, 정확하고 빠를 수록 구현 능력이 좋다고 말한다.
• 목표 : 본인이 선택한 프로그래밍 언어의 문법을 정확히 알고 있어야 하며, 문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것을 목표로 두는 것

◎ 시뮬레이션

• 시뮬레이션
  • 모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 유형
  • 보통 문제에서 설명해 준 로직 그대로 코드로 작성하면 되어서 문제 해결을 떠올리는 것 자체는 쉬울 수 있으나 길고 자세하여 코드로 옮기는 작업이 까다로울 수 있다.
  • 문제에 대한 이해를 바탕으로 제시하는 조건을 하나도 빠짐없이 처리해야 정답을 받을 수 있다. 하나라도 놓친다면 통과할 수 없게 되고, 길어진 코드 때문에 헷갈릴 수도 있으니 주의해야 한다.

◎ 완전 탐색 알고리즘(Brute-Force Algorithm)

• 완전 탐색 알고리즘(Brute-Force Algorithm, BFA)

  • 무차별 대입 방법을 나타내는 알고리즘
  • 순수한 컴퓨팅 성능에 의존하여 모든 가능성을 시도하여 문제를 해결하는 방법
  • 공간복잡도와 시간복잡도의 요소를 고려하지 않고 최악의 시나리오를 취하더라도 솔루션을 찾으려고 하는 방법

• BFA 사용하는 경우

  • 프로세스 속도를 높이는데 사용할 수 있는 다른 알고리즘이 없을 때
  • 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때

• 한계

  • 문제에 더 적절한 해결 방법을 찾기 전에 시도하는 방법이므로, 데이터의 범위가 커질수록 상당히 비효율적이다.
  • 문제의 복잡도에 매우 민감함 (문제가 복잡해질수록 기하급수적으로 많은 자원을 필요로 할 수 있다)

• 사용하는 곳

  • 순차 검색 알고리즘 (Sequential Search) : 정렬되지 않은 배열 안에 특정값이 존재하는지 검색
    • 인덱스 하나하나마다 특정 값과 일치하는지 확인하여야 함
  • 문열 매칭 알고리즘 (Brute-Force String Matching): 길이가 n인 전체 문자열과 길이가 m인 문자열 패턴을 포함하는지를 검색
    • 길이가 n인 문자열을 맨 앞부터 순회하면서 문자열 패턴이 일치하는 곳이 있는지 판단
  • 선택 정렬 알고리즘 (Selection Sort) : 전체 배열을 검색하여 현재 요소와 비교하고 컬렉션이 완전히 정렬될 때까지 현재 요소보다 더 작거나 큰 요소(오름차순 또는 내림차순에 따라)를 교환하는 알고리즘
    • 전체 배열을 계속 순회하면서 현재 요소와 최소 요소를 비교

    ---

  • 버블 정렬 알고리즘 - Bubble Sort
  • Tree 자료 구조의 완전탐색 알고리즘 - Exhausive Search (BFS, DFS)

◎ 동적 프로그래밍 - DP(Dynamic Programing)

• 동적 프로그래밍 (Dynamic Programing) 알고리즘 기법

  • 이미 계산된 결과(하위 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 설계함으로써 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

• DP 문제가 성립할 조건

  • 최적 부분 구조(Optimal Substructure) : 상위 문제를 하위 문제로 나눌 수 있으며 하위 문제의 답을 모아서 상위 문제를 해결가능
  • 중복되는 부분 문제(Overlapping Subproblem) : 동일한 작은 문제를 반복적으로 해결

• Top-down VS Bottom-up

  • Top-down(하향식)
    • 상위 문제를 해결하기 위해서 하위 문제를 재귀적으로 호출하여 하위 문제를 해결함으로써 상위 문제를 해결하는 방식
    • 해결해놓은 하위 문제를 저장해 놓기 위해 Memoization이 사용

  public class Topdown {
      static int[] dp; // Memoization
      
      public static void main(String[] args) {
          int n = 100;
          dp = new int[n+1];
          System.out.println(fibo(n));
  
      }
  
      // Top-down : 재귀 사용
      static int fibo(int x) {
          if( x ==1 || x==2) return 1;
          if(dp[x] != 0) return dp[x];
          dp[x] = fibo(x-1) + fibo(x-2);
          return dp[x];
      }
  }

  • Bottom-up(상향식)
    • 하위에서부터 문제를 해결해나가면서 먼저 계산했던 문제들의 값을 활용해서 상위 문제를 해결해나가는 방식
    • 여기서 사용되는 문제 결과 값 저장용 리스트는 DP 테이블이라고 부름

  public class Bottomup {
  
      static int[] dp; // DP 테이블
      public static void main(String[] args) {
          int n = 100;
          dp  = new int[n+1];
  
          System.out.println(fibo(n));
      }
  
      // Bottom-up : 반복문 사용
      static int fibo(int x) {
          dp[1] =1;
          dp[2] =1;
          for(int i=3; i<x+1; i++) {
              dp[i] = dp[i-1] + dp[i-2];
          }
          return dp[x];
      }
  }

• 메모제이션 특징

  • 같은 문제를 다시 호출 하면 메모했던 결과를 그대로 가져온다.
  • DP에만 국한된 개념이 아님. 한 번 계산된 결과를 담아 놓기만 하고 DP가 아닌 다른 방식으로도 사용될 수 있다.

• 참고 사이트 : https://loosie.tistory.com/150