[WEEK01] 리스트 컴프리헨션과 집합

리스트 컴프리헨션 (List Comprehension)

리스트 컴프리헨션은 파이썬에서 리스트를 간결하고 효율적으로 생성하는 방법이다. 일반적인 for 루프를 사용한 리스트 생성보다 더 짧고 읽기 쉽게 코드를 작성할 수 있다는 장점이 있다.

[표현식 for 항목 in iterable]

 

"ABC"를 한 글자씩 배열에 넣고 싶다고 가정하자. 반복문을 사용하면 다음과 같이 코드를 작성해야 한다.

str = "ABC"
arr1 = []
for i in range(len(str)):
    arr1.append(str[i])
print(arr1)

 

반면, 리스트 컴프리헨션을 사용하면 다음과 같이 더 간결하게 작성할 수 있다.

str = "ABC"
arr2 = [i for i in str]
print(arr2)

 

리스트 컴프리헨션은 내부적으로 최적화되어 있어 일반적으로 for 문보다 더 빠르게 실행된다. 특히 큰 데이터셋을 처리할 때 성능 차이가 더 두드러질 수 있다. 또한 리스트 컴프리헨션은 추가적으로 조건을 걸 수 있어 특정 조건만을 만족시키는 요소만 리스트에 추가할 수 있다.

arr = [i for i in str if i in 'ACE']
print(arr)

 

여러 줄에 걸친 입력을 받아야 할 때에도 리스트 컴프리헨션을 사용할 수 있다.

import sys
arr3 = [sys.stdin.readline() for _ in range(5)]
print(arr3)

 

시간 복잡도, 공간 복잡도 자체는 모두 O(n)으로 동일하지만, 리스트 컴프리헨션이 for문보다 내부적으로 더 최적화되어 있기 때문에 조금 더 빠르다.

---

집합 (Set)

집합은 순서가 없는 고유한 요소의 집합이다. 주요한 특징은 다음과 같다.

• 중복된 요소를 허용하지 않음
• 인덱스를 사용하지 않음
• 변경 가능한 데이터 구조

my_set = {1, 2, 2, 3, 4}
print(my_set)

 

집합은 중복을 허용하지 않기 때문에 출력은 {1, 2, 3, 4} 로 된다.

집합과 리스트의 차이

백준 단어 정렬 문제에서 list를 사용했을 때보다 set을 사용했을 때가 연산 속도 8배 정도 더 빨랐다.

n = int(input())
arr = list()
for _ in range(n):
    word = input()
    if word not in arr:
        arr.append(word)
arr.sort(key=lambda x: (len(x), x))
for i in range(len(arr)):
    print(arr[i])

n = int(input())
arr = set()
for _ in range(n):
    arr.add(input())
arr = sorted(arr, key=lambda x: (len(x), x))
for i in range(len(arr)):
    print(arr[i])

 

Set이 List보다 더 빠른 탐색 속도를 가지는 이유로는 크게 두 가지를 들 수 있다.

• 데이터 구조
  - Set은 해시 테이블(Hash table)로 구현되어 있어 중복된 값을 허용하지 않으며, O(1)의 시간 복잡도를 가진다.
  - List는 배열(Array)로 구현되어 있어 최소 O(1)에서 최대 O(n)의 시간 복잡도를 가진다.
• 탐색 알고리즘
  - Set에서 값의 존재 여부를 확인하는 연산은 내부적으로 해시 함수와 bucket을 사용하기 때문에 O(1)의 시간 복잡도를 가진다.
  - List에서 값의 존재 여부를 확인하기 위해서는 순차적인 비교 연산을 수행해야 하기 때문에 worst-case의 경우 O(n)의 시간 복잡도를 가진다.

타입	데이터 구조 구현	탐색 알고리즘	특징
Set	Hash Table	해시 함수, 버킷	중복 제거
List	Array	완전탐색	인덱싱 가능

 

위와 같은 이유로 집합이 리스트보다 시간적 측면에서 이점을 가지지만, 순서가 보장되지 않으며 인덱스를 사용할 수 없다는 단점도 존재한다.