c++ 알고리즘 공부 3 - 배열
첫 번째로 배열은 메모리 상에 원소를 연속하게 배치한 자료구조이라서 k번째 원소의 위치를 바로 계산할 수 있게 됩니다. 시작 주소에서 k칸 만큼 오른쪽으로 가면 되기 때문입니다. 그렇기 때문에 k번째 원소를 O(1)에 확인하거나 변경할 수 있습니다.
두 번째로 메모리는 다른 자료구조와 다르게 추가적으로 소모되는 메모리의 양이 거의 없습니다. 아직 다른 자료구조를 배우지 않아서 비교를 할 수가 없는데, 다른 자료구조들을 배우고 나면 지금 이 소리가 무슨 의미인지 알 수 있을 것입니다.
세 번째로 메모리 상에 데이터들이 붙어있으니까 Cache hit rate가 높습니다.
네 번째로 메모리 상에 연속한 구간을 잡아야 하니 할당에서 다소 제약이 있습니다.
제일 짤막한건 cstring 헤더에 있는 memset 함수를 활용하는 방식입니다. 그런데 memset 함수는 실수할 여지가 굉장히 많습니다. 예를 들어 0이나 -1이 아닌 다른 값을 넣으면 오동작한다거나, 2차원 이상의 배열을 함수의 인자로 넘겨 그 곳에서 memset을 하면 잘못 들어간다거나 하는 점들이 있습니다. 그래서 memset은 정말 비추천합니다.
두 번째로는 그냥 for문을 돌면서 값을 하나하나 다 바꾸는 방식이고, 코드가 조금 투박하긴 하지만 실수할 여지가 없기 때문에 무난하고 좋습니다.
마지막 방식은 algorithm 헤더의 fill 함수를 이용하는 것이고, fill 함수는 실수할 여지도 별로 없고 코드도 짧으니 익숙해진다면 가장 추천하는 방식입니다.
이제는 STL vector를 설명해보겠습니다. vector는 배열과 거의 동일한 기능을 수행하는 자료구조로, 배열과 마찬가지로 원소가 메모리에 연속하게 저장되어 있기 때문에 O(1)에 인덱스를 가지고 각 원소로 접근할 수 있습니다. 그런데 vector는 배열과 달리 크기를 자유자재로 늘이거나 줄일 수 있다는 장점이 있습니다.
아주 까마득한 후에 그래프의 인접 리스트라는 것을 저장할 때에는 vector를 쓰는게 많이 편해서 vector가 필요하게 되지만 그 전까지는 사실 굳이 배열 대신 vector를 써야하는 상황이 딱히 없습니다. 그래서 당장은 몰라도 크게 상관 없지만 다른 사람이 vector로 짠 코드를 본다고 하면 아무래도 vector를 아는게 좋을 것 같아서 딱 그 정도만 설명을 드리겠습니다.
일단 사용법은 상단의 레퍼런스 사이트에 들어가면 다 익힐 수 있고 앞으로도 가능하면 설명글 보다는 직접 레퍼런스 사이트를 확인하면서 메소드들을 정확하게 익히는게 낫긴 하지만, 익숙하지 않으면 솔직히 좀 힘드니까 그냥 직접 vector를 사용한 예시 코드를 보여드리겠습니다.
직접 타이핑을 해서 확인해도 되고 github 링크에 들어가서 붙여넣기 해도 됩니다. 전반적으로 한 번 보시고, 특히 insert와 erase가 메소드로 이미 구현이 되어 있는 것을 알 수 있습니다. 인자로 v.begin() + x와 같이 주는걸 볼 수 있는데 STL의 iterator 개념을 모르면 조금 낯설 수 있을 것 같습니다. 하지만 설명은 안하고 넘어가겠습니다. iterator의 정체가 궁금하다면 따로 공부를 하시는걸 추천드립니다.
또 vector에서 =를 사용하면 deep copy가 발생합니다. 16번째 줄에서 v4는 {1, 2, 4}가 되었고 이후 v4를 바꿔도 v3에는 영향을 주지 않습니다.
vector에 있는 모든 원소를 순회하려고 할 때, 아마 이전에 본 적이 없으실 range-based for loop를 이용할 수 있습니다. 04, 05번째 줄 처럼 int e : v1 이라고 하면 e에 v1의 원소들이 하나씩 들어가는 for문이 됩니다.
지금은 값을 바꾸지 않고 그냥 출력만 해서 별 상관이 없지만, 만약 int e : v1이라고 하면 복사된 값이 e에 들어가고 int& e : v1이라고 하면 원본이 e에 들어갑니다. 그렇기 때문에 int e : v1라고 쓴 for문 내에서 e를 바꿔도 v1에는 영향이 가지 않지만, int& e : v1이라고 쓴 for문 내에서는 e를 바꾸면 원본인 v1에서 실제 해당 원소의 값이 바뀌게 됩니다.