알고리즘 Algorithm

알고리즘 정의 & 중요성

"문제 해결"

• '입력된 자료'를 토대로 '원하는 출력' 유도하는 규칙의 집합
• 생각할 수 있는 여러가지 경우의 수 중에 어떤게 상황에 맞는 최선의 알고리즘인지를 찾아내는 능력을 갖춰야 한다
• 좋은 프로그램 = 프로그램을 수행하기 위해 꼭 필요한 자료구조 + 알고리즘
• 컴퓨팅 사고력을 극대화 할 수 있는 것
• "취업"에서 매우 중요한 영역

복잡도

시간 복잡도

• 프로그램의 수행 성능을 최악의 경우를 가정하여 정량화하는 방법
• 문제를 해결하는데 걸리는 시간과 입력의 함수 관계

사례 1

func findMaxNum(_ array: [Int]) -> Int? {
	 for num in array { // array 의 길이만큼 아래 연산이 실행
     	for compareNum in array { // array 의 길이만큼 아래 연산이 실행
        	if num < compareNum { // 비교 연산 1번 실행
            	break
            }
        } else {
        	return num
        }
    }
	return nil
}
let input = [3, 5, 6, 1, 2, 4]
let result = findMaxNum(input)

• array의 원소 갯수 = N
• array의 원소 갯수 array의 원소 갯수 비교 연산 1번 = N * N
• 이 함수는 $N^2$ 만큼의 시간이 걸렸다고 표현 할 수 있다
• Big-O(빅오) 표기법으로 표시하며 이 경우엔 O($N^2$)의 시간 복잡도를 가졌다고 한다

사례 2

func findMaxNum(_ array: [Int[) -> Int? {
	guard let firstNum = array.first esle {
    	return nil
   	}
    var maxNum = firstNum // 연산 1번 실행
    for num in array { // array 의 길이만큼 아래 연산이 실행
    	if num > maxNum { // 비교 연산 1번 실행
        	maxNum = num // 대입 연산 1번 실행
        }
    }
    return maxNum
}
let input = [3, 5, 6, 1, 2, 4]
let result = findMaxNum(input)

• array의 원소 갯수 = N
• maxNum 대입연산 1번 + array의 길이 * (비교 연산 1번 + 대입 연산 1번) = 1 + 2N
• Big-O(빅오) 표기법에서는 N의 지수부분만 유효하게 쓰이므로 O(N)이 된다

공간 복잡도

• 시간 복잡도와는 다르게 공간 복잡도는 문제를 행결하는데에 대한 공간과의 상관관계를 말한다

My Opinion

알고리즘을 풀 때, 우선 순위는 우리가 아는 문법을 대입하여 문제를 풀어보는 게 가장 중요하고, 여유가 생기기 시작할 때, 시간 복잡도를 고려하여 알고리즘 문제를 풀어보는 습관을 가져야 한다 ( 아직은 모든게 낯설고 어렵다 )