5/31 (화) 코딩 테스트 준비 - 1️⃣ 알고리즘, 의사코드, 시간복잡도(Big-O)

 

 

 

 

 

코드스테이츠 학습목표

• 알고리즘이 무엇인지 설명할 수 있다.
• 알고리즘 문제를 이해하고 전략을 세울 수 있다.
• 알고리즘 풀이에 필요한 의사 코드를 작성할 수 있다.
• 의사 코드에서 세운 전략을 코드로 구현할 수 있다.
• 내가 구현한 알고리즘을 자바 언어로 설명할 수 있다.

 

 

 

❑ Algorithm

 

 

➤ 알고리즘이 무엇인가?

 

알고리즘은 어떠한 문제를 해결하기 위해 정해진 일련의 절차이다. - 위키백과 -

 

알고리즘은 문제를 해결하기 위한 최선의 선택이다.

 

 

➤ 코딩테스트 푸는 전략

 

시작하기

• 대부분의 코딩테스트는 문제의 설명, 입출력 예시, 제한사항, 주의사항 등으로 문제 상황을 제시
• 조건을 토대로 문제를 이해하는 것부터 시작

 

문제 해결 전략 세우기

• 수도 코드를 작성하기 전 전체적인 그림을 종이에 그려가는 작업이 필요함
• 누군가와 같이 해결해야 한다면 그림을 그려가면서 설명하고 논의해서 해결해야 함
• 코드 작성전에 수도 코드 먼저 작성하기! 수도 코드만 잘 짜도 코딩이 쉽다!

 

 

 

 

❑ 의사코드(pseudoicode)

 

 

➤ 의사코드(pseudocode) 란?

 

프로그래밍 언어로 코드를 작성하기 전에 우리가 쓰는 일상 언어로 프로그램이 작동하는 논리를 먼저 작성하는 것

 

 

➤ 의사코드의 장점

 

1. 시간이 단축된다

코드가 간단하면 수도코드를 작성하는게 더 시간이 걸린다.

하지만 길고 복잡한 코드를 작성할 때는 세세한 부분까지 작성하면서 로직이 기억나지 않을 수 있고 결국 시간이 더 걸리게 된다. 그래서 수도 코드를 먼저 작성하면 수도 코드가 지표가 되어 헤매는 시간이 줄어든다!

 

2. 디버깅이 용이하다

프로그래밍 언어로만 된 코드를 디버깅 할 때 오류가 난 부분이 어느 부분인지 알아보기 힘들다. 하지만 모국어로 된 수도 코드를 보면 해당 부분이 논리적으로 어느 절차인지 쉽게 이해할 수 있다.

 

3. 프로그래밍 언어를 모르는 사람과 소통할 수 있다

수도 코드는 우리의 일상 언어로 쓰여졌기 때문에 프로그래밍 언어를 모르는 사람도 프로그램의 수도코드를 보면 어떤 로직으로 동작하는지 이해할 수 있다.

 

 

➤ 왜 구체적으로 써야 할까?

 

컴퓨터는 사람과 달리 알려주지(배우지) 않은 부분은 스스로 할 수가 없기 때문에 세세한 절차까지 코드로 알려주어야 한다.

그래서 의사 코드를 빈틈없이 작성하면 실제 코드에서 빠트리는 부분이 없게 되어 코드가 문제없이 작동할 수 있다.

 

 

➤ 의사코드 작성법? 올바른 작성?

 

의사코드는 자연어(영어나 한국어처럼 일상에서 쓰는 언어)만 사용해도 되고 프로그램 언어와 섞어서 써도 된다.

협업을 하는 실제 업무에서는 의사코드는 매우 중요하다.

따라서 의사 코드에 대한 내용은 클린코드 ‘4장 주석’ 을 읽으면서 더 깊게 알아갈 필요가 있다.

 

 

---

 

 

❑ 시간 복잡도(Time Complexity)

 

알고리즘에서 시간 복잡도는 Big-O 표기법을 사용해서 비교한다.

 

알고리즘 문제를 풀다보면 해결하는 것 만큼 얼마나 효율적으로 풀었는지도 중요하다.

어떤 알고리즘 문제들은 프로그램 연산에 제한 시간이 있는 경우도 있다.

 

효율적인 방법을 고민한다

= 시간 복잡도를 고민한다

 

 

➤ 시간 복잡도?

 

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

 

알고리즘은 연산이 많아질수록 시간이 오래걸린다.

시간 복잡도는 연산 횟수와 관계있다.

 

 

➤ Big-O

 

• Big-O(빅-오) : 최악의 경우
• Big-Ω(빅-오메가) : 최선의 경우
• Big-θ(빅-세타) : 중간(평균)의 경우

 

주로 빅오(최악의 경우)를 가장 많이 사용한다.

프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다.

“최소한 이 정도 걸린다” 보다는 “이 정도 시간까지 걸릴 수 있다” 를 고려해야 모든 상황에 대응이 가능하기 때문이다.

 

 

➤ Big-O의 수학적 정의와 계산법

 

어떤 함수 f(n)의 Big-O notatino이 O(g(n))이라는 것은

n의 값이 일정 수준을 넘어가면 그 이상의 어떤 n을 대입하여도 c*g(n)보다 결과값이 작은 상수 c가 존재한다는 뜻이다.

 

시간 복잡도는 단위연산(정의, 단순계산, 비교, 출력 등)의 횟수를 기준 함수로 둔다.

 

int result = 0;
for(int i = 1; i <= n; i++) {
	for(int j = 1; j <= i; j++) {
    	result++;
    }
}

 

위 알고리즘의 연산횟수는 1+2+ ... + n 이므로 n(n+1)/2 이다.

단위연산의 수를 T(n)이라 할 때, T(n) = n(n+1)/2 + 2 이다.

빅오 표현법으로 나타내기 위해 적절한 g(n)과 c, n0를 선택한다.

g(n) = n^2, c = 1, n0 = 3 이라고 하면

c * g(n) = n^2 >= T(n)

n*n >= n(n+1)/2 + 2

양 변에 *2 ➡️ 2n*n >= n(n+1) + 2*2

n*n + n*n >= n^2 + n + 4

n^2 >= n + 4

➡️ n0인 3 이상의 모든 수 n에 대하여 T(n)보다 c*g(n)의 값이 크다

따라서 이 알고리즘의 시간복잡도는 O(n^2)이라고 표기한다.

 

 

※ Big-O의 표기법

 

가능한 가장 작은 표기법을 사용한다.

O(n^2)도 되고 O(n)도 된다면 더 작은 O(n)을 사용한다.

가능한 가장 간단하게 표기한다.

O(3n+4)과 같이 쓰지 않고 O(n)으로 쓴다.

 

 

 

➤ 많이 쓰는 Big-O

 

 

O(1) : constant complexity

입력값이 증가해도 시간(연산)이 늘어나지 않는다.

 

O(n) : linear complexity

입력값이 증가하면 시간도 같은 비율로 증가

 

O(log n) : logarithmic complexity

O(1) 다음으로 빠른 시간 복잡도를 가짐

BST(이진 탐색 트리)가 O(log n)의 시간복잡도를 가짐

연산을 할 수록 전체 해야할 연산 수가 줄어들 때이다

 

for(int i = 0; i < n; i++) {
	i *= k;
}

 

예를 들어 i는 연산할 수록 k가 곱해지고 n과 비교한다. 따라서 k*k*k*...(t번 실행 -> k^t) >= n 가 될 때까지 t번 실행하게 된다.

(여기서 증감문의 i++는 신경쓰지 않아도 된다. n이 무수히 커질 수록 +1이나 상수를 곱하는건 근소한 차이이기 때문에 무시해도 되기 때문이다.)

여기서 k^t = n 를 만족하는 t만큼 실행하게 되는 것이다.

t = logk n인 것이다.

따라서 시간 복잡도는 O(logk n) ➡️ O(log n) 이다.

(O(log2 n)이나 O(log3 n)등도 모두 O(log n)으로 표기한다.)

 

 

 

O(n^2) : quadratic complexity

O(n^2)이나 O(n^5) 등도 모두 O(n^2)으로 표기한다.

시간 복잡도가 O(n^2)이 되는 순간 부터 입력값이 커질수록 컴퓨터에 가는 부담이 어마어마 해진다...

여러번 중첩된 for문은(실행수가 입력값에 영향을 받을 때) 가능하다면 피하는 것이 좋다..

 

O(2^n) : exponential complexity

가장 느린 시간 복잡도를 가짐

재귀를 이용한 알고리즘이 보통 O(2^n)의 시간복잡도를 갖는다.

그래서 재귀를 이용하면 코드는 직관적이고 짧아지지만 입력값이 커질수록 실행시간이 엄청 늘어난다.

재귀로 작성한 피보나치 수열을 떠올려보자.

100번 실행하려면....2의 100승을 계산해야 한다...

피보나치는 입력값이 커질 것을 대비하고 싶다면 재귀보다는 배열을 사용해서 이전인덱스와 전전인덱스를 불러오는 것이 효율적이다..

 

 

➤ Big-O는 어떻게 활용할까?

대부분 코딩테스트에서 실행 타임에 제한 시간이 걸려있다.

최대 입력값을 확인하고 시간복잡도를 고려해서 알고리즘을 설계할 수 있는지 확인하는 것이다.

 

입력값이 최대일 때를 항상 고려해서 알고리즘을 설계하면 안정적인 프로그램을 만들 수 있다.

입력값의 최댓값이 많이 크다면 시간 복잡도가 작은 알고리즘으로 작성하는 것이 좋다.

그런데 입력값이 작다면 굳이 시간을 들이고 머리를 굴려가면서 시간 복잡도가 작은 알고리즘을 찾을 필요는 없다.

보통 데이터 크기에 따른 시간복잡도 설계는 이 정도만 해도 된다.

 

n <= 1,000,000 ➡️ O(n) or O(log n)

n <= 10,000 ➡️ O(n^2)

n <= 500 ➡️ O(n^3)

 

 

 

 

---

 

❑ 탐욕 알고리즘(Greedy)

 

말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황을 쫓아 최종적인 해답에 도달하는 방법

매 순간 최적이라 생각되는 해답(locally optimal solution)을 찾고 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식

항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의 근사한 값을 빠르게 도출할 수 있다는 장점이 있음

 

 

➤ 탐욕 알고리즘  해결 방법

 

1. 선택 절차(Selection Procedure)

현재 상태에서의 최적의 해답을 선택

2. 적절성 검사(Feasibility Check)

선택된 해가 문제의 조건을 만족하는지 검사

3. 해답 검사(Solution Check)

원래의 문제가 해결되었는지 검사하고 해결되지 않았다면 선택 절차로 돌아가 위 과정 반복

 

 

➤ 탐욕 알고리즘은 은탄?

 

현재의 최적의 선택이 언제나 최적의 결과를 보장하진 않는다.

탐욕 알고리즘을 사용한 것이 꼭 최적의 결과는 아닌 경우도 있다.

 

ex) 마시멜로 실험 결과

마시멜로를 지금 받으면 1개 1분을 기다렸다가 받으면 2개를 받을 수 있다.

greedy는 현재의 최적의 선택인 지금 1개를 받는 것을 선택하지만

최종적으로는 1분을 기다리고 2개를 받는 것이 최적의 결과이다.

 

 

➤ 탐욕 알고리즘을 적용하기 위한 조건

 

1. 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다

2. 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다

 

 

 

읽어주셔서 감사합니다. 좋은 하루 되시고 도움이 되셨길 바랍니다.

오개념에 대한 지적은 언제나 환영입니다~😍