KTY repository

Algorithm

•
  • Algorithm
 •
  • algorithm
  • codestates
  • time-complexity
  • big-o
  • space-complexity
  • greedy-algorithm
  • dynamic-programming
  • brute-force-algorithm

기본적인 이론도 몰랐던 알고리즘

1. 알고리즘

문제를 해결하는 최선의 선택

9세기 천문학자 al-Khowarizmi에서 유래되었다. 십진법에 의해 산술연산과 제곱근, 원주율을 구하는 방법을 아랍어로 기록했는데, 산술의 해를 구하는 절차를 공식화한 기록이 알고리즘으로 발전했다.

어떤 문제를 해결하기 위해서 일련의 절차를 정의하고, 공시고하한 형태로 표혀현한 일종의 문제의 풀이방법, 해를 의미한다. 프로그래밍에서는 입력값을 통해 출력값을 얻기 위한 계산과정이다.

  • input: 출력에 필요한 자료를 입력받아야한다.
  • output: 출력이 있어야 끝인걸 알 수 있다. 유한성
  • fititeness: 유한한 명령어를 수행, 유한한 시간 내 종료
  • definiteness: 각 단계는 단순하고 명확, 모호하면 안된다.
  • efficiency: 가능한 효율적, 모든 과정은 명백히 실행가능히야된다. 시간복잡도와 공간복잡도를 통해 결정된다. 시간복잡도, 공간 복잡도가 낮을수록 효율적인 알고리즘이다.

연산은 괄호과 가까운 순, 왼쪽에서 오른쪽으로 연산한다. 정확하지 않은 알고리즘은 정확하지 않은 해를 낸다.

2. 시간 복잡도

Time Complexity

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마나 걸리는가?

입력값이 커짐에 따라 증가하는 시간의 비율을 최소하한 알고리즘이 효율적인 알고리즘이다. Big-O로 표기한다.

2.1. Big-O

  • Big-Ω
  • Big-θ
  • Big-O: 최악 -> 입력값의 변화에 따라 연산을 실행할 시, 연산 횟수에 비해 시간이 얼마나 걸리는가를 표기한다.

2.2. O(1)

constant complexity, 입력값이 증가해도 시간이 늘어나지 않는다.

배열의 크기가 무한이라도 index를 통해 바로 접근가능하다.

2.3. O(n)

linearcomplexity, 입력값이 증가함에따라 시간도 같은 비율로 증가한다.

반복문으로 값을 배시간다고하여 O(배수n)이 아닌, O(n)이라고하는 이유는 입력값이 커지더라도 계수의 의미(영향력)가 퇴색되기 때문이다.

2.4. O(log n)

O(log n), logarithmic complexity, Big-O 중 O(1) 다음으로 빠른 시간 복잡도를 가진다.

이진트리의 경우 노드를 이동할때마다 경우의수가 절반으로 줄어든다.

2.5. O(n2)

quadratic complexity, 입력값이 증가하면 시간이 n의 제곱수의 비율로 증가한다.

O(n)과 마찬자기로 반복문안에 반복문을 넣어 반복문수만큼 제곱연산을 하더라도 의미(영향력)가 퇴색되어 O(n2)로 표기한다.

2.6. O(2n)

exponential complexity, 가장 느린 시간복잡도를 가진다.

종이 접으면 두깨는 두배 -> 이방식으로 시간복잡도가 도출되면 다른 접근방식을 고민해야한다.

2.7. 데이터 크기에 따른 시간 복잡도

데이터 크기 제한↔ 예상되는시간 복잡도
n ≤ 1_000_000 O(n) or O(logn)
n ≤ 10_000 O(n2)
n ≤ 500 O(n3

3. 공간 복잡도

Space Complexity

알고리즘이 수행되는데 필요한 메모리의 총량이다. 프로그램이 필요로하는 메모리공간을 산출한다.

시간복잡도가 공간복잡도보다 중요하다. 하지만 동적 계획법(dynamic programming)과 같은 알고리즘이나 하드웨어 환경이 매우 한정되어 있어, 알고리즘 자체가 구현 시 메모리를 많이 요구하여 입력값의 범위가 넓어지면 사용하지 못하는 경우가 있어, 하드웨어 환경이 매우 한정되어있는 임베디드나 펌웨어같은 경우에는 공간복잡도가 중요하다.

4. Greedy Algorithm

탐욕스러운, 욕심많은 탐욕알고리즘은 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.

  1. selection procedure: 현재 상태에서 최적의 해답을 선택
  2. feasibility check: 선택도니 해가 문제의 조건을 만족하는지 검사
  3. solution check: 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 selection procedure로 회기 후 반복

매 순간, 최적의 해답(locally optimal solution)을 찾으며, 이를 토대로 최종문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식이다.

마시멜로 실험
지금 마시멜로 받으면 1개, 1분뒤에 받으면 2개, 1분뒤에 받는 2개가 최적의 선택(원래는 현재에 최선인 당장받아야됨)

  • 특징
    • greedy choice property: 앞의 선택이 이후의 선택에 영향을 주지 않는다.
    • optimal substructure: 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

5. 구현 기초

내가 생각한 문제 해결 과정을 컴퓨터의 사고로 변환하여 코드로 구현하는것이다.

  • 데이터가 정렬가능한가
  • 데이터를 효율적 탐색가능한가
  • 데이터를 조합가능한가
  • 등등

주요 기술 스택을 정확하 일아야 문제의 조건에 전부 부합하는 코드를 작성가능하다.

  • 구현능력 평가
    • brute force: 완전 탐색, 모든 문제는 이 방법으로 풀 수 있으나 답이 무조건 있는 강력함이 있다.
      • 조건: 효율은 만족못하는 경우가 있다.
        1. 문제를 해결가능한가?
        2. 효율적으로 동작하는가?
      • 모든 경우의 수를 탐색하는 모든 경우를 통칭한다
        • brute force: 조건/반복을 사용해 해결
        • 재귀, 순열, DFS/BFS 들
    • simulation: 시뮬레이션, 모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 뭔지 확인하는 유형이다. 로직 그대로 코드로 작성해서 문제해결을 떠올리는건 쉬울 수 있지만, 길고 자세해 코드로 옮기는 작업이 까다롭다.

6. 동적 계획법

Dynamic Programming, 탐욕알고리즘이랑 같이 나오는 알고리즘으로 작은 문제에서 출발하는것이 동일하다. 탐욕알고리즘은 매 순간 최적의 선택을 찾는다면, dp는 모든 경우의 수를 조합회 최적의 해법을 찾는다.

주어진 문제를 여러개의 작은 하위 문제로 나누어 풀고, 하위 문제들의 해결방법을 결합해 최종 문제를 해결한다. 하위 문제계산 후 해결책을 저장하고, 나중 동일한 하위 문제를 만날 시 저장된 해결책을 적용해 계산 횟수를 줄인다. 하나의 문제는 단 한번만 풀도록하는 알고리즘이다.

  • 가정
    1. overlapping sub-problems: 큰문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다. ex) 피보나치 수열
    2. optimal substructure: 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제도 같ㄷ가. 작은 문제에서 구한 정답을 큰 문제에서도 사용한다. ex) 최단 경로를 찾는 문제

7. Brute Force Algorithm

시행착오 방법론, 암호학(Brute Force Attack), 모든 값을 대입하는 방법, 지능형 전략을 사양하지 않는다.

                                       ↓ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㄱ
start -> keyowrd initialization -> data calling -> matching -> buteForce conditions are met? -yes-> print identification result -> end
  • usage
    • 프로세스 속도를 높이는데 사용할 수 있는 알고리즘이 없을때
    • 문제를 해결하는 여러 솔루션이 있고, 각 솔루션을 확인할때

데이터의 범위가 커질수록 비효율적이다.

  • 한계
    • 문제의 복잡도에 매우 민감하다.
    • 현재의 자원이 충분히 커버 가능할때 사용
  • ex
    • 순차 검색 알고리즘: sequential search, 배열안 특정값이 존재하는지?
    • 문자열 매칭 알고리즘: brute-force string matching, 문자열 패턴을 포함하는지?
    • 선택 정렬 알고리즘: selection sort, 전체 배열 검색해 현재 요소와 비교하고, 컬렉션이 완전히 정렬될 때까지 현재 요소보다 더 작거나 큰 요소(오름차운 또는 내림차순에 따라) 교환하는 정렬 알고리즘
    • 버블 정렬 알고리즘: bubble sort
    • 트리자료구조 완전탐색: exhausive search(bfs, dfs)
    • 동적 프로그래밍: dynamic programming
  • keyword
    • Brute Force vs Dynamic Programing
    • Closet-Pair Problems by Brute Force
    • Convex-Hull Problems by Brute Force

참조

codestates