자료구조/알고리즘 - 알고리즘 part1

1.알고리즘(Algorithm)
 -문제를 해결하는 최선의 선택

 -아래의 순서를 생각하며 문제 해결하기
  (1)문제 이해하기(문제 설명, 입출력예시, 제한 및 주의사항 등)
  (2)전략 세우기(의사코드)
  (3)전략을 코드로 구현하기


1-1.의사코드(Pseudocode)
 -프로그래밍 언어로 코드를 작성하기 전에 우리가 쓰는 일상 언어로 프로그램이 작동하는 논리를 먼저 작성하는 것

 -장점
  (1)시간 단축
  (2)디버깅에 용이
  (3)프로그래밍 언어를 모르는 사람과 소통할 수 있음

 -컴퓨터는 단순하게 0과 1로만 이루어져 있는 기계이기 때문에 기초적인 부분부터 구체적이고 상세하게 명령해야함
 -개인의 기호에 맞게 자연어와 프로그래밍 언어를 섞어서 사용하되 자신만의 원칙을 만들어, 일관성이 있으며 다른 사람도 이해할 수 있도록 만드는 것이 중요


1-2.시간 복잡도(Time Complexity)
 -알고리즘 문제를 풀 때 가장 중요한 것은 해답을 찾는 것이지만 그에 못지않게, 얼마나 효율적인 방법으로 해결했는지도 중요함
 -효율적인 방법은 바꾸어 말해 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성하는 것

 -시간 복잡도 표기법
  (1)빅-오(Big-O) : 최악의 경우를 고려하고, 가장 자주 사용됨
  (2)빅-오메가(Big-Ω) : 최선의 경우를 고려
  (3)빅-세타(Big-θ) : 중간(평균)의 경우를 고려

 *Big-O 표기법(입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는지를 표기)
  -O(1) = constant complexity = 입력값이 증가하더라도 시간이 늘어나지 않음
   예)배열을 입력받고, 특정 인덱스의 요소값을 검색하는 경우

  -O(n) = linear complexity = 입력값이 증가함에 따라 시간 또한 같은 비율로 증가

public void O_n_algorithm(int n) {
    for(int i = 0; i < n; i++) {
    // do something for 1 second
    }
}
 
public void another_O_n_algorithm(int n) {
    for(int i = 0; i < n * 2; i++) {
    // do something for 1 second
    }
}

   예)O_n_algorithm 함수 : O(n), another_O_n_algorithm 함수 : O(2n)

  -O(log n) = logarithmic complexity = 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듦
   예)BST에선 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어듦

  -O(n^2) = quadratic complexity = 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가
  
  -O(2^n) = exponential complexity = 입력값이 증가함에 따라 시간이 2를 n번 제곱하는 비율로 증가
   예)재귀로 구현하는 피보나치 수열
 
  +입력 데이터가 클 때는 O(n) 혹은 O(log n)의 시간 복잡도를 만족할 수 있도록 예측해서 문제를 풀고, 주어진 데이터가 작을 때는 시간 복잡도가 크더라도 문제를 풀어내는 것에 집중하는 것이 중요


1-3.탐욕 알고리즘(Greedy)
 -문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식

 -문제 해결 순서
 (1)선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택
 (2)적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사
 (3)해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위 과정을 반복
  
+탐욕 알고리즘을 적용하려면 해결하려는 문제가 다음의 조건을 성립해야함
 (1)탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않음
 (2)최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됨

 +탐욕 알고리즘은 "현재"에 최선인 선택을 하기에 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있음


1-4.완전 탐색 알고리즘(Brute-Force Algorithm, BFA)
 -무차별 대입 방법을 나타내는 알고리즘으로 순수한 컴퓨팅 성능에 의존하여 모든 가능성을 시도하여 문제를 해결하는 방법
 -프로세스 속도를 높이는데 사용할 수 있는 다른 알고리즘이 없거나 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때 사용
 -문제가 복잡해질수록 기하급수적으로 많은 자원(시간, 컴퓨팅 자원)을 필요로 하는 비효율적인 알고리즘이 될 수 있음

 -BFA가 사용되는 곳
  (1)순차 검색 알고리즘(Sequential Search) : 배열 안에 특정 값이 존재하는지 검색할 때 인덱스 0부터 마지막 인덱스까지 차례대로 검색
  (2)문열 매칭 알고리즘(Brute-Force String Matching) : 길이가 n인 전체 문자열과 길이가 m인 문자열 패턴을 포함하는지를 검색
  (3)선택 정렬 알고리즘(Selection Sort) : 전체 배열을 검색하여 현재 요소와 비교하고 컬렉션이 완전히 정렬될 때까지 현재 요소보다 더 작거나 큰 요소(오름차순 또는 내림차순에 따라)를 교환
   *그 밖의 BFA활용 알고리즘(Bubble Sort, Exhausive Search, Dynamic Programming) - 직접 검색해볼 것!

   +더 공부하면 좋은 키워드
      Brute Force vs Dynamic Programing
      Closet-Pair Problems by Brute Force
      Convex-Hull Problems by Brute Force


1-5.이진 탐색 알고리즘(Binary Search Algorithm, BSA)
 -수많은 데이터 중 원하는 데이터를 찾아낼 때 탐색 알고리즘을 활용하는데 탐색 알고리즘은 크게 3가지 Linear Search Algorithm(선형 탐색 알고리즘), Binary Search Algorithm(이진 탐색 알고리즘), Hash Search Algorithm(해시 탐색 알고리즘)로 나뉘고, 셋 중 BSA에 대해 먼저 알아볼 예정

 -BSA는 데이터가 정렬된 상태에서 절반씩 범위를 나눠 분할 정복기법으로 특정한 값을 찾아내는 알고리즘

 -BSA 단계별 동작법
  (1)정렬된 배열의 가장 중간 인덱스를 지정합니다.
  (2)찾으려고 하는 값이 지정한 중간 인덱스의 값이라면 탐색을 종료합니다. 아니라면 3단계로 갑니다.
  (3)찾으려고 하는 값이 중간 인덱스의 값보다 큰 값인지, 작은 값인지 확인합니다.
  (4)값이 있는 부분과 값이 없는 부분으로 분리합니다.
  (5)값이 있는 부분에서 다시 1단계부터 반복합니다.

 -BSA는 정렬된 배열에서 요솟값을 검색할 때 혹은 정렬된 데이터의 양이 많을 때 주로 사용됨
 -탐색을 반복할 때마다 탐색 범위가 절반으로 줄어들기 때문에 시간복잡도는 O(logn)으로 빠른 편이지만 항상 효율이 좋은 것은 아님
  *데이터양이 적고, 앞쪽에 위치한 데이터를 탐색할 때는 Linear Search Algorithm이 빠른 구간이 존재
  **참고로 Linear Search Algorithm은 0번 인덱스부터 순서대로 검색

 +Binay Search Tree(BST)와 핵심은 같지만 BST는 자료구조를 나타내고 BSA는 해결방법을 나타내는것
 +더 공부하면 좋은 키워드들
   Linear Search Algorithm
   Hash Search Algorithm
   Divide-and-conquer algorithm
   Binary Tree vs Binary Search Tree
   Binary Search Algorithm vs Binary Search Tree

 

 

 

이미지 및 내용 출처 - code states