[자료구조] 누구나 자료구조와 알고리즘

 

1.자료구조가 중요한까닭

데이터를 어떻게 조직하는가에 따라서, 프로그램은 수십 수백배 더 빠르게 혹은 더 느리게 실행 될 수 있다.

대량의 데이터를 처리해야하는 프로그램이나 수천명이 사용하는 웹앱을 개발한다고 가정할때, 우리가 선택한 

자료구조가 문제없이, 빠르게 실행될수있는 명쾌한 코딩을 작성하는 능력을 갖추고, 소프트웨어 공학자가 가져야

하는 전문성을 키우기 위해서는 각각의 자료구조가 프로그램의 성능에 어떠한 영향을 끼치는지 아는것이 중요하기

때문이다.

 

2.알고리즘이 중요한까닭

사용자가 선택하는 알고리즘에 따라 코드의 속도가 영향이 크게 미치기 때문이다. 같은 프로그래밍 목적이더라도, 모든 상황에 딱 들어맞는 단하나의 자료구조나 알고리즘은 없기 때문 (예를들면 검색시 선형검색과 이진검색시 시간복잡도 차이를 예로들수있다)

 

3.빅오표기법

이름	시간복잡도	알고리즘 예제
상수 시간	O(1)	리스트에서 인덱스를 사용하여 데이터를 찾음
로그 시간	O(log n)	이진 트리 탐색
선형 시간	O(n)	정렬되지 않은 배열에서 데이터 검색 등
선형 로그 시간	O(n log n)	퀵정렬, 머지정렬 등
2차 시간	O(n^2)	버블 정렬, 삽입정렬 등
3차 시간	O(n^3)	편상관관계 계산 등
지수 시간	O(2^n)	피보나치, Brutal Force 등
팩토리얼 시간	O(n!)	완전탐색(Brutal Force)무작위 대입

4.빅오로 코드속도올리기 

빅오표기법을 명확히 이해하면, 두개의 코드중 어떠한 코드가 느린지 식별할수있고, 두 경쟁 알고리즘 중 더빠른 알고리즘을 분명하게 고를 수 있다.

• 4-1.배열의 중복 값이 있는지 확인하는 이차시간이 걸리는코드

function hasDuplicateValue(array){
	let steps = 0;
	for(let i = 0; i < array.length; i++){
    	for(let j = 0; j < array.length; j++){
        	steps++;
    		if( i !== j && array[i] == array[j] ){
            	return true
            }
    	}	
    }
    return false;
}

 

• 4-2 선형시간이 걸리는 해결법

function hasDuplicateValue(array){
    let existingNumbers = [];
    for ( let i = 0; i < array.length; i++){
    	if(existingNumbers[array[i]] === undefined){
        	existingNumbers[array[i]] = 1;
        }else{
        	return true;
        }
    }
    return false;
}

 

5.빅오를 사용하거나 사용하지않는 코드최적화 

빅오는 버블정렬과 선택정렬간에 차이를 두지 않지만, 알고리즘의 장기적인 증가율에 대해서는 선형시간이 이차시간보다 빠르다. 다시말해 어느 정도 크기의 데이터에 대해서는 O(N)이 O(N^2)보다 빠르다. 하지만 빅오표기법은 시간복잡도의 상수를 무효하기  때문에 100N이든 2N이든 같은 같은 O(N)이라고 측정한다. 실질적으로 같은 상수시간의 시간복잡도를 가지더라도, 해당 로직의 단계를 줄여주는 ex) O(100N) -> O(2N) 차이가 발생할수 있음을 알려주고 충분히 최적화 할수 있음을 알려준다. (반복문을 통해 원소의 갯수 즉, 룩업을 띄어넘기 하는방법을통해)