by
Oct 31. 2020
C++, JAVA 자료구조 및 그래프 순회
백준 BFS, DFS
대학교 2학년 시절 자료구조라는 과목을 배웠다. 그 당시엔 너무 재미없었고 점심 이후에 배우다 보니 잠에 빠져 제대로 공부하지 못했다. 컴퓨터공학과의 꽃이라 할 수 있는 중요한 과목을 대충 배워버린 탓에 복학이 무서워 군대에서 자료구조 책을 달달 볼 수밖에 없었다.
너무 많이 봐서 이제는 낡아버린 자료구조 책이지만 불과 회사에 입사 전 코딩 테스트를 준비하기 전까지도 자료구조를 제대로 알지 못했다.
처음 프로그래밍 언어를 배우고 어느 정도 익숙해지면 무엇이든 만들 수 있을 것 같은 자신감이 생긴다. 하지만 처리하는 데이터가 많아질수록 메모리가 부족하고 시간 안에 처리하지 못하는 문제에 직면하게 된다. 빅데이터 시대에 살아가는 우리들에게 자료구조는 필수적으로 배워야 하는 과목이다. 자료구조는 많은 양의 데이터를 처리할 때 가장 효율적으로 읽고 쓰도록 데이터를 관리하는 방식이자 기술이라 할 수 있다. C++ 언어로 자료구조에 무엇이 있는지 알아보고 백준에서 BFS, DFS 문제를 함께 풀어보자. 각 자료구조마다 코드를 보여줄 텐데 파이썬은 list 하나로 모두를 해결하므로 파이썬 코드 대신 C++과 JAVA를 함께 보여주겠다. 언어마다 어떤 식으로 자료구조를 사용하는지 비교해보자.
많은 자료구조가 있지만 오늘은 가장 기본적인 자료구조만 알아보자
List
실제로 내가 이 자료구조를 구현하기 위해선 포인터를 알아야 한다. 아직 포인터에 대해 설명하지 않았으므로 추상적으로 설명하겠다. 여러 개의 데이터가 메모리에 중구난방으로 저장되어 있다. 이 데이터를 일렬로 세우고 싶은데 어떻게 해야 할까? 데이터마다 앞에 있는 데이터의 위치와 뒤에 있는 데이터의 위치를 기억하도록 하면 될 것이다.
이렇게 하면 바로바로 다음 위치에 있는 데이터를 쉽게 찾아 읽을 수 있다. 중간에 추가하거나 빼는 방법도 간단하다. 알고 있는 데이터 위치를 변경하면 된다.
위처럼 양방향으로 위치를 기억하는 리스트를 더블 링크드리스트라고 한다. 이 리스트는 그림처럼 어느 위치에서도 삽입/제거가 빠르다. 단점도 있지 않을까?
단점은 중간에 있는 데이터를 참조할 수 있는 방법이 없다는 것이다. 중간에 있는 데이터를 읽으려면 처음 또는 끝에서부터 찾아나가야 한다. 다시 말해서 특정 컨테이너로 직접 접근이 불가능하다. 데이터를 모두 읽는 방법은 Forward 방향 또는 Reverse 방향으로 컨테이너에 접근하면 된다.
C++
JAVA
위와 같이 데이터를 넣고 정렬하고 조회(순회)하면 된다. JAVA와 달리 C++에서 자료구조를 순회하기 위해선 iterator라는 것을 이용해야 한다. 컨테이너의 위치(주소)를 기억하는 변수라고 생각하자. 앞에 데이터를 넣고 빼려면 위와 반대로 push_front, pop_front 함수를 호출하면 된다. 반대로 정렬하기 위해선 reverse 함수를 이용하면 된다. 그 외 함수는 구글 검색하면 쉽게 확인할 수 있으니 더 이상 설명하지 않겠다.
Vector
다음에 알아볼 자료구조는 동적 배열 Vector이다. 우리가 알고 있는 배열과 매우 유사하지만 배열은 길이가 고정적이어야 하는 반면 Vector은 크기가 가변적이다. 데이터를 넣다가 크기가 모자라면 알아서 기존 크기의 2배만큼 더 할당한다. Vector는 List의 단점을 보완해준다. 바로 중간 참조가 가능하다는 것이다.
배열이기 때문에 그 순서만 알고 있다면 바로 중간에 있는 데이터를 참조할 수 있다. 단점은 중간에 데이터를 넣고 빼려면 그다음에 있는 데이터들을 모두 밀거나 당겨야 하기 때문에 느리다. 하지만 끝에 데이터를 넣는 것은 매우 빠르다. 그렇다면 벡터는 언제 사용해야 할까? 마지막에만 데이터를 추가하거나 처음에 데이터를 넣고 변경 없이 조회하는 용도로만 사용하는 것이 좋다.
벡터 코드는 다음과 같다.
C++
JAVA
C++은 List와 매우 유사한데 주석으로 처리한 부분을 유심히 보면 된다. 정렬방법이 조금 다르고 중간 참조가 가능하다.
JAVA의 경우 Vector와 ArrayList가 매우 유사한데 그 차이를 알기 위해선 스레드가 무엇인지 알아야 한다. 가볍게 설명하자면 한 프로그램에서 동시에 여러 개의 코드를 실행시킨 것을 스레드라 하는데 Vector는 스레드에 대해 데이터가 안전하다는 장점이 있다. 코딩 테스트에선 스레드를 사용하지 않으므로 ArrayList를 사용하는 것을 추천한다.
Stack
앞에서 설명한 자료구조는 처음부터 끝까지 데이터를 읽어야 하거나 중간에 있는 데이터를 참조할 때 사용했다. 데이터를 중간에 삽입할 필요 없고 마지막 데이터만 참조하거나 뺄 거라면 앞에 있는 자료구조를 사용할 필요 없다. 이때 Stack을 사용하면 된다. 보통 자식 노드가 없을 때까지 가능한 멀리까지 탐색하는 깊이 우선 탐색이나 백 트랙킹을 할 때 사용된다. 위상 정렬에서도 stack을 이용할 수 있다.
C++
JAVA
여기선 모든 데이터를 조회할 필요 없으므로 stack에 데이터가 없을 때까지 데이터를 모두 읽는 방식으로 코드를 작성했다. 각 언어마다 stack에서 데이터를 참조하는 방법이 다르다. C++ 은 top 함수로 java는 peek 함수로 데이터를 참조한다.
Queue
그렇다면 데이터를 마지막에 넣지만 가장 처음에 넣은 데이터를 참조하고 빼고 싶다면 어떤 자료구조를 사용해야 할까? 이때는 Queue 자료구조를 사용하면 된다. 가장 근접한 노드들을 우선 조회하는 너비 우선 탐색에서 사용된다.
C++
JAVA
코드는 stack과 거의 비슷하다. 단지 자바에서는 LinkedList를 이용해서 Queue 자료구조를 만든 것이 그 차이인데 이는 클래스의 상속이라는 개념을 알아야 이해할 수 있으므로 우선 설명을 패스하겠다.
Heap, Max Heap, Min Heap
앞에서 설명한 자료구조는 정렬 후 중간에 데이터를 삽입할 경우 다시 정렬해줘야 하는 문제가 있다. 넣은 데이터 중에서 가장 큰 값이나 작은 값을 알고 싶을 때 사용하는 자료구조는 없는 것일까? 이때 Heap을 사용한다.
Heap을 이해하기 위해선 완전이진트리라는 개념부터 이해해야 한다. 앞에 설명한 자료구조를 이용해 그래프를 그릴 때 다음과 같은 규칙이 있다고 가정하자. 자식 노드는 2개만 가능하고 자식 노드는 부모 노드보다 값이 작거나 같아야 한다. 완전 이진트리는 아래 그림과 같다.
위와 같다면 가장 위에 있는 부모 노드가 넣은 데이터중에서 가장 장 큰 값일 것이다. 이런 자료 구조를 MaxHeap라 하며 반대로 자식 노드가 부모 노드보다 크다면 가장 최상단에 있는 부모 노드는 값이 가장 작은 자료구조를 MinHeap이라고 한다.
C++
JAVA
보면 우선순위 큐(PriorityQueue)를 이용해 MaxHeap 또는 MinHeap을 만든 것을 알 수 있다. C++은 우선순위 큐 기본이 MaxHeap인 반면 JAVA는 MinHeap이 기본이다.
더 많은 자료구조가 있지만 기본적인 자료구조는 이 정도인 것 같다.
이제 위의 자료구조를 이용해 백준 문제 몇 개를 풀어보자!
https://www.acmicpc.net/problem/1260
