앞에서 본격 코딩 테스트를 위한
예열인 재귀와 자료구조에 대해 공부했었다.
세삼 알고리즘이 왜 어렵고 사람들이 골아파하며
눈물을 훔치는지 이제 알았다.

image

당장 내가 문제를 풀 수 없다는 것은 알고있었는데
이정도의 벽이 있을 줄이야…
웹 개발에 대한 지식을 공부하기전에 쓴맛을 보고간다.
내가할 수 있는 공부를 마치고 알고리즘 공부도
본격적으로 해볼 생각이다.

그때까지 화이팅

오늘은 코딩테스트 준비를 위한
알고리즘방법 및 여러가지 지식들을 쭉 훑어볼 생각이다.
이 지식을 토대로 내일부터 알고리즘 문제를
푸는 시간을 페어와 가질 것 같다.

오늘은 개념 정도만 이해하고 정리하는 수준으로 넘겨야 할 것 같다.


시간 복잡도 (Time Complexity)

image

우리는 문제를 풀다보면 효율적인 방법을 찾기 마련이다.
불필요한 구문은 지워주고 줄일수 있는 코드는 리펙토링을 한다.
시간복잡도를 고려한다는 의미는
입력값에 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?와 같다.

표기법

  • Big-O(빅-오) : 최악을 고려한 표기
  • Big-Ω(빅-오메가) : 최선을 고려한 표기
  • Big-θ(빅-세타) : 중간(편균)을 고려한 표기

우리는 알고리즘을 작성할때 최악의 기준으로 작성을 하는 연습을 하기 때문에
Big-O 표기법을 가장 많이 사용하게 된다.
백준 알고리즘 문제를 풀 경우에도 최악을 가정한 입력값을 주고 문제풀이를 시키는 경우가 많은 것 처럼.

이름 constant logarithmic linear quadratic exponential
표기법 O(1) O(log n) O(n) O(n^2) O(2^n)

<—————작음 (빠름)   시간복잡도 정도   (느림) 큼 —————>

O(1) - constant complexity
입격값의 크기와 관계 없이, 즉시 출력값을 얻어낼 수 있는 정도의
시간 복잡도를 가진 알고리즘을 표기한다.

ex)

int[] arr = new int[]{1,2,3};
int results = test(arr, 0);
System.out.println(results); // 1

입력값이 아무리 커져도 같은 출력값을 얻어낼 수 있다.
즉, 배열의 길이가 수백개가 되더라도 index에 접근해 값을 반환할 수 있다.

O(n)- linear **complexity**
입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.
예를 들어 for문을 쓰는 경우와 같다.

for(int i = 0; i < n; i++) {
// 실행내용
}

n의 수량이 늘어나는 만큼 같은 비율로 시간이 증가한다.

for(int i = 0; i < n; i++) {
// 실행내용
}

for(int j = 0; j < n; j++) {
// 실행내용
}

만약 두개의 for문이 있을 경우에는 O(2n)과 같이 표기한다고 생각할 수도있다.
하지만 Big-O표기법으로는 O(n)으로 동일하게 표현한다.

O(log n) - logarithmic complexity
BST자료 구조에서 배웠던 것과 같다.
경우의 수를 절반씩 줄여가면 탐색하는 알고리즘의 시간복잡도를 표현한다.

O(n^2) - quadratic complexity
입력값이 증가함에 따라 시간이 n의 제곱수의 비율로
증가하는 알고리즘을 표현할때 쓰는 표기법이다.
예를 들어 다중 for문 같은 경우이다.

for(int i = 0; i < n; i++) {
// 실행내용
    for(int j = 0; j < n; j++) {
    // 실행내용
	}
}

n이 증가함에따라 안의 있는 for문까지 제곱의 비율로
늘어나는 것을 볼 수 있다.

O(2^n) - exponential complexity
가장 느린 복잡도를 가지며, 2배씩 늘어나는 특성을 가지고 있다.
피보나치 수열의 재귀와 같은 문제가 이에 해당한다.
해당 함수를 여러번 실행하는 만큼 해당 시간복잡도가 배로되면 늘어나는 셈이기 때문이다.


탐욕 알고리즘 (Greedy)

탐욕 알고리즘은 쉽게 말해 당장 눈앞에 보이는
최적의 상황만을 쫓아 최종적인 해당을 도출해내는 방법이다.
탐욕 알고리즘 작성 단계는 아래와 같이 구분된다.

  • 선택 절차
  • 적절성 검사
  • 해답 검사

탐욕 알고리즘의 조건을 성립하려면 2가지가 있어야한다.

  • 탐욕적 선택 속성 : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
  • 최적 부분 구조 : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

image

탐욕의 알고리즘 예시로는
빵집에서 빵을 고르려는데 담을 수 있는 통의 양은 정해져있고
각기 다른 가격과 무게를 가진 빵들을 고르는 사람의 기준으로
최적으로 담을 수 있도록 문제를 푸는 것을 가장 대표적인 예시로 들고있다.


구현 (Implementation)

알고리즘을 푼다는 것은, 내가 생각한 문제해결과정을
컴퓨터적 사고로 변환하여 코드로 구현하는 것 과 같다.
여러 문제들은 여러 카테고리로 묶여지게된다.

우리는 여러 문제들을 보고 구현하기가 힘들어 지는 경우가 많고
구현 능력을 보는 대표적인 사례로 시뮬레이션과 완전탐색이 있다.

시뮬레이션 (Simulation)

시뮬레이션은 말과 같은 내용이며
모든 과정과 조건이 제시된다. 그 과정을 거친 결과가 무엇인지
확인하는 알고리즘이다.
톱니바퀴 문제같은 유형을 시뮬레이션 알고리즘과 같다고 볼 수 있다.


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

영여로 직역하면 무차별 대입 알고리즘이라는 뜻이다.
즉, 모든 값을 대입하여 문제를 푸는 방법을 얘기한다.
모든 가능성을 시도하여 문제를 해결하는 방법이며
최적의 솔루션이 아니라는 말과 같다고 볼 수 있다.

공간복잡도와 시간복잡도의 요소를 고려하지 않고 최악의 시나리오를
취하더라도 솔류션을 찾으려고하는 방법을 뜻한다.

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

위 의 두가지 경우의 주로 완전 탐색 알고리즘을 사용한다.

주로 사용하는 패턴은

  • 문자열의 패턴의 매칭을 찾을 경우.
  • 선택 정렬 알고리즘의 경우
  • 버블 정렬 알고리즘의 경우
  • Tree 자료 구조의 완전탐색 알고리즘의 경우 (BFS, DFS)
  • 동적 프로그래밍 알고리즘의 경우


이진 탐색 알고리즘 (Binary Search Algorithm)

이진 탐색 알고리즘은 관련성 높은 결과를 정리해두고
원하는 정보를 찾을때 사용하는 알고리즘 방법이다.
이진 탐색 알고리즘과 같이
우리는 탐색을 할때 여러가지 알고리즘을 사용한다.
(선형 탐색 알고리즘, 해시 탐색 알고리즘)

image

가장 간단한 예시로 우리는 8이라는 값을 찾기위해
해당 배열의 중간부터 탐색해볼 수 있다.
이후에 5~9의 중간인 7을 탐색후, 7~9의 중간인 8를 도출 해낼 수 있다.
이렇게 총 3회의 걸쳐 찾을 수 있다.

하지만 위에서 배운 완전탐색으로는 8번의 걸쳐야 찾을 수 있게 되는 것이다.
여기서 알 수 있는 이진탐색알고리즘의 한계가 있다.

  • 배열에서만 구현할 수 있다.
  • 정렬되어 있어야만 구현할 수 있다.
    -> 정렬되어있지 않아 정렬을한다면 이진탐색알고리즘을 사용해도 효율이 높지않다.


오늘은 알고리즘의 대략적인 방법들을 알아보았다.
위의 방법을 어떻게 프로그램으로 구현할 수 있는지는 아직도
어렵고 많은 연습들이 필요할 것 같다.
오늘 공부는 여기서 끝!


오늘의 커피량: ☕️ ☕️ ☕️
오늘의 점심: 삽겹살, 공기밥