Algorithm의 개념1

목차

 

 

 

 

 

📌  Algorithm의 개념

 

 

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

 

 

📍시간 복잡도

 

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

 

효율적인 알고리즘 구현 👉🏻👉🏻 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘

 

 

🔗 Big-O 표기법

 

시간 복잡도를 표기하는 방법

 

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

 

각각 최악, 최선, 중간(평균)의 경우를 대하여 나타내는 방법, Big-O표기법이 가장 자주 사용

Big-O표기법 👉🏻👉🏻 최악을 고려 "최소한 특정 시간 이상이 걸린다" , "이 정도 시간까지 걸릴 수 있다"

 

 

O(1)

 

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

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, 입력값이 증가함에 따라 시간 또는 같은 비율로 증가하는 것을 의미

 

Ex) 입력값 :  1 👉🏻 1초

      입력값 : 100배 👉🏻 1초의 100배 👉🏻 100초가 걸리는 알고리즘 👉🏻👉🏻 시간복잡도를 가진 알고리즘이다.

 

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)이 아니라 O(n)이다. 몇배가 증가해도 n은 n이다.

 

 

O(log n)

 

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

 

 

O(n의 2승)

 

quadratic complexity, n의 제곱수의 비율로 증가하는 것을 의미

 

 

Ex) 입력값 :  1 👉🏻 1초

      입력값 : 5  👉🏻 25초가 걸리는 알고리즘 👉🏻👉🏻 시간복잡도를 가진 알고리즘이다.

 

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(n의 2승)

 

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

 

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

 

 

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

 

제한된 시간 내에 반환하는 프로그램을 작성해야하기 때문에 데이터 크기 제한에 따른 시간 복잡도를 예측하는 것이 중요

 

 

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

 

 

 

📍공간 복잡도

 

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

프로그램은 고정적인 공간과 가변적인 공간을 요구하는데 처리할 데이터의 양에 따라 다르게 요구되는 공간인 가변적인 공간이

프로그램 성능에 큰 영향을 준다.

 

공간 복잡도 계산은 시간 복잡도 계산과 비슷하게 Big-O표기법으로 표현한다.

 

// factorial은 재귀함수로 구현
function factorial(n) {
	if(n === 1) {
		return n;
	}
	return n*factorial(n-1);
}
// n 부터 1까지 스택에 쌓이는 구조로 이를 공간 복잡도의 O(n)이다.

 

 

🔗 공간 복잡도의 중요성

 

시간 복잡도의 비해 중요성은 떨어지나, 동적 계획법과 같은 알고리즘이나 하드웨어 환경이 매우 한정된 경우

공간 복잡도를 중요하게 본다. 동적 계획법은 알고리즘 자체가 구현 시 메모리를 많이 요구하기 때문에 입력값의

범위가 넓어지면 사용하지 못하는 경우도 있고, 하드웨어 환경이 한정되어 있는 경우라면 가용 메모리가 제한 되어있기 때문

 

 

 

 

 

📍Greedy Algorithm

 

Greedy는 "탐욕스러운, 욕심 많은" 이란 뜻

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

 

 

탐욕 알고리즘의 특징

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

 

탐욕 알고리즘의 문제 해결 방법

 

거스름돈을 줘야하는 문제라고 가정해서,

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

 

 

 

 

📍 Algorithm구현의 기초

 

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

 

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

 

 

🔗  완전 탐색

 

모든 문제는 완전 탐색으로 풀 수 있다. "답이 무조건 있다."

 

Ex) 양의 정수 1부터 100까지의 임의의 요소가 오름차순으로 하나씩 담긴 배열 중, 원하는 N값을 찾기 위해서는

배열의 첫 요소부터 마지막요소까지 전부 확인한다면 최대 100번의 탐색 끝에 원하는 값을 찾을 수 있다.

 

2가지 규칙으로 생각해 볼 수 있다.

• 첫 번째, 문제를 해결할 수 있는가?
• 두 번째, 효율적으로 동작하는가?

 

완전 탐색으로 문제를 해결한다면, 시간복잡도 즉 두번째 규칙에 만족할 수 없다.

완전 탐색의 방법은 Brute Force(조건/반복을 사용하여 해결), 재귀, 순열, DFS/BFS 등 여러 가지가 있다.

 

 

 

🔗  시뮬레이션

 

모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 유형이다.

 

 

시뮬레이션 예시 - 상하좌우

 

 

https://velog.io/@jehjong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%ED%98%84Implementation-%EC%8B%9C%EB%AE%AC%EB%A0%88%EC%9D%B4%EC%85%98%EA%B3%BC-%EC%99%84%EC%A0%84-%ED%83%90%EC%83%89

 

답안 예시

 

n = int(input())
x, y = 1, 1
plans = input().split()

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
direction = ['L', 'R', 'U', 'D']

for plan in plans:
	for i in range(len(direction)):
		nx = x + dx[i]
		ny = y + dy[i]
	if nx < 1 or ny < 1 or nx > n or ny > n:
		continue
	x, y = nx, ny

print(x, y)

 

 

🔗 Dynamic Programming(DP, 동적 계획법)

 

탐욕 알고리즘, 주어진 문제를 여러 개의 (작은) 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결

하위 문제를 계산한 뒤 그 해결책을 저장하고, 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다.

하나의 문제는 단 한 번만 풀도록 하는 알고리즘이 바로 다이내믹 프로그래밍

 

 

• Overlapping Sub-problems : 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.
• Optimal Substructure : 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다.

 

Overlapping Sub-problems

 

큰 문제로부터 나누어진 작은 문제는 큰 문제를 해결할 때 여러 번 반복해서 사용될 수 있어야 한다.

 

// 대표적인 예시 피보나치 수열
function fib(n) {
	if(n <= 2) {
		return 1;
	};
	return fib(n - 1) + fib(n - 2);
}
// 1, 1, 2, 3, 5, 8...

 

 

Optimal Substructure

 

정답은 최적의 해결 방법을 의미, 작은 문제들의 최적의 해법을 결합하면 결국 전체 문제의 최적의 해법을 구현할 수 있다.

최단 경로를 찾는 문제가 대표적인 예시이다.

 

A → D로 가는 최단 경로 : A → B → C → D

A → C로 가는 최단 경로 : A → B → C (A → B → E → C 가 아닙니다.)

A → B로 가는 최단 경로 : A → B