2023. 10. 18. 10:20ㆍCS
학교 공부를 통해 막연하게 생각했던 자료구조와 알고리즘에 대해 자세히 알게 됐다.
한줄로 간단하게 요약하자면 자료구조와 알고리즘은 '시간복잡도와 공간복잡도를 효율적으로 사용하기 위한 탐색, 정렬 방법과 그에 적절한 자료형을 사용하는 것' 을 배우는 것이다.
내가 알고 있는 Java언어에 빗대어 선형구조의 자료형을 알아보자.
선형 구조란 자료형이 순서를 가지고 있는 것이다. 여기서 순서란 물리적 순서와 논리적 순서를 구분하지 않는다. 즉 어디에서든 순서가 있으면 된다는 것이다.
물리적 순서는 메모리에 저장돼있는 자료형의 데이터를 말하고 논리적 순서는 코드로 동작할 때 접근하는 순서라고 생각하면 된다.
-순차리스트와 선형리스트의 내부 구조
Java에서 Array(배열, 순차리스트)은 인덱스를 가지고 있고 LinkedList는 인덱스가 없다.
그 이유는 배열은 내부적으로 물리적 순서와 논리적 순서를 일치시키기 때문이다.
그러나 LinkedList는 물리적 순서가 뒤엉켜있다. 노드의 포인터는 바로 뒤의 노드를 서로 가르키는 식으로 이어져있는 자료형이기 때문이다.(주의할 것은 물리적 순서가 다르다고 해서 논리적 순서가 없는 것은 아니므로 LinkedList와 같이 Node로 이어져있는 자료구조도 선형구조라고 본다)
이러한 자료구조의 특성 때문에 삽입과 삭제, 탐색에 있어서 시간복잡도가 다르게 된다.
-탐색 및 삽입 삭제에서의 시간복잡도는?
일반적으로 순차 리스트의 경우에는 값의 조회(탐색)에는 O(1)의 시간복잡도를 가진다. 논리적 순서와 물리적 순서가 동일하기 때문에 인덱스를 통해 접근하기 때문이다.
그러나 선형 리스트는 순서가 없기 때문에 특정 값을 찾기 위해서는 특정 data를 가지고 있는 Node를 front위치부터 최악의 경우 rear까지 탐색해야할 것이다. 따라서 시간복잡도는 O(n)이 된다.
삽입과 삭제에서도 이러한 구조가 동일할까? 아니다.
Node로 이루어진 선형리스트(Java에서 LinkedList)는 비엔나 소시지와 같다. 중간에 비엔나 소시지를 자르고 이어붙인다 생각해보자. 정말 간단하게 연결된다.
그러나 Array는 다르다. 배열은 크기가 불변이기 때문에 값의 삭제와 삽입에 있어서 굉장히 제약적이다. 벡터와 ArrayList를 사용한다면 크기가 가변적으로 변할 수 있지만 이는 곧 내부적으로는 배열의 생성 및 삭제 과정을 포함하고 있기 때문에 사용하기 용이한 것 뿐이지 삽입과 삭제가 빈번할 때 배열이 유리한 것은 아니라는 뜻이다.
따라서 배열의 삽입/삭제 시간복잡도는 O(n)이고 선형리스트의 삽입/삭제의 시간복잡도는O(1)이다.
-마치며
자료구조 이외에도 정렬에 대한 여러가지 알고리즘을 배웠지만 실제로 적용해본적은 없다.
그러나 자료구조만 잘 적용시켜도 백준에서 시간초과로 풀지 못한 문제는 꽤 많이 해결될 것 같다.
그리고 백준에서 정렬은 버블정렬만 사용했는데 버블정렬은 O(n제곱)의 시간복잡도를 가지고 있기 때문에 굉장히 비효율적인 알고리즘이라 볼 수 있다. 합병 정렬(nlogN)이나 쉘 정렬(얘는 배열의 그룹간 탐색할 gap을 설정해줘야 한다)을 이용하면 좀 더 개선되지 않을까 생각도 든다.