[실전 알고리즘] 0x02강 - 배열과 연결 리스트_구버전

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

현재 보고있는 강의는 구버전입니다. 내용에는 문제가 없으나 리뉴얼 중이니 이 게시글을 참고해주세요.

 

리뉴얼한 버전은 [실전 알고리즘] 0x03강 - 배열, [실전 알고리즘] 0x04강 - 연결 리스트 에서 확인할 수 있습니다. 리뉴얼 버전으로 보시는 것을 추천드립니다.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

안녕하세요, 이번 시간에 다룰 주제는 배열과 연결 리스트입니다. 연결 리스트를 해야할지 말아야할지 고민을 좀 많이 했는데, 코딩 테스트에 나올 가능성이 그닥 높지 않은 자료구조이긴 하지만 그래도 개념 정도는 소개를 드리는게 좋을 것 같아 연결 리스트를 포함했습니다. 특히 연결리스트에서는 STL과 더불어 코딩테스트에서 큰 도움이 될 간단한 버전의 연결 리스트 구현을 넣어뒀으니 참고하세요.

 

 

배열은 자료구조를 따로 공부한 적이 없는 사람도 알고 있는 가장 익숙한 자료구조입니다. 배열은 메모리 상에 원소를 연속하게 배치한 자료구조로, 원소를 저장하는 것 이외에 추가적으로 소모되는 메모리의 양이 거의 없는 것이 장점입니다. 또한 메모리 상에 원소가 연속해서 있어야 한다는 성질은 cache hit rate가 높다는 장점을 이끌어냅니다.(만약 cache hit rate가 뭔지 모르시면 넘어가도 됩니다.) 그러나 반드시 메모리상에 연속한 구간을 잡아야하기 때문에 할당에 다소 제약이 걸린다는 단점도 있습니다.

 

원래 C언어에서 제공하는 배열은 길이 정보가 없지만 배열을 가지고 작업할 때 따로 변수를 하나 두어 배열의 길이를 저장하고 있으면 간단하게 해결할 수 있는 문제이기 때문에 배열의 길이를 알고 있다고 가정하고 여러 가지 연산에 대한 시간복잡도를 알아보겠습니다.

 

배열에서 $i$번째 원소를 확인/변경하는 것은 상식적으로 생각했을 때 $O(1)$에 수행 가능합니다. 원소를 끝에 추가하는 것 또한 마찬가지로 $O(1)$에 수행 가능합니다.

 

마지막 원소를 제거하는 것도 마찬가지입니다. 그러나 임의의 위치에 원소를 추가하기 위해서는 그 뒤의 원소를 전부 한 칸씩 밀어야 하므로 $O(N)$이 필요합니다. 마치 책장에 책이 연속해서 꽂혀있을 때 중간에 책을 넣기 위해서는 나머지 책들을 밀어야하는 것과 같은 상황입니다. 그 위치가 끝에 가까울수록 시간은 줄어들고, 앞에 가까울수록 시간은 늘어나나 평균적으로 생각하면 $N/2$ 개의 원소를 밀어야할 것이기 때문에 $O(N)$이라고 해도 무방합니다.

 

그리고 임의의 위치에 원소를 제거하는 것 또한 뒤의 원소들을 모두 앞으로 밀어야하기 때문에 마찬가지로 $O(N)$입니다. 그냥 빈 채로 두면 안되냐고 생각을 할 수도 있지만, 그렇게 되면 메모리 상에 원소가 연속해서 존재하지 않기 때문에 더 이상 $i$번째 원소를 $O(1)$에 찾을 수가 없습니다.

 

이 4가지 연산에 대한 시간복잡도를 정리하면 오른쪽과 같습니다.

 

배열은 워낙 간단한 구조이기 때문에 특별한 팁은 없는데, 전체를 특정 값으로 초기화시킬 때 어떻게 하면 효율적으로 할 수 있는지만 짚고 넘어가겠습니다. 제일 짤막한 방식으로는 memset 함수를 활용하는 방식이 있는데, memset 함수는 실수할 여지가 굉장히 많습니다. 예를 들어 0과 -1이 아닌 다른 값을 넣으면 오동작한다거나, 2차원 이상의 배열을 함수의 인자로 넘겨 그 곳에서 memset을 하면 잘못 들어간다거나 하는 점들이 있습니다. 그렇기 때문에 memset은 정말 비추천합니다.

 

두 번째로는 그냥 for문으로 차분하게 하나하나 값을 다 바꾸는 방식입니다. 코드가 조금 길긴 하지만 실수할 여지가 별로 없기 때문에 무난하고 괜찮습니다.

 

마지막으로는 STL의 fill 함수를 이용하는 방식입니다. 이 방식은 실수할 여지도 별로 없고 코드도 짧으니 익숙해진다면 가장 추천하는 방식입니다.  

 

방금 소개한 fill 함수 말고도 굉장히 많은 함수들이 존재하나 나중에 필요할 때 다시 알려드리는 것으로 하고 넘어가겠습니다. 개인적으로 알아보고 싶으면 공식 레퍼런스 사이트의 algorithm 헤더 부분(링크)을 확인하면 됩니다.

 

배열은 인덱스에 해당하는 원소를 빠르게 접근해야 할 때, 그리고 마치 창고처럼 데이터를 쌓아두고 싶을 때 유용하게 활용할 수 있습니다. 만약 데이터의 삽입/삭제가 빈번한 상황이면 배열이 비효율적입니다. 사실 거의 대부분의 문제에서, 일단 입력값을 저장해놓고 시작하는 일이 많기 때문에 배열이 쓰입니다. 그러니 이 용도 말고 인덱스에 해당하는 원소를 빠르게 접근하는 목적으로 배열을 사용하면 효율적인 문제를 소개해드리겠습니다.

 

BOJ 10808번 알파벳 갯수 문제입니다. S에 'a', 'b', ... 'z'가 몇 개 들어있는지를 알아야 하므로 'a', 'b', 'c' , .. , 'z'에 대해 S를 한 바퀴 돌면서 갯수를 세면 됩니다. 이를 구현한 정답 코드를 확인해보세요. (코드)

 

그런데 이 방식대로면 같은 문자열을 26번이나 확인하게 됩니다. 뭔가 더 효율적인 방법은 없을까요? 만약 사람한테 이 문자열에서 각 글자가 몇 개씩 들어있는지를 세보라고 한다면 문자열을 26번이나 세지는 않았을텐데.. 사람은 이런 식으로 풀지 않았을까요?

 

 

 

 

 

 

이 방식을 코드로 옮겨내기 위해서는 각 문자의 등장 횟수를 저장할 26칸 짜리 배열이 필요합니다. 정답 코드 상의 freq 배열을 참고하세요. (코드)

 

이번에는 STL vector를 간략하게 설명드리겠습니다. vector 자료구조는 배열과 거의 동일한 기능을 수행하는 자료구조로, 배열과 마찬가지로 원소가 메모리에 연속하게 저장되어 있기 때문에 배열과 마찬가지로 인덱스로 원소에 $O(1)$에 접근할 수 있습니다. 그런데 vector는 배열과 달리 크기를 자유자재로 늘이거나 줄일 수 있다는 장점이 있습니다.

 

추후에 그래프의 인접 리스트(Adjacency List)를 다루기 전 까지는 굳이 배열을 쓰지 말고 Vector를 써야하는 상황이 잘 나오지 않아 당장은 몰라도 되지만 다른 사람의 코드를 읽을 때 Vector를 어려워할 것 같아 간략하게 소개하고 갑니다.

 

Vector에는 다양한 메소드들이 있는데, 그냥 직접 눈으로 다양한 메소드들의 실행 결과를 살펴보세요. push_back, size, insert, erase, pop_back 정도만 알고 있어도 크게 불편함은 없습니다. 그 외에 더 많은 메소드들을 보고 싶거나 사용법에 대해 궁금한 점이 있으면 직접 레퍼런스 사이트를 찾아보세요. (링크) (오류를 지적해주신 zmzmzmzm님 감사합니다!)

 

Vector에서 제일 주의해야하는 것은 size()의 반환 값이 unsigned int라는 점입니다. 이것으로 인해 개고생을 하는 경우를 몇 번 봤습니다. 아래의 코드를 보면 vector v1의 모든 원소를 출력하는 코드로 딱히 틀린점이 없어보입니다. 그런데 이 코드가 v1이 비어있을 때에는 심각한 결과를 불러 일으킵니다. unsigned int 0에서 int 1을 빼면 unsigned int $2^-1$이 되기 때문이죠. 그렇기 때문에 $i$가 0부터 $2^-1$까지 돌게 됩니다. 이를 막기 위해 int로 강제 형변환을 시켜주거나 그냥 v1.size에서 무언가를 빼지 않아야 합니다.

 

그리고 insert, erase가 중간에 있는 원소에 대해 사용했을 경우에는 배열과 마찬가지로 $O(N)$의 시간을 필요로 한다는 점 또한 주의해야합니다. 생각해보면 당연한건데 이 사실을 까먹고 잘못된 시간복잡도로 문제를 접근하는 경우를 막기 위해서입니다.

 

배열은 끝이 났고 지금부터는 연결 리스트를 살펴보겠습니다. 연결 리스트는 마치 레고 혹은 직렬연결과 같은 형태로 각 원소가 자신의 다음 원소, 혹은 이전 원소와 다음 원소의 위치까지 함께 가지고 있는 자료구조입니다. 그리고 원소들은 메모리 상에 불연속적으로 위치하고 있어도 무방합니다.

 

각 원소가 자신의 다음 원소의 위치만 가지고 있는 연결 리스트를 Singly Linked List, 자신의 이전/다음 원소의 위치를 모두 가지고 있는 연결 리스트를 Doubly Linked List, 마지막 원소가 처음 원소의 위치를 가지고 있는 연결 리스트를 Circular Linked List입니다. 굳이 나온다면 면접에 나올법한 정의네요.

 

연결 리스트는 임의의 위치에 원소를 추가하는 것, 그리고 제거하는 것 모두 $O(1)$입니다. 여기서 주의해야 하는게, 해당 임의의 위치에 일단 도달을 하고 난 후에 $O(1)$이라는 의미입니다. 만약 시작 위치만 주어진 후에 $k$번째 위치에 원소를 추가해라 라는 명령이 들어오면 배열과 다르게 $k$번째 위치를 $O(1)$에 찾아갈 수가 없기 때문에 이것은 $O(1)$에 수행할 수 없고 평균적으로 $O(N)$이 걸립니다.

 

그리고 임의의 위치에 있는 원소의 값 확인 및 변경은 앞에서 얘기한 것과 같이 직접 그 위치까지 도달을 해야하기 때문에 $O(N)$이 걸립니다.

 

Linked List의 구현은 보통 C의 구조체와 동적할당을 이용합니다. 이 부분은 손코딩이나 면접에서 단골 질문문제이기 때문에 반드시 따로 공부를 하셔야 합니다. 그러나 이 구현은 코딩테스트에서 쓰기엔 별로 좋지 않습니다.

 

STL List는 Doubly Linked List 구조를 가지고 있기 때문에 Linked List가 필요하면 그냥 가져다 쓰면 됩니다. 만약 STL을 쓸 수 없는 코딩테스트라면, 구조체 + 동적할당 대신 제가 조금 뒤에 알려드릴 야매 Linked List를 이용하시면 됩니다.

 

Linked List는 기능이 단순하기 때문에 딱히 응용해서 낼 만한 여지가 없습니다. 보통 시뮬레이션 느낌의 문제에서 쓰이는데, 그런 문제는 꼬아낼 수가 없기 때문에 딱 보자마자 Linked List가 필요하다는 것을 알아차릴 수 있을 것입니다.

 

만약 Linked List처럼 보이는 문제라고 하더라도 N이 작아 시간복잡도가 널널하다면 굳이 Linked List를 쓰지 말고 Vector로 구현하는게 마음 편합니다.

 

STL List도 예제로 이해를 해봅시다. 뒤에 문제를 풀 때에도 STL List를 써서 푸는 풀이 코드를 두었으니 나중에 같이 읽어보셔도 좋습니다. 레퍼런스 사이트도 필요하면 확인해보세요. (링크)

 

지금부터 소개할 것은 야심차게 준비한 저의 야매 Linked List입니다. 이 야매 Linked List는 원소를 배열로 관리하고, prev와 next에 이전/다음 원소의 포인터 대신 배열 상의 인덱스를 저장하는 방식으로 구현한 Linked List입니다. 메모리 누수의 문제 때문에 실무에서는 절대 쓸 수 없는 방식이지만 코딩테스트에서는 구현 난이도가 일반적인 Linked List보다 쉽고 시간복잡도 또한 동일하기 때문에 애용합시다. 

 

구현에 필요한 변수는 dat, pre, nxt배열과 unused 입니다. data, prev, next라고 쓰면 좋겠지만 3개 모두 이미 std namespace에 이미 선점되어 있어서 한 글자씩 뺐습니다. dat는 원소의 값, pre는 이전 원소의 인덱스, nxt는 다음 원소의 인덱스입니다. unused는 현재 사용되지 않는 인덱스를 의미하며 새로운 원소가 추가될 때 마다 1씩 증가합니다. 특별히 0번지는 Linked List의 시작 원소로 고정되어 있으며, 0번지의 원소는 값이 들어가지 않는 dummy node입니다.

 

길이 정보가 필요하다면 따로 len 변수를 두어서 삭제가 일어나면 1 감소시키고 삽입이 일어나면 1 증가시키면 됩니다.

 

3, 13, 51, -2가 연결 리스트를 이루고 있는 것을 data, pre, nxt 배열의 형태로 생각하면 아래와 같습니다. 3은 1번지에, 13은 2번지에, 51은 3번지에, -2는 5번지에 들어있습니다. 4번지에는 원래 값이 있었으나 제거가 된 상태이고 실제로는 점이 아니라 다른 어떤 값이 들어있겠지만 앞으로 참조될 일이 없기 때문에 무슨 값이 들어있던지 전혀 상관이 없습니다.

 

51의 오른쪽에 20을 삽입하는 상황을 step by step으로 이해해봅시다. 오른쪽 상단에서 연결 리스트의 각 노드의 상태가 바뀌는게 코드 상에는 어떻게 들어가는지를 알 수 있게끔 해두었습니다.

 

 

일단 unused가 가리키는 곳의 data에 20을 씀으로서 관념적으로 새로운 원소를 만들어냅시다.

 

 

새 원소의 pre의 값에 삽입할 위치인 51의 주소 3을 넣습니다.

 

 

nxt에는 삽입할 위치의 nxt 값인 5를 넣습니다.

 

 

그리고 51의 nxt, -2의 prv를 모두 unused로 바꾸면 노드의 삽입이 완료되었습니다.

 

 

마지막으로 다음번의 삽입을 위해 unused를 1 증가시킵니다.

 

 

각 step을 코드로 옮기기만 하면 됩니다. 단 step 4에서 $nxt[idx]$가 -1인지 아닌지에 따라 처리를 달리 해주어야 합니다. 지금 이 함수는 추가된 위치를 반환하는데, 편의에 따라 추가된 위치의 이전 위치를 반환하거나, 그냥 void 함수로 만들어도 상관 없습니다.

 

 

그 다음으로 알아볼 것은 삭제입니다. 51을 지우고 싶은 상황에서 앞 뒤를 넘나드는게 굉장히 헷갈리기 때문에 "삭제할 위치"(51), "이전 위치"(13), "다음 위치"(-2) 라는 용어를 미리 정의하고 가겠습니다. 마찬가지로 위의 연결 리스트 형태와 실제 데이터의 이동 상황을 비교해 살펴보면 됩니다.

 

 

우선 이전 위치의 nxt를 삭제할 위치의 nxt로 바꿉니다.

 

 

그리고 다음 위치의 pre를 삭제할 위치의 pre로 바꾸면 끝입니다. 51이 적혀있는 3번지의 값은 건드릴 필요가 없습니다. 어차피 이제 영영 참조될 일이 없는 값이니까요.

 

 

이 두 과정을 코드로 옮기면 오른쪽과 같습니다. 왜 $pre[idx] != -1$인지는 체크하지 않아도 되는데 $nxt[idx] != -1$인지는 체크해야 할까요? 이 부분은 스스로 해답을 찾아보시는 것을 추천드립니다. 삽입과 마찬가지로 제거된 원소의 이전 원소를 반환해도 되고, 다음 원소를 반환해도 되고 그냥 void 함수로 두어도 됩니다.

 

단 삭제 후에 잘못된 인덱스의 값을 참조하지 않도록 조심해야 합니다.

 

 

순회는 단순합니다. 0번지의 dummy node의 nxt에서 시작해 -1이 될 때 까지 계속 nxt로 이동하면 끝입니다.

 

이제 BOJ 1406번 에디터 문제를 풀어봅시다. 문제를 확인하면 알겠지만 문장 중간에서의 삭제와 삽입이 빈번하다는 점으로부터 대놓고 연결 리스트를 쓰는 문제인 것을 알 수 있습니다. 단, 만약 $N$이 최대 500,000이 아니라 5,000이었다면 $O(N^2)$이 시간 내로 통과되므로 굳이 익숙하지 않은 Linked List를 쓰지 않고 Vector로 풀었을 것입니다. 어쨌든 STL List를 쓴 코드와 야매 Linked List를 쓴 코드 둘 다 있으니 확인해보세요.

 

그룹에 이번 시간에 다룬 두 문제 이외에도 추가로 문제들을 넣어두었습니다. 지금은 4문제만 넣어두었지만 괜찮은 문제를 발견하면 계속 추가할 예정입니다.

 

링크드 리스트와 관련해 면접이나 손코딩에서 물어볼만한 문제 2가지를 마지막으로 소개해드립니다. 수학퍼즐이라고 생각하고 즐겁게 풀어보세요. 반드시 다음 장으로 넘기기 전에 본인만의 답을 구상해보세요.

 

 

어떤가요? 생각한 풀이도 공간복잡도 $O(1)$ 풀이였나요? 참고로 Q2번 문제가 저희 고등학교 자료구조 및 알고리즘 수업 기말고사 문제였습니다. 아직까지 기억이 나네요.

 

이번 시간에 배열과 연결 리스트의 정의, 제공되는 연산, 쓰임새를 배웠습니다. STL Vector와 List도 짚고 넘어갔습니다. 야매 Linked List도 배웠네요. 문제 풀어보시고 다음 시간엔 Stack과 Queue를 해봅시당