Overview

• 응용프로그램에서 동작성능 & 안정성 확보를 위해 적절한 data stacture를 선택하는 것이 매우 중요하다.
• 이번 장에서는 linear data structures를 소개하고 있다.
• 자료구조를 잘 이해하고 있으면, 성능 향상, 표준화, 가독성, 유지 보수 등의 관점에서 유리하게 데이터를 관리할 수 있다.

연속된 자료 구조 & 연결된 자료 구조

• 어떤 자료 구조를 선택할 것인가에 대한 적합한 지표로 time complexity가 있다.
• 시간 복잡도(time complexity)는 특정 작업 수행 시 걸리는 시간을 데이터 크기에 대한 수식으로 표현하는 방식이다.
  • 데이터 크기가 변하면 연산 시간이 어떻게 변하는지를 보여준다.

연속된 자료 구조

• 모든 원소를 단일 메모리 chunk에 저장한다.
• 모든 원소가 같은 Type이면 모든 원소는 같은 크기의 메모리를 사용하므로 sizeof(type)으로 표시될 수 있다.
• 해당 자료 구조에서는 배열 전체 크기에 상관없이 원소에 곧바로 접근할 수 있다.
  • BA(Base Address) + i*sizeof(type), 해당 수식으로 곧바로 접근
• 데이터 접근 시간은 항상 일정하므로 Big-O 표기법으로 나타내면 O(1)로 표시할 수 있다.
• 배열의 유형
  • static array
    • 선언 블록 끝나면 소멸 -> stack 메모리에 할당되기 때문
    • int arr[size]
  • dynamic array
    • 생성 시점과 해제 시점을 자유롭게 결정 -> Heap 메모리에 할당 되기 때문
    • int* arr = new int[size]
• 배열은 하나의 원소 접근 시 인접 원소 몇개도 함께 cache로 가져온다. (cache locality)
  • 다시 주변 원소 접근시 캐시로 접근하므로 매우 빠른 동작 발생
    • 시간 복잡도에는 영향 X
• 배열은 연속된 원소에 매우 빠르게 접근할 수 있다는 큰 장점이 생긴다.
  • cache locality가 좋다.

연결된 자료 구조

• Node 라고 하는 여러 메모리 chunk에 데이터를 저장
  • 서로 다른 메모리 위치에 데이터가 저장된다.
  • linked list
• linked list의 각각 노드는 저장할 data, 다음 node를 가리키는 pointer를 가지고 있다.
  • 맨 마지막 노드는 NULL을 next node pointer로 갖고 있음으로서 끝을 의미하게 해준다.
• i 번째 원소 접근 시 linked list 내부를 연속적으로 이동하므로 O(n) 이다.
  • n : node 개수
• 새로운 원소 삽입 시 New Node 생성, 각 Node의 next pointer 수정
• 기존 원소 제거 시 더 이상 연결 리스트에 연결되어 있지 않도록 next pointer를 수정
  • 이후 메모리 할당 해제 및 다른 적절한 처리를 수행
• 연결 리스트는 배열과 달리 메모리 영역이 달라 cache locality가 좋지 않다.
• 연결 리스트에서 모든 원소를 차례대로 방문하는 경우 이론적으로 시간 복잡도는 동일하나 실제로는 연결 리스트 성능이 조금 더 떨어진다.

연속 vs 연결

• 연속 (array)
  • 임의 접근 O(1)
  • 맨 뒤 원소 삽입 O(1)
  • 중간 원소 삽입 O(n)
  • cache locality Good
• 연결 (linked list)
  • 임의 접근 O(n)
  • 맨 뒤 원소 삽입 O(1)
  • 중간 원소 삽입 O(1)
  • cache locality Bad
• C++ 에서는 std::array, std::vector, std::List 같은 다양한 자료구조 클래스를 제공하고 있다.
  • 적은 Bug

C style array의 제약사항

• 메모리 할당과 해제를 수동으로 처리
  • 해제 못하면 메모리 leak 발생
• [] 연산자에서 배열 크기보다 큰 원소를 참조하는 것을 검사 못한다.
  • segmentation fault or memory 손상으로 이어진다.
• 배열을 중첩해서 사용하면, 문법이 매우 복잡
  • 코드 이해 어려움
• deep copy가 기본적으로 동작하지 않는다.
  • 수동 구현필요
• std::array는 위 문제를 회피할 수 있도록 만들었다.

std::array

• 메모리를 자동으로 할당하고, 해제

std::array<int, 10> arr1;

• 원소의 type, 배열 size를 매개변수로 하는 클래스 template이다.

for (int i = 0; i < arr.size(); i++)
	std::cout << arr[i] <<" ";

• [] 연산자 제공
• 빠른 동작을 위해 전달 index 값이 배열 size보다 큰지는 검사하지 않는다.

try
{
	std::cout << arr.at(3) << std::endl;
}
catch (const std::out_of_range& ex)
{
	std::cerr << ex.what() << std::endl;
}

• at(index)도 제공 ([]과 같은 기능)
  • 인자로 전달된 index 값이 유효하지 않으면 std::out_of_range 예외 발생
  • 해당 메서드 사용 시, 예외에 적절하게 처리 가능하다.
  • 유효하지 않은 index에 접근할 수 있는 상황이면 예외 처리 코드를 만들 수 있다.

template <size_t N>
void print(const std::array<int, N>& arr);

• 함수 매개변수에서 size를 지정한 array를 선언하면, 다른 size 인 array 삽입 시 에러가 난다.
  • 복잡하게 template으로 만들어줘야 된다.
• 기본적으로 array 객체 전달 시 새로운 배열에 모든 원소가 deep copy 되므로 reference를 사용하면 좋다.

for (auto it = arr.begin(); it != arr.end(); it++)
{
	auto element = (*it);
    std::cout << element <<  ' ';
}

• 반복자, begin(), end()라는 멤버 변수를 제공하고 있으며 가장 첫 번째 원소, 마지막 원소의 위치를 반환하고 있다. 범위 기반 for문은 반복자 덕분에 사용 가능하다.
• const_iterator : 일반 iterator의 const version
  • const로 선언한 array에 iterator를 반환 받으면 const_iterator가 나온다.
• reverse_iterator : 역방향 이동 iterator
  • 이 반복자를 ++과 같은 연산자와 함께사용하면 반대 방향으로 이동하게 된다.
• front()
  • 배열 첫 번째 원소에 대한 참조 반환
• back()
  • 배열 마지막 원소에 대한 참조 반환
• data()
  • 실제 데이터 메모리 버퍼를 가리키는 pointer 반환 (예전 스타일 함수 사용시 유용)
• 배열은 관계 연산자 사용 시 두 배열의 크기가 같아야한다.

std::vector

• array의 단점
  • size는 컴파일 시간에 결정되어야 하는 상수
    • 프로그램 중간에 변경 불가
  • 메모리 할당 방법 변경 불가
    • 항상 stack 메모리 사용
• 대부분 응용프로그램에서 데이터는 동적이며 고정 크기 X
• vector는 가변 크기 배열이다.

std::vector<int> vec;

std::vector<int> vec = { 1, 2, 3, 4 };

# 크기가 10
std::vector<int> vec(10);

크기가 10, 모든 원소가 5로 초기화
std::vector<int> vec(10, 5);

• 원소 크기를 지정하지 않고 선언 가능
• 벡터 크기 명시적 지정 없을 경우 컴파일러에 따른 용량을 갖는 벡터 생성

원소 추가

• push_back()
  • 맨 마지막에 새로운 원소 추가
    • O(1)
  • vector의 size가 모두 차면 2*size 만큼 메모리 새로 할당
    • 새로 할당한 메모리로 기존 원소 전부 복사/이동
    • 데이터 포인터를 새로 할당한 메모리 주소로 지정
    • size가 모두 찬 상태의 push_back()이면 위 동작 이후 맨 뒤에 원소 삽입
    • 이 경우, O(n)
• insert()
  • 원하는 위치에 원소를 추가
  • 지정 반복자 위치 다음 모든 원소를 이동 시키는 연산 필요
    • 필요할 경우 메모리 새로 할당하는 작업도 수행
    • O(n)

vec.insert(vec.begin(), 0);

• vector는 push_front()를 지원하지 않아 insert를 사용해야 될 수도 있다.

vec.insert(find(vec.begin(), vec.end(), 1), 4);

• 1 앞에 4추가하는 예시다.
• push_back, insert는 추가할 원소를 먼저 임시로 생성한 후 벡터 버퍼 내부 위치로 복사 또는 이동을 수행한다.
  • emplace_back() or emplace()
    • 새 원소 위치에서 곧바로 객체가 생성되도록 최적화

원소 제거

• pop_back()
  • 맨 마지막 원소 제거
  • vector size - 1
• erase()
  • 반복자 하나를 받아 해당 위치 원소를 제거하는 방법, 시작과 끝을 나타내는 반복자를 받아 시작 부터 끝 바로 앞 원소까지 제거 하는 식으로 오버로딩 되어 있다.
  • 특정 위치 원소 삭제 후 뒤 쪽 원소들을 이동해야한다.
    • O(n)

유용한 함수

• clear() : 모든 원소 제거하여 완전히 비어있는 벡터로 만든다.
• reserve(capacity)
  • 벡터에서 사용할 용량 지정
  • 매개변수 값이 현재 용량보다 같거나 작으면 아무 동작하지 않고, 해당 용량보다 커야 동작한다.
• shrink_to_fit() : 여분의 메모리 공간을 해제하는 용도로 사용
  • 함수 호출 시 벡터 용량이 벡터 크기와 같게 설정
  • 벡터 크기가 더이상 변경되지 않을 때 사용하면 유용

할당자

• template 매개 변수에서 data type 다음에 allocator 전달 가능
  • array 단점 해결 가능
• 사용자 정의 할당자를 사용하려면 정해진 interface를 따라야한다.
  • 할당자는 allocate(), deallocate(), construct(), destoy() 등의 함수를 제공해야한다.
  • 자동 메모리 관리 및 자체적인 메모리풀을 사용하는 경우 유용하다.
• 평균적으로 벡터의 성능은 배열에 비해 그리 나쁘지 않다. 성능과 유연성으로 널리 사용되는 STL 컨테이너다.

std::forward_list

• 연속된 자료 구조에서는 데이터 중간에 자료를 추가하거나 삭제하는 작업이 매우 비효율적
• forward_list는 성능 유지를 위해 전체 리스트 크기 or 첫 번쨰 원소를 제외한 나머지 원소에 직접 접근하는 기능을 제공하지 않는다.
  • back() 함수 제공 X
• 원소 삽입, 삭제, 순서 뒤집기, 분할을 위한 기능 등은 제공한다.
  • 연결 리스트의 메모리 사용량, 성능에 영향 X

원소 삽입

std::forward_list<int> fwd_list =  {1, 2, 3};

fwd_list.push_front(0);

auto it = fwd_list.begin();

fwd_list.insert_after(it, 5);

• push_front()
  • forward_list는 마지막 원소에 직접 접근이 어려우므로 push_back()이 제공되지 않는다.
• insert_after()
  • 특정 위치에 원소 삽입 시 사용하는 함수다.
  • 새로운 원소 삽입 후 해당 위치 앞에 있는 원소의 next 포인트를 수정해야해서 해당 함수이름이 저따구다.
• 삽입 후 원소 이동이 필요없는 자료구조 이므로 배열 기반 구조보다 더 빠르게 작동한다.
  • 즉, 삽입 함수는 원소 크기에 영향을 받지 않는다. O(1)
• emplace_front(), emplace_after() 함수도 제공한다.
  • 앞에 배열에서의 설명과 마찬가지로 추갖거인 복사/이동을 거치지 않아 더 효율적이다.

원소 삭제

std::foward_list<int> fwd_list = {1, 2, 3, 4, 5};

fwd_list.pop_front();

auto it = fwd_list.begin();

fwd_list.erase_after(it);

fwd_list.erease_after(it, fwd_list.end()); // 맨 앞 원소 다음부터 맨 마지막원소까지 삭제

• pop_front()
  • 맨 처음 원소 제거
  • 원소 이동 필요 X -> O(1)
• erase_after()
  • 특정 원소를 가리키는 반복자를 인자로 받아 다음 위치 원소를 삭제

기타 멤버 함수

std::forward_list<citizen> citizens = {{"Kim", 22}, {"Lee", 25}};

citizens.revmoe_if([](const citizen &c) {
					return (c.age < 19);
}

• rmove()
  • 삭제할 원소 값 하나를 매개변수로 받는다.
  • 데이터 타입에 정의된 등호 연산자를 사용해 전달된 값과 일치하는 모든 원소를 찾아 삭제한다.
• remove_if()
  • remove()는 등호 연산에만 의존하므로 좀더 유연한 메서드가 필요
  • remove_if()는 뎅터 원소 값 하나를 인자로 받아 bool값을 반환하는 조건자 함수를 인자로 받는다.
  • 해당 조건자가 true를 반환하는 모든 데이터 원소를 리스트에서 삭제한다.
  • lambda expression 사용 가능
• 위 함수들은 원소 값을 검사해 삭제하는 멤버함수다.

std::forward_list<int> list = {23, 0, 1, -3};

list1.sort()

list1.sort(std::greater<int>());

• sort() : 원소 데이터 정렬
  • array 자료들은 std::sort(first_iter, last_iter) 함수를 통해 원소를 정렬할 수 있다. 하지만 연결 리스트 같은 자료 구조는 특정 원소에 임의 접근이 불가능해 std::sort() 함수를 사용할 수는 없다.
  • forawrd_list에서 제공하는 sort()는 < 연산자 기반, 다른 하나는 매개 변수로 전달된 comparator(비교자)를 사용하는 형태로 지원한다.
    • 비교자는 default로 std::less<value_type> 이다. -> 첫 번쨰 인자가 두 번쨰 보다 작으면 true를 반환하는 바교자 (< 연산자 래퍼임)
  • O(nlogn)

std::forward_list<int> list1 = { 2, 54, 1 };

list1.reverse();

list1.unique();

• reverse() : 저장된 원소의 순서를 역순으로 변경
  • O(n)
• unique() : 홀로 나타나는 원소는 놔두고, 인접해서 중복되는 원소에 대해 첫 번째만 남겨두고 나머지는 제거한다.
  • 인자가 없는 형태, 등호 연산자를 사용해 같은지 판단하는 형태 두 가지 형태로 제공된다.
  • 시간 복잡도가 선형인데, 이는 각각 우너소를 나머지 원소 전체와 비교하는 형태로 동작하지 않음을 암시한다.
  • 따라서 유일한 원소들만 남게 만들려면 먼저 리스트를 정렬한 후 unique() 함수를 사용해야된다.

반복자

• 배열과 벡터에서 사용되는 반복자는 기능 면에서 가장 유연한데, 연속된 자료 구조를 사용하므로 특정 위치의 원소에 곧바로 접근할 수 있기때문이다.
• forward:list 의 경우 기본적으로 역방향 이동 기능을 제공하지 않는다.
  • 이전 노드로 이동하려면 처음 노드부터 다시해서 찾아가야됨
  • 해당 반복자는 증가 연산만 가능하고, 이런 반복자를 forward iterator라고 한다.
• 반복자 타입에 따라 사용할 수 있는 함수 중 advance(), next(), prev()가 있다.
  • advance() : 반복자와 거리 값을 인자로 받고 반복자를 거리 만큼 증가시킨다.
  • next(), prev() : 반복자와 거리 값을 받아 해당 반복자에서 지정한 거리만큼 떨어진 위치의 반복자를 반환한다.
  • 해당 함수들은 해당 반복자가 지원하는 경우에만 동작한다.
    • 순방향 반복자에 대해서 prev() 함수 호출 시 에러 발생
  • 해당 함수들은 반복자 타입에따라 동작 시간이 결정된다.

advance()

auto it = vec.begin();

it += 8;

advance(it, -3);

• vec에서는 상수 시간으로 동작한다.

auto it = fwd.begin();

advance(it, 5);

• fwd iterator의 경우 선형 시간으로 동작한다. O(n)
• fwd iterator의 경우 -5 등의 음수 값을 사용하면 Error
• it += 2; 사용 시, operator+= 에 대해 지원하지 않는다는 Error

std::list

• std::forward_list는 단순 linked list의 래퍼 형태였다.
  • 유용한 기능 중 리스트 끝에 원소 추가, 역방향이동, 크기 반환 등을 제공하지 않았다.
    • 매우 적은 기능 제공
• 위를 해결하기 위해 std::list는 이중 연결 리스트(doubly-linked list)를 제공한다.

strcut doubly_linked_list_node
{
	int data;
    doubly_linked_list_node* next;
    doubly_linked_list_node* prev;
}

• 이중 연결 리스트 노드는 이전 노드도 가리키는 포인터가 추가로 있다.
  • 메모리가 forward_list 대비 약간 증가
  • 이 포인터를 욕해 역방향 이동 지원
  • push_back(), size() 함수를 지원

멤버함수

• insert(), emplace(), push_back(), emplace_back(), pop_back() 제공

std::list<int> list1 = {1, 2, 3, 4, 5};
list1.push_back(6); // 맨 뒤 6추가
list1.insert(next(list1.begin()), 0)); 맨 처음원소 다음에 0 추가
list1.insert(list1.end(), 7); // 맨 뒤 7추가

list1.pop_back(); // 맨 뒤 7 제거

• fwd_list와 이론적으로 함수 시간 복잡도는 같지만, std::list에서 좀 더 많은 연산이 필요
  • 두 개의 포인터를 갖고 있으면서 삽입, 삭제 연산 시 두 개의 포인트럴 관리해야하므로 대략 두배 연산을 수행해야하는 것을 추론할 수 있다.

양방향 반복자

• 배열 기반의 임의 접근 반복자와 fwd_list 기반 순방향 반복자의 중간 정도 유연성을 가지고 있다.
• 역방향 이동 가능(reverse iterator 사용 가능)
• 임의 접근 반복자 처럼 특정 위치로 한 번에 이동하는 것은 불가능
  • 이동 시 선형 시간 복잡도를 가진다.
• 어느 방향으로 움직일 수 있는 반복자여서 양방향 반복자라고 불릴 뿐이다.

반복자 무효화

auto v_it = vec.begin() + 4; // vec[4]

vec.insert(vec.begin() + 2, 0) // v_it 무효화

• vec의 경우 push_back은 새로 메모리 공간을 할당하고 기존 모든 원소를 새 메모리 공간으로 복사하는 동작이 발생하는 경우가 있다.
  • 이때, 기존 사용하던 모든 반복자, 포인터, 참조는 모두 무효화된다. -> 버그 및 에러 발생
• 위 코드의 경우 insert() 함수 수행 시 메모리 재할당이 필요한데, 원소 삽입 위치 이후 원소를 모두 이동해야하면서 이 위치를 가리키는 반복자는 무효화된다.

auto list_it = next(lst.begin(), 4);

list_it.insert(next(lst.begin(), 2), 0);

• linked list 류 에서는 삽입 또는 삭제 동작에서 원소 이동이 발생하지 않으므로 반복자가 무효화 되지 않는다.

---

• std::list는 sts::forward_list 보다 더 많은 함수를 제공하면서 시간 복잡도도 대부분 빠르다. 그래서 더 많이 사용된다. 메모리 또는 성능 최적화 하고 싶은 경우에만 forard_list를 제한적으로 사용하면 될 것 같다.

std::deque

• 배열 기반, 연결 리스트 기반이 섞여있는 형태
• 벡터는 가변 길이 배열이면서 push_froint(), pop_front() 등 비용이 많이 드는 경우가 있다. 이러한 단점을 극복할 수 있는 자료형이다.

구조

• C++ 표준
  • push_front(), pop_front(), push_back(), pop_back() 동작이 O(1) 으로 동작
  • 모든 원소에 대해 임의 접근 동작 O(1) 으로 동작
  • deque 중간에 원소 삽입 및 삭제는 O(n) 으로 동작, 실제로 최대 n/2 단계 동작
    • n : deque size
• deque은 양방향으로 매우 빠른 확장, 모든 원소에 임의 접근을 제공해야한다.
  • vec과 달리 앞, 뒤로 모두 확장
• n/2 단계 동작으로 보아 원소 중간 삽입 및 삭제 시 모든 원소 이동 동작을 수행함을 추론할 수 있다.
  • 원소를 항상 오른쪽으로 이동해야만하는 것은 아니다.
  • 원소 삽입 위치에서 가장 가까운 끝 쪽으로 나머지 원소를 이동해도 된다.
  • 특정 위치에서 가장 가까운 끝은 컨테이너 내부 삽입 위치에서 n/2 이상 떨어져있을 수 없으므로 최대 n/2 시간 복잡도를 가진다는 것이다.
• deque은 단일 매모리 청크를 사용하지 않는다.
  • 크기가 같은 여러 개의 메모리 청크를 사용해 데이터 저장
    • 청크 인덱스 및 크기를 통해 특정 위치의 원소가 어느 청크에 저장되어있는지 알 수 있는 것이다.
  • 메모리 청크 주소를 연속적인 메모리 구조에 저장해 놓고 사용하면 O(1) 의 시간 복잡도로 원소 임의 접근이 가능해 진다.
    • 임의 접근은 Vector 처럼 상수 complexity지만, 어떤 청크의 몇번째다라는 연산을 해야하므로 더 오래걸리는 연산이긴 하다.
    • 청크로 관리한다는 것은 vector에 비해 Cache locality가 낮을 수 있음에 유의
• deque 맨 앞에 new 원소 추가 시 첫 번째 메모리 청크에 여유 공간이 없다면 새로운 청크를 할당하고, 이 메모리 청크 주소를 맨 첫 번째 메모리 청크주소로 설정한다.
  • 청크 주소를 저장하는 메모리 공간을 새로 할당하지만 데이터 이동은 일어나지 않아도 된다.
  • 메모리 재할당을 최소화하려면 첫 청크부터 원소를 추가하지 않고, 중간 위치의 청크부터 원소를 저장할 수 있다. 이런 방식을 이용하면 일정 횏수의 push_front() 함수에 대해 메모리 재할당을 피할 수 있다.

std::deque<int> deq = {1, 2, 3, 4, 5};

deq.push_front(0);

deq.push_back(6);

deq.insert(deq.begin() + 2, 10);

deq.pop_back();

deq.pop_front();

deq.erase(deg.begin() + 1);

deq.erase(deq.begin() + 3, deq.end());

• deque은 데이터를 앞 뒤로 매우 빠르게 원소를 삽입하거나 삭제할 수 있다.
  • 벡터와 유사한 속도를 같지만 약간 빠르다.

컨테이너 어댑터

• 기존 컨테이너를 기반으로 만들어지는 컨테이너들이 있다.

  • 이는 코드에 좀 더 의미를 부여하고 싶거나 의도하지 않는 함수를 실수로 사용하지 못하도록 제한하고 싶거나, 특별한 인터페이스를 새롭게 제공하고 싶은 경우에 래핑한다.

  std::stack

  std::stack<int> stk;
  stk.push(1);
  stk.pop();
  stk.push(2);
  stk.pop_front(0); // 지원 X Error

• LIFO 구조

• 해당 구조의 명확성을 위해 사용, pop_front() 안되게 해보림

• std::deque으로 만든 간단한 래퍼로, 스택 자료형에 필요한 인터페이스만 제공

• emtpy(), size(), top() (<- back()), push(), pop() (<- pop_back()), emplace()

std::queue

• FIFO 구조

std::queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.pop();

• pop() (<- pop_front())

std::priority_queue

• heap이라고 부르는 매우 유용한 구조를 제공한다.
  • heap : 컨테이너에서 가장 작은(or 가장 큰) 원소에 빠르게 접근할 수 있는 자료 구조
• 최대/최소 원소에 접근하는 동작이 O(1)
• 원소 삽입 O(logn)
• 원소 제거는 최대/최소 원소에 대해서만 가능
• 최대/최소 한번에 빠르게 접근하는게 아니라 컨테이너 비교자에 의해 최대 or 최소에 빠르게 접근할지가 정해진다.
  • std::vector를 기본 컨테이너로 사용
  • 비교자는 std::less가 기본 (최대 힙)-> 최대 원소가 top
• 새로운 원소 삽입 시 최대 or 최소 원소가 최 상위에 위치되돍 하기 위해 단순히 기본 컨테이너 함수를 호출하는 형태로 도작할 수 없다. 대신 비교자를 사용해 최대 또는 최소 데이터를 맨 위 까지 끌어올리는 heapify 알고리즘을 구현해야 한다.
  • 이런 연산이 컨테이너 크기에 대해 O(logn) 소요
• 우선순위 큐 생성자는 O(n) 시간 복잡도로 빠르게 동작하는 다른 힙 생성 알고리즘으로 초기화한다.

어댑터 반복자

• 어댑터에 대해서는 반복자를 지원하지 않는다.
  • 모든 어댑터는 각 자료구조에서 꼭 필요한 기능만 지원 (모든 원소 순회 등 필요 X)