[자료구조 & 알고리즘] 1. 자료구조와 알고리즘

자료구조와 알고리즘

1. 자료구조 (Data Structure)

• 데이터를 저장하고 관리하는 방식

• 데이터를 체계적으로 저장하여 메모리를 효율적으로 사용할 수 있게 하고, 빠르고 안정적으로 데이터를 처리할 수 있게 도와줌.

• 알고리즘과 긴밀한 관계

     - 특정 알고리즘을 구현하기 위해 꼭 사용해야 하는 자료구조가 있음.

     - 어떤 자료구조를 선택하는지에 따라 알고리즘이 달라질 수 있음.

 

2. 알고리즘 (Algorithm)

• 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법

• 자주 쓰이는 문제 해결 방법을 패턴화하고 이름을 붙인 것

     - ex) BFS, DFS, Binary Search, Dijkstra 등

• 한 문제를 해결할 수 있는 알고리즘은 다양함.

     - 각 문제에 적합한 알고리즘을 선택할 수 있어야 함.

     - 알고리즘을 평가할 수 있어야 함.

 

3. 알고리즘의 평가 기준

• 시간 복잡도
     - 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계

     - 주로 빅-오 표기법으로 나타냄.

• 공간 복잡도

     - 입력의 특성에 따라 문제를 해결하는 데 필요한 메모리 공간의 양

 

※ 시간 복잡도와 공간 복잡도는 Trade-Off 관계

     - 실행 시간을 줄이기 위해서는 메모리를 더 사용해야 하고, 메모리 사용량을 줄이기 위해서는 실행 시간이 늘어나게 됨.

 

4. 빅-오(Big-O) 표기법

• 인자가 무한대로 향할 때 함수의 극한적인 동작을 설명하는 수학적인 표기법

     - 인자가 무한으로 향할 경우 최고차항을 제외한 낮은 차수의 항이나 계수 등은 최고차항에 비해 영향이 미미하기 때문에 배제

     - 최고차항만을 표기함.

     - ex) 3 n² + 5n은 O(n²)으로 표기할 수 있음.

• 알고리즘의 시간 복잡도를 계산할 때 주로 사용.

     - 알고리즘의 입력 값의 양에 따라 얼만큼의 연산을 하는지를 빅-오 표기법으로 나타냄.

 

• 아래의 test1 메소드는 array1의 크기에 따라 연산 횟수가 달라짐.

     - array1의 크기를 n이라고 하면 아래 함수는 3n + 1 정도의 연산 횟수를 가짐.

     - 빅-오 표기법으로 나타낼 경우 최고차항만을 표기하기 때문에 O(n)로 나타낼 수 있음.

private void test1(int[] array1) {
    int length = array1.length;

    for(int i = 0; i < length; i++) {
        System.out.println(array1[i]);
    }

    for(int i = 0; i < length; i++) {
        System.out.println(array1[i]);
    }

    for(int i = 0; i < length; i++) {
        System.out.println(array1[i]);
    }
}

 

• 아래의 test2 메소드는 n² + 10n + 1 정도의 연산 횟수를 가지기 때문에 빅-오 표기법으로 나타내면 O(n²)임.

private void test2(int[] array2) {
    int length = array2.length;

    for(int i = 0; i < length; i++) {
        for(int j = 0; j < length; j++) {
            System.out.println(array2[j]);
        }
    }

    for(int i = 0; i < 10*length; i++) {
        System.out.println(array2[i]);
    }
}