주어진 리스트가 있을 때, 그 리스트로 만들 수 있는 모든 부분 리스트(서브리스트)를 출력하는 프로그램을 작성해 보겠습니다. 이 문제는 파이썬의 슬라이싱(slicing) 기능과 중첩 반복문을 활용하면 아주 간단하게 해결할 수 있습니다.
예시
입력 : list = [1, 2, 3] 출력 : [], [1], [1, 2], [1, 2, 3], [2], [2, 3], [3]
[1, 2, 3]이라는 리스트는 빈 리스트를 포함해 총 7개의 서브리스트를 가질 수 있습니다. 일반적으로 길이가 n인 리스트는 빈 리스트를 포함하여 n(n+1)/2 + 1개의 서브리스트를 갖게 됩니다.
알고리즘
전체적인 풀이 흐름은 다음과 같습니다.
- 1단계 : 리스트를 하나 준비합니다.
- 2단계 : 처음에는 비어 있는 서브리스트를 저장할 리스트를 생성합니다.
- 3단계 : 리스트의 길이만큼 첫 번째 for 반복문을 실행합니다.
- 4단계 : i+1부터 리스트 길이까지 두 번째 반복문을 실행하여, 인덱스 i부터 오른쪽 끝까지의 모든 부분 배열을 구합니다.
- 5단계 : i부터 j까지 슬라이싱하여 부분 배열을 추출합니다.
- 6단계 : 추출한 부분 배열을 결과를 저장할 다른 리스트에 추가합니다.
- 7단계 : 마지막에 저장된 전체 결과를 출력합니다.
예제 코드
# 주어진 리스트에서
# 모든 서브리스트를 출력하는 파이썬 프로그램
# 모든 서브리스트를 생성하는 함수
def displaysublist(A):
# 모든 서브리스트를 저장할 리스트
B = [[]]
# 첫 번째 반복문
for i in range(len(A) + 1):
# 두 번째 반복문
for j in range(i + 1, len(A) + 1):
# i부터 j까지 부분 배열을 슬라이싱
sub = A[i:j]
B.append(sub)
return B
# 드라이버 코드
A = list()
n = int(input("첫 번째 리스트의 크기를 입력하세요 :: "))
print("첫 번째 리스트의 요소를 입력하세요 :: ")
for i in range(int(n)):
k = int(input(""))
A.append(k)
print("서브리스트 ::>", displaysublist(A))
실행 결과
첫 번째 리스트의 크기를 입력하세요 :: 3 첫 번째 리스트의 요소를 입력하세요 :: 1 2 3 서브리스트 ::> [[], [1], [1, 2], [1, 2, 3], [2], [2, 3], [3]]
코드 동작 원리
핵심은 두 개의 중첩된 반복문입니다. 바깥쪽 반복문 변수 i는 서브리스트의 시작 인덱스를, 안쪽 반복문 변수 j는 끝 인덱스를 담당합니다. A[i:j] 슬라이싱을 통해 시작점은 고정한 채 끝점을 하나씩 늘려가며 가능한 모든 연속 구간을 추출합니다.
예를 들어 i = 0일 때는 [1], [1, 2], [1, 2, 3]이 차례대로 생성되고, i = 1일 때는 [2], [2, 3], i = 2일 때는 [3]이 생성됩니다. 여기에 초기값으로 넣어 둔 빈 리스트 []까지 합쳐져 총 7개의 서브리스트가 완성됩니다.
이 방식의 시간 복잡도는 서브리스트의 개수가 O(n²)개이고 각 슬라이싱에 O(n)이 걸리므로 전체적으로 O(n³)입니다. 리스트의 크기가 크지 않다면 충분히 실용적인 접근 방법입니다.