효율적인 탐색을 위한 자료구조: 리스트와 세트 비교

1. 리스트와 세트의 정의

• 리스트 (List): 순서가 있는 데이터의 집합으로, 중복된 값을 허용하며, 인덱스를 통해 접근할 수 있다.
• 세트 (Set): 순서가 없고, 중복된 값을 허용하지 않는 데이터의 집합이다. 해시 테이블을 기반으로 구현되어 있어, 평균적으로 탐색 시간이 빠르다.

2. 탐색 성능 비교

리스트에서 특정 요소를 찾는 과정은 순차적으로 모든 요소를 비교해야 하므로 **O(N)**의 시간 복잡도를 가진다. 반면, 세트는 해시 함수를 사용하여 특정 요소를 빠르게 찾을 수 있어 평균적으로 **O(1)**의 시간 복잡도를 가진다.

3. 예제 코드

아래 코드는 두 개의 리스트를 비교하여, 두 번째 리스트의 각 요소가 첫 번째 리스트에 존재하는지를 확인하는 간단한 예시이다. 이 예제에서 리스트를 세트로 변환하여 탐색 성능을 향상시킨다.

바꾸기 전 코드 (백준 1920번, 시간초과)

# 정수 N 입력받기
N = int(input())
# N개의 정수를 입력받아 리스트로 변환
N_list = list(map(int, input().split()))

# 정수 M 입력받기
M = int(input())
# M개의 정수를 입력받아 리스트로 변환
M_list = list(map(int, input().split()))
M_len = len(M_list)  # M_list의 길이를 저장 (필요하지 않다면 삭제 가능)

# M_list의 각 요소가 N_list에 있는지 확인
for i in M_list:
    if i in N_list:  # 리스트 N_list에서 i가 존재하는지 확인
        print('1')  # 요소가 N_list에 있으면 '1' 출력
    else:
        print('0')  # 요소가 N_list에 없으면 '0' 출력

바꾸고 난 후 코드 (리스트를 세트로 변환)

# 정수 N 입력받기
N = int(input())
# N개의 정수를 입력받아 리스트로 변환
N_list = list(map(int, input().split()))

# 정수 M 입력받기
M = int(input())
# M개의 정수를 입력받아 리스트로 변환
M_list = list(map(int, input().split()))

# N_list를 세트로 변환하여 중복을 제거하고 탐색 성능 향상
N_set = set(N_list)

# M_list의 각 요소가 N_set에 있는지 확인
for i in M_list:
    if i in N_set:
        print('1')  # 요소가 N_set에 있으면 '1' 출력
    else:
        print('0')  # 요소가 N_set에 없으면 '0' 출력

 

 

4. 코드 설명

1. 입력: 먼저 두 개의 리스트를 입력받는다. N_list는 탐색 대상이 되는 리스트이고, M_list는 탐색할 값들을 포함한다.
2. 세트 변환: N_list를 세트로 변환하여 N_set을 만든다. 이 과정에서 중복된 값이 제거된다.
3. 탐색: M_list의 각 요소에 대해 N_set에 존재하는지를 확인하고, 존재하면 '1', 그렇지 않으면 '0'을 출력한다.

5. 결론

리스트와 세트는 각각의 사용 목적에 맞게 적절히 선택해야 한다. 만약 중복된 값을 허용해야 하거나 순서가 중요한 경우 리스트를 사용하고, 빠른 탐색이 필요한 경우 세트를 사용하는 것이 좋다. 이처럼 자료 구조의 선택은 알고리즘의 효율성을 크게 좌우할 수 있다는걸 알았다.