Time Complexity & Greedy & Brute Force

⭐ 시간 복잡도 (Time Complexity)

• 보다 효율적인 방법 탐색 = 시간복잡도 탐색
• 문제를 해결하기 위한 알고리즘의 로직을 코드로 구현 시, 시간복잡도를 고려한다는건 무슨 의미일까?
• 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼만큼 걸리는가?
• 효율적인 알고리즘을 구현한다는 것 = 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘 구성

 

 

📌 시간 표기법 

• Big-O(빅-오)
• Big-Ω(빅-오메가)
• Big-θ(빅-세타)

위 3가지 표기법은 시간복잡도를 각각 최악,최선,중간(평균)의 경우에 대해 나타내는 방법임

Big-O 표기법

 

 

📌 시간복잡도가 O(1) 인 경우  

• O(1)은 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않음.
• 입력값의 크기와 관계없이 즉시 출력값을 얻어낼 수 있다는 의미임
• 예를들어 arr의 길이가 100만이라고 해도, 즉시 해당 index에 접근해 값 반환 가능
  
  

입력값의 크기가 아무리 커져도 즉시 출력값을 얻어낼 수 있는 O(1) 알고리즘 예시

 

 

📌 시간복잡도가 O(n) 인 경우

• linear complexity라고 하며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가함
• 예를들어 입력값이 1일때 1초의 시간이 걸리고,
  입력값을 100배 증가시켰을때 100초가 걸리는 알고리즘을 구현했다면,
  그 알고리즘은 O(n)의 시간 복잡도를 가진다고 할 수 있음.
  
  

첫번째 함수에선 입력값(n)이 1 증가할때마다 코드 실행시간이 1초씩 증가함
두번째 함수는 입력값이 1 증가할때마다 코드 실행시간이 2초씩 증가하므로 이 알고리즘은 O(2n) 이라고 표현할 수 있음

 

 

 

📌 시간복잡도가 O(log n) 인 경우

• logarithmic complexity라고 하며, Big-O 표기법중 O(1) 다음으로 빠른 시간복잡도를 가진다
• 자료구조에서 배웠던 BST에선 원하는 값을 탐색할때, 노드를 이동할때마다 경우의 수가 절반으로 계속 줄어듬.
  BST의 값 탐색과 같은 로직으로 O(log n)의 시간복잡도를 가진 알고리즘(탐색기법) 임

 

 

📌 시간복잡도가 O(n^2) 일 경우

• quadratic complexity라고 하며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가
• 예를들어 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주니 25초가 걸리게 된다면
  이 알고리즘의 시간복잡도는 O(n^2)라고 표현함
  
  

2n, 5n을 모두 O(n)이라고 표현하는 것 처럼, n^3과 n^5도 모두 O((n^2)로 표기함. n이 커질수록 지수가 주는 영향력이 점점 퇴색됨

 

 

 

📌 시간복잡도가 O(2^n) 일 경우

• exponential complexity라고 하며, Big-O표기법 중 가장 느린 시간복잡도를 가짐

재귀로 구현한 fibonazzi 수열은 O(2^n)의 시간 복잡도를 가진 대표적인 알고리즘임.

 

 

 

📌 Advanced

• 일반적으로 알고리즘 테스트 시, 정확한 값을 제한된 시간내에 반환하는 프로그램을 작성해야함
• 시간제한과 주어진 데이터 크기제한에 따른 시간복잡도를 예측을 잘 해야함
• 예를 들어 입력으로 주어지는 데이터에는 n만큼의 크기를 가지는 데이터가 있고,
  n이 1,000,000보다 작은 수일 때
  O(n) 혹은 O(nlogn)의 시간 복잡도를 가지도록 예측하여 프로그램을 작성할 수 있음

 

n^2의 시간 복잡도를 예측할 수 없는 이유는 실제 수를 대입해 계산해보면 유추할 수 있음.

1,000,000^2은 즉시 처리하기에 무리가 있는 숫자이다.
(1,000,000 * 1,000,000 = 1,000,000,000,000) 만약 n ≤ 500 으로 입력이 제한된 경우에는
O(n^3)의 시간 복잡도를 가질 수 있다고 예측할 수 있음.

O(n^3)의 시간 복잡도를 가지는 프로그램을 작성한다면 문제를 금방 풀 수 있을 텐데,
시간 복잡도를 O(log n)까지 줄이기 위해 노력할 필요는 없다.

따라서, 입력 데이터가 클 때는 O(n) 혹은 O(log n)의 시간 복잡도를 만족할 수 있도록
예측해서 문제를 풀어야 함.
그리고 주어진 데이터가 작을 때는 시간 복잡도가 크더라도 문제를 풀어내는 것에 집중하자

 

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

---

종합적인 시간복잡도 학습성과 질의

• 가장 빠른/느린 시간 복잡도는 무엇일까?
  ↓ 내려갈수록 속도 Down
  
  1. O(1) - constant complexity
  - 제일 빠른 시간복잡도, 입력값이 아무리 커져도 즉시 출력값을 얻는다
  
  2. O(log n) - logarithmic complexity
  - O(1) 다음으로 빠른 시간복잡도를 가짐
  - O(n)보다 항상 빠른가? 답: 항상 빠른건 아님 why? n이 점점 커질수록
  
  3. O(n) - linear complexity
  - 입력값과 시간이 같은비율로 증가함
  
  4. O(n^2) - quadratic complexity
  - 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주면 25초가 걸리게 된다 즉, 5^2와 같은 결과
  
  5. O(2^n) - exponential complexity
  - 가장 느린 시간복잡도를 가짐
  
  
  
  
• 효율적인 알고리즘을 구성했다 함은 무엇을 의미할까요?
  - 시간의 비율을 최소화한 알고리즘 구현
  
  
• 시간 복잡도는 A와 B의 비례함이 어느 정도인지를 나타냅니다. A와 B는 무엇일까요?
  A = 입력값
  B = 시간

---

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

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

 

예시)
김코딩은 오늘도 편의점에서 열심히 아르바이트하고 있습니다. 손님으로 온 박해커는 과자와 음료를 하나씩 집어 들었고, 물건 가격은 총 4,040원이 나왔습니다. 박해커는 계산을 하기 위해 5,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로 하여 거슬러 달라고 하였습니다.

1. 선택 절차 : 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택
2. 적절성 검사 : 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사함.
   초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택.
3. 해답 검사 : 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사함. 액수가 부족하면 1번 과정부터 다시 반복

 

마시멜로 실험이란? 지금 마시멜로를 받겠다고 말하면 1개를 받을 수 있지만,
1분을 기다렸다가 받는다면 2개를 받을 수 있다.

greedy는 "현재"에 최선인 선택을 하기 때문에 마시멜로를 당장 받아내어 1개를 받게 되지만, 전체적으로 보게 되면 1분 뒤에 받는 2개가 최적의 선택이 된다.

두가지 조건을 만족하는 특정한 상황이 아니면 최적의 해를 보장하지 못하며,
알고리즘을 적용하려면 문제가 다음의 2가지 조건을 성립해야 함

• 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않음
• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적문제 해결 방법으로 구성

---

📌 Implementation
1. Brute Force(완전탐색 알고리즘)
2. Binary Search(이진탐색 알고리즘)

 

📌 Brute Force

- 무차별 대입 방법을 나타내는 알고리즘

- 순수 컴퓨팅 성능에 의존하여 모든가능성 시도

- 공간복잡도와 시간복잡도의 요소를 전혀 고려하지 않은, 최악의 시나리오를 감수한 솔루션 탐색 방법

- 크게 2가지 경우에 사용됨

  1. 프로세스 속도를 높이는데 사용할 수 있는 다른 알고리즘이 없을때

  2. 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때

 

📌 Brute Force의 한계

- 문제가 복잡해질수록 기하급수적인 자원을 필요로 하는 비효율적인 알고리즘 (자원 = 시간or시스템자원)

 

 

📌 Brute Force 의 사용처

• 순차 검색 알고리즘 (Sequential Search)
  • 배열 안에 특정 값이 존재하는지 검색할 때 인덱스 0부터 마지막 인덱스까지 차례대로 검색합니다.
• 문열 매칭 알고리즘 (Brute-Force String Matching)
  • 길이가 n인 전체 문자열과 길이가 m인 문자열 패턴을 포함하는지를 검색합니다.
• 선택 정렬 알고리즘
  
  • 전체 배열을 검색하여 현재 요소와 비교하고 컬렉션이 완전히 정렬될 때까지 현재 요소보다 더 작거나 큰 요소(오름차순 또는 내림차순에 따라)를 교환하는 정렬 알고리즘입니다.

• 그 밖의 Brute Force 활용 알고리즘
  • 버블 정렬 알고리즘 - Bubble Sort
  • Tree 자료 구조의 완전탐색 알고리즘 - Exhausive Search (BFS, DFS)
  • 동적 프로그래밍 - DP(Dynamic Programing)

더 공부하면 좋은 키워드

• Brute Force vs Dynamic Programing
• Closet-Pair Problems by Brute Force
• Convex-Hull Problems by Brute Force

 

 

📌 Binary Search

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

 

📌 동작 방식

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

 

Binary Search Algorithm은 대규모의 데이터 검색에 주로 사용합니다.

• 사전 검색
  • 사전에서 단어를 찾을 때 사용합니다.
• 도서관 도서 검색
  • 도서관에서 사용하는 도서 코드로 도서를 검색할 때 사용합니다.
• 대규모 시스템에 대한 리소스 사항 파악
  • 시스템 부하 테스트에서 예측된 부하를 처리하는데 필요한 CPU 양에 대해서 파악할 때 사용합니다.
• 반도체 테스트 프로그램은 디지털, 아날로그 레벨을 측정하는데 Binary Search Algorithm을 사용합니다

 

 

---

📌 pseuducode 작성법 복습 예시
- 자연어 + 프로그래밍 언어의 조합으로 pseuducode 작성