알고리즘 시작: 개념, 마인드

윤뿔소·2022년 12월 9일
algorithm마인드복잡도
0

Algorithm

목록 보기
1/13
post-thumbnail

알고리즘을 풀기 전 알아야할 개념들을 모아놓았다.

알고리즘이란?

어떤 문제를 해결하기 위해서 일련의 절차를 정의하고, 공식화한 형태로 표현한 일종의 문제의 풀이 방법, 해(解)

다시 말해 '프로그래밍에서는 input 값을 통해 output 값을 얻기 위한 계산 과정'이다.

예시

일상생활에도 알고리즘이 적용할 수 있다.

횡단보도 옆에 신호등이 있습니다. 현재는 빨간불이지만 5분 뒤에는 초록불로 바뀔 것입니다.
5분이 지나고, 초록불로 바뀐 신호등은 10초 뒤 ‘30’이라는 숫자와 함께 1초에 한 번씩 점등하기 시작합니다.
총 30번을 점등한 신호등은 이어 빨간불로 바뀝니다.

  • 입력(Input) : 알고리즘은 출력에 필요한 자료를 입력받을 수 있어야 합니다. 이 상황에서는 제일 먼저 빨간불인 신호등이 초록불이 되려면 5분이라는 시간을 입력 받아야 합니다. 하나 더 알아야 할 것은 신호등은 항상 시간을 입력받아야 알고리즘이 동작하지만 꼭 입력을 받지 않아도 되는 알고리즘도 있습니다. (ex. 원주율(pi)의 1조 번째 자리 수를 구하려는 경우 입력은 없지만 출력은 있다.)

  • 출력(Output) : 알고리즘은 실행이 되면 적어도 한 가지 이상의 결과를 반드시 출력해야 합니다. 만약 알고리즘에 출력이 없다면 이 알고리즘은 끝이 났는지, 끝이 나지 않았는지 확인할 길이 없기 때문입니다. 출력은 알고리즘에서 “끝이 났다" 라는 표현이므로 반드시 존재해야 하며, 이는 유한성과도 연관이 있습니다. 이 상황에서 출력은 “초록불로 바뀐다" 입니다.

  • 유한성(Finiteness) : 알고리즘은 유한한 명령어를 수행한 후, 유한한 시간 내에 종료해야 합니다. 이는 알고리즘은 실행된 후에는 반드시 종료되어야 한다는 말과도 같습니다. 알고리즘이 무한히 실행이 된다면 무한히 기다려야 할 것이며, 그것은 출력의 기약이 없는 알고리즘일 것입니다. 신호등이 빨간불인 상태에서 초록불로 변하는 과정에 대한 기약이 없다면 그 신호등은 제대로 된 알고리즘으로 동작하는 것이 아닐 것입니다.

  • 명확성(Definiteness) : 알고리즘의 각 단계는 단순하고 명확해야 하며, 모호해서는 안 됩니다. 예를 들어 ‘신호등이 몇 분 뒤에 켜집니다’ 와 같이 표현한다면, 명확성이 떨어질 뿐더러 모호한 표현이라고 볼 수 있습니다. ‘신호등이 5분 뒤에 켜집니다‘ 와 같이 명확하게 표현을 해야만 합니다.

  • 효율성(Efficiency) : 알고리즘은 가능한 한 효율적이어야 합니다. 모든 과정은 명백하게 실행 가능해야 하며, 실행 가능성이 떨어지는 알고리즘은 효율적이지 못한 알고리즘이라 볼 수 있습니다. 알고리즘은 시간 복잡도와 공간 복잡도를 통해 결정이 되므로, 시간 복잡도와 공간 복잡도가 낮을 수록 효율적인 알고리즘이라 볼 수 있습니다.

이와 같이 일상생활에도 접목되어있는데 계산기 등 무언갈 결과낼 때 사용하는 모든 것이 알고리즘에 의해 결론지어진다. 즉, 정확하지 않은 알고리즘은 정확하지 않은 해(解)를 내놓게 된다. 정확하지 않은 답은 혼란을 주고, 프로그래밍 자체에 큰 문제를 야기하기에 꼭 알맞은 알고리즘을 적재적소에 배치하자.

어떻게, 왜 풀까?

문제를 이해하세요.

  • 대부분의 코딩 테스트에서는 문제의 설명과 입출력예시, 제한사항, 그리고 주의사항 등으로 문제 상황을 제시합니다. 주어진 조건을 토대로 문제가 무엇인지를 이해하는 것부터 시작해야 합니다.

문제를 어떻게 해결할 수 있을지, 전략을 세워야 합니다.

  • 연습장에 전체적인 그림을 그려가면서 페어와 나눠보세요. 전체적인 흐름을 공유할 수 있습니다.
  • 수도코드를 작성하기 전, 인간의 사고로 문제를 해결할 수 있어야 합니다. 연습장이나 온라인 화이트보드를 사용하여 문제에 대해 논의하고, 해결하세요.
  • 코드를 작성하기 전에 페어와 수도코드를 먼저 작성해주세요! 알고리즘 전략은 잘 짜여진 수도코드에서부터 시작합니다!
  • ⭐️막혔던 생각이 페어에게 설명을 하면서 해결되는 경우도 있습니다.
    (이거 리얼임, 내가 이런 케이스, 그래서 혼자 걍 설명하며 답을 구할 때가 많음)

문제를 코드로 옮겨 보세요.

  • 페어와 논의한 전략을 코드로 옮겨 보세요!
  • 구현한 코드를 페어와 논의해 보고, 구현한 코드의 최적화를 시도해 보세요!

알고리즘 테스트에 통과하기 위해 공부하는 것도 좋지만 제일 핵심은 새로운 문제에 봉착했을 때, 전략과 알고리즘을 구상하여 실제로 코드로 구현해 보는 경험은 매우 중요하다! 그래서 알고리즘을 공부하는 것!

복잡도

이것보다 더 효율적인 방법은 없을까? 또는 이게 제일 좋은 방법이 맞나? 를 추구하기 위해 잡아놓은 방법론과 단위

시간 복잡도(Time Complexity)

Big-O 표기법

먼저 복잡도를 나타내는 단위를 알아야할 필요가 있다.
3가지가 있는데

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

그 중 빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문에 빅-오를 많이 해서 빅-오에 대해 알아보자

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?를 표기하는 방법

O(1)

constant complexity, 입력값이 증가하더라도 시간이 늘어나지 않음

function O_1_algorithm(arr, index) {
	return arr[index];
}

let arr = [1, 2, 3, 4, 5];
let index = 1;
let result = O_1_algorithm(arr, index);
console.log(result); // 2

O(n)

linear complexity, 입력값이 증가함에 따라 시간 또한 '같은 비율'로 증가하는 것

기본적인 반복문을 예로 들 수 있다.

function O_n_algorithm(n) {
	for (let i = 0; i < n; i++) {
	// do something for 1 second
	}
}

function another_O_n_algorithm(n) {
	for (let i = 0; i < 2n; i++) {
	// do something for 1 second
	}
}

참고: O(2n)은 없나요?

위 코드의 함수 another_O_n_algorithm은 입력값이 1 증가할때마다 코드의 실행 시간이 2초씩 증가한다. 그러면 O(2n)이라고 쓸 수 있다. 하지만 Big-O 표기법으로는 O(n)으로 표기한다.
왜냐면 입력값이 커지면 커질수록 계수(n 앞에 있는 수)의 의미(영향력)가 점점 퇴색되기 때문에, 같은 비율로 증가하고 있다면 2배가 아닌 5배, 10배로 증가하더라도 O(n)으로 표기해야돼서!

O(log n)

logarithmic complexity, O(1) 다음으로 빠른 시간 복잡도

이진탐색의 시간복잡도라 생각하면 된다.

  1. 1~100 중 하나의 숫자를 플레이어1이 고른다 (30을 골랐다고 가정합니다).
  2. 50(가운데) 숫자를 제시하면 50보다 작으므로 down을 외친다.
  3. 1~50중의 하나의 숫자이므로 또다시 경우의 수를 절반으로 줄이기 위해 25를 제시한다.
  4. 25보다 크므로 up을 외친다.
  5. 경우의 수를 계속 절반으로 줄여나가며 정답을 찾는다.

결과적으로 7번이면 원하는 숫자를 찾아낼 수 있게 된다.
매번 숫자를 제시할 때마다 경우의 수가 절반이 줄어들기 때문에 이진 탐색은 O(log n)의 시간 복잡도를 가진 탐색기법이다.

O(n^2)

quadratic complexity, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것

다중 반복문에서 나오는 시간 복잡도이다.

function O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
		// do something for 1 second
		}
	}
}

function another_O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			for (let k = 0; k < n; k++) {
			// do something for 1 second
			}
		}
	}
}

여기서도 O(2n)에서 했듯이 n^3, O^4, ... 에도 똑같이 O(n^2)로 표기한다.

O(2^n)

exponential complexity, 가장 느린 시간 복잡도

O(2^n)에겐 미안하지만 가장 쓰레기인, 피해야하는 시간복잡도이다. 재귀+피보나치에서 많이 보이는 시간복잡도이다.

function fibonacci(n) {
	if (n <= 1) {
		return 1;
	}
	return fibonacci(n - 1) + fibonacci(n - 2);
}

n이 100 이상이면 평생 결과를 반환받지 못할 수도 있다..

결론

그렇다고 시간복잡도가 많이 걸린다고 표현법을 버리거나 그러지는 말고 입력 데이터가 작다면 시간복잡도를 덜 신경 쓰고, 크다면 더 신경 쓰는 등 입력 데이터를 계산하는 프로그램에 맞춰 결국 완성시키는 것이 중요하다.
그러기위해 시간 복잡도를 어림잡아 예측해 보는 것은 중요하다!

대략적인 데이터 크기에 따른 권장 시간복잡도는 아래와 같다.

데이터 크기 제한예상되는시간 복잡도
n ≤ 1,000,000O(n) or O (log n)
n ≤ 10,000O(n^2)
n ≤ 500O(n^3)

정답은 아니지만 문제 해결과 완성이 주라면 이렇게 하면 좋다! 물론 구현할 때는 복잡도를 최대한 줄이는 것이 효율적이겠지?

공간 복잡도(Space Complexity)

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

메모리라는 고정적 환경, 가변적 환경 속에서 처리할 데이터의 양에 따라 다르게 요구되는 공간으로서 프로그램의 성능에 큰 영향을 주기에 공간복잡도도 신경쓰면 좋다.

하지만 시간 복잡도보다 중요성이 떨어진다. 왜냐하면 시간이 적으면서 메모리까지 지수적으로 증가하는 경우는 거의 없으며 시간 내에 발생하는 메모리 문제들은 보통 알고리즘을 구현할 때에 발생하는 문제이기도 하고, 시간 복잡도에 맞다면 공간 복잡도도 얼추 통과하기 때문에 그렇다.

그래도 때에 따라 공간 복잡도를 중요하게 보는 경우가 있는데, 동적 계획법(Dynamic Programming)과 같은 알고리즘이나 하드웨어 환경이 매우 한정되어 있는 경우가 바로 그 경우다. 동적 계획법은 알고리즘 자체가 구현 시 메모리를 많이 요구하기 때문에 입력 값의 범위가 넓어지면 사용하지 못하는 경우도 많고, 하드웨어 환경이 매우 한정되어 있는 경우(ex. 임베디드, 펌웨어 등)라면 가용 메모리가 제한되어 있기 때문이니까 말이다.

예시: 팩토리얼

function factorial(n) {
	if(n === 1) {
		return n;
	}
	return n*factorial(n-1);
}

함수 factorial은 재귀함수로 구현됐다. 변수 n에 따라 변수 n이 n개가 만들어지게 되며, factorial 함수를 재귀함수로 1까지 호출할 경우 n부터 1까지 스택에 쌓이게 된다. 따라서 해당 함수의 공간 복잡도는 O(n)이라 볼 수 있다.

구현하기

그렇다면 구현을 어떻게 해야할까?

알고리즘 문제를 푼다는 것은, 내가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환하여 코드로 구현한다는 것

  • 데이터를 정렬할 수 있는가?
  • 데이터를 효율적으로 탐색할 수 있는가?
  • 데이터를 조합할 수 있는가? ...etc

즉, 이러한 문제 해결을 위해 얼마나 빨리, 효율적으로 하는 지 보기 위해 알고리즘 구현 문제를 내는 것이다. 특히 본인이 선택한 프로그래밍 언어의 문법을 정확히 알고 있어야 하며, 문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하기 위한 목표로 두는 것을 구현 문제, 구현 유형이라고 통칭한다.

다양한 알고리즘 구현 주제들이 있고, 외워서 할 수 있지만 그리디, 완전 탐색(Brute Force, 재귀, 순열, DFS/BFS 등), 시뮬레이션, DP 등이 있다.
이러한 특성을 알고 어떤 식으로 문제를 접근해야하는지가 반 코드 작성이 반이니 꼭 잘 알고 접근하자.

또, 여기 카테고리에선 자주 나오는 알고리즘 자체 개념과 자주 나오는 유형등을 나눠 기술할 것이다.

profile
윤뿔소
코뿔소처럼 저돌적으로
다음 포스트

알고리즘 유형: 완전 탐색(Brute Force)

0개의 댓글