리스트 초고급 20문제 (코드골프 + 알고리즘 응용)
문제 + 핵심 아이디어 + 예시 코드 + 풀이 설명을 한 번에 볼 수 있는 학교 제출용 HTML 자료
구성 안내
- 총 20문제:
코드골프 5문제 + 알고리즘 응용 15문제
- 각 문제마다 목표, 예시, 힌트, 예시 코드, 설명 포함
- 리스트 슬라이싱, 컴프리헨션, 정렬, 누적합, 투 포인터, DP, 그래프 탐색까지 단계적으로 확장
코드골프
1. 리스트 뒤집기 최단 표현
문제 목표: 리스트 a를 가장 짧고 직관적으로 뒤집어 새로운 리스트를 만드시오.
예시: 입력: a = [1,2,3,4,5] → 출력: [5,4,3,2,1]
힌트: 슬라이싱의 step을 음수로 주면 역방향 순회가 가능합니다.
예시 코드
a = [1,2,3,4,5]
print(a[::-1])
설명: a[::-1]은 처음부터 끝까지 한 칸씩 거꾸로 읽는 가장 대표적인 리스트 역순 표현입니다.
코드골프
2. 짝수만 추출하는 한 줄 코드
문제 목표: 1부터 20까지 중 짝수만 리스트로 만드시오.
예시: 출력: [2, 4, 6, ..., 20]
힌트: 리스트 컴프리헨션과 나머지 연산을 함께 사용해 보세요.
예시 코드
print([x for x in range(1,21) if x%2==0])
설명: 조건식 if x%2==0 으로 짝수만 통과시켜 한 줄로 생성합니다.
코드골프
3. 중복 제거 후 정렬
문제 목표: 리스트에서 중복을 제거하고 오름차순 정렬하시오.
예시: 입력: [3,1,2,3,2,5,1] → 출력: [1,2,3,5]
힌트: set으로 중복 제거, sorted로 정렬이 가능합니다.
예시 코드
a = [3,1,2,3,2,5,1]
print(sorted(set(a)))
설명: set(a)로 중복을 없애고 sorted(...)로 정렬한 새 리스트를 만듭니다.
코드골프
4. 리스트 평탄화
문제 목표: 2차원 리스트를 1차원 리스트로 평탄화하시오.
예시: 입력: [[1,2],[3,4],[5]] → 출력: [1,2,3,4,5]
힌트: 중첩 for를 리스트 컴프리헨션 안에 넣어 보세요.
예시 코드
a = [[1,2],[3,4],[5]]
print([x for row in a for x in row])
설명: 바깥 리스트의 각 row를 순회하고, 다시 row 내부 원소 x를 꺼내 이어 붙입니다.
코드골프
5. 최빈값 후보 찾기
문제 목표: 리스트에서 가장 많이 등장한 값을 구하시오.
예시: 입력: [1,2,2,3,3,3,4] → 출력: 3
힌트: key=a.count 를 활용하면 짧게 쓸 수 있습니다.
예시 코드
a = [1,2,2,3,3,3,4]
print(max(a, key=a.count))
설명: 각 원소의 등장 횟수를 기준으로 최대값을 찾습니다.
알고리즘 응용
6. 회전 이동
문제 목표: 리스트를 오른쪽으로 k칸 회전시키시오.
예시: 입력: [1,2,3,4,5], k=2 → 출력: [4,5,1,2,3]
힌트: 슬라이싱 두 조각을 이어 붙이면 됩니다.
예시 코드
a = [1,2,3,4,5]; k = 2
k %= len(a)
print(a[-k:] + a[:-k])
설명: 뒤쪽 k개와 앞쪽 나머지를 이어 붙여 회전 결과를 만듭니다.
알고리즘 응용
7. 투 포인터로 두 수의 합
문제 목표: 정렬된 리스트에서 합이 target인 두 수를 찾으시오.
예시: 입력: [1,2,4,7,11,15], target=15 → 출력: (4,11)
힌트: 왼쪽과 오른쪽 끝에서 동시에 좁혀 가는 방법을 사용해 보세요.
예시 코드
a = [1,2,4,7,11,15]; target = 15
l, r = 0, len(a)-1
while l < r:
s = a[l] + a[r]
if s == target:
print((a[l], a[r]))
break
l, r = (l+1, r) if s < target else (l, r-1)
설명: 합이 작으면 왼쪽을 키우고, 크면 오른쪽을 줄이는 투 포인터 기법입니다.
알고리즘 응용
8. 누적합 배열 만들기
문제 목표: 각 위치까지의 누적합을 저장한 리스트를 만드시오.
예시: 입력: [3,1,4,1,5] → 출력: [3,4,8,9,14]
힌트: 이전 합을 계속 더해 가면 됩니다.
예시 코드
a = [3,1,4,1,5]
s = 0
prefix = []
for x in a:
s += x
prefix.append(s)
print(prefix)
설명: 현재까지 합을 s에 저장하고 append로 순서대로 누적합 리스트를 만듭니다.
알고리즘 응용
9. 최대 부분합 (Kadane)
문제 목표: 연속된 부분 리스트의 합 중 최대값을 구하시오.
예시: 입력: [-2,1,-3,4,-1,2,1,-5,4] → 출력: 6
힌트: 현재 구간의 최적값과 전체 최적값을 따로 관리합니다.
예시 코드
a = [-2,1,-3,4,-1,2,1,-5,4]
cur = best = a[0]
for x in a[1:]:
cur = max(x, cur + x)
best = max(best, cur)
print(best)
설명: 현재 위치에서 새로 시작할지, 이전 구간에 이어 붙일지를 비교하는 대표 알고리즘입니다.
알고리즘 응용
10. 에라토스테네스의 체
문제 목표: n 이하의 소수를 모두 리스트로 구하시오.
예시: 입력: n=30 → 출력: [2,3,5,7,11,13,17,19,23,29]
힌트: 배수들을 지워 나가면 됩니다.
예시 코드
n = 30
s = [True]*(n+1)
s[0]=s[1]=False
for i in range(2, int(n**0.5)+1):
if s[i]:
for j in range(i*i, n+1, i):
s[j] = False
print([i for i,v in enumerate(s) if v])
설명: 소수의 배수를 제거하는 방식으로 전체 소수 목록을 효율적으로 구합니다.
알고리즘 응용
11. 리스트 압축 (Run-Length Encoding)
문제 목표: 연속해서 반복되는 값을 (값, 개수) 형태로 압축하시오.
예시: 입력: [1,1,1,2,2,3,1,1] → 출력: [(1,3),(2,2),(3,1),(1,2)]
힌트: 이전 값과 현재 값을 비교하며 개수를 세면 됩니다.
예시 코드
a = [1,1,1,2,2,3,1,1]
res = []
cur, cnt = a[0], 1
for x in a[1:]:
if x == cur:
cnt += 1
else:
res.append((cur, cnt))
cur, cnt = x, 1
res.append((cur, cnt))
print(res)
설명: 같은 값이 이어지는 구간의 길이를 세어서 압축 표현으로 바꿉니다.
알고리즘 응용
12. 행렬 전치
문제 목표: 2차원 리스트 행렬을 전치하시오.
예시: 입력: [[1,2,3],[4,5,6]] → 출력: [[1,4],[2,5],[3,6]]
힌트: zip(*matrix)가 핵심입니다.
예시 코드
m = [[1,2,3],[4,5,6]]
print([list(row) for row in zip(*m)])
설명: zip(*m)은 각 행의 같은 위치 원소들을 묶어 열을 행으로 바꿔 줍니다.
알고리즘 응용
13. 달팽이 순회 기초
문제 목표: 2차원 리스트를 바깥에서 안쪽으로 시계 방향 순회하시오.
예시: 입력: [[1,2,3],[4,5,6],[7,8,9]] → 출력: [1,2,3,6,9,8,7,4,5]
힌트: 맨 윗줄을 꺼내고 나머지를 회전시키는 아이디어가 있습니다.
예시 코드
a = [[1,2,3],[4,5,6],[7,8,9]]
res = []
while a:
res += a.pop(0)
a = [list(row) for row in zip(*a)][::-1] if a else []
print(res)
설명: 윗줄을 제거한 뒤 나머지 부분을 반시계 회전시키며 같은 작업을 반복합니다.
알고리즘 응용
14. 병합 정렬
문제 목표: 리스트를 병합 정렬로 정렬하시오.
예시: 입력: [5,2,4,6,1,3] → 출력: [1,2,3,4,5,6]
힌트: 분할 정복으로 반씩 나누고 정렬된 두 리스트를 합칩니다.
예시 코드
def merge_sort(a):
if len(a) < 2: return a
m = len(a)//2
l, r = merge_sort(a[:m]), merge_sort(a[m:])
res = []; i = j = 0
while i < len(l) and j < len(r):
if l[i] < r[j]: res.append(l[i]); i += 1
else: res.append(r[j]); j += 1
return res + l[i:] + r[j:]
print(merge_sort([5,2,4,6,1,3]))
설명: 리스트를 계속 반으로 나눈 뒤, 정렬된 결과를 다시 합치는 전형적인 O(n log n) 정렬입니다.
알고리즘 응용
15. 이진 탐색
문제 목표: 정렬된 리스트에서 target의 위치를 찾으시오.
예시: 입력: [1,3,5,7,9], target=7 → 출력: 3
힌트: 중간값과 target을 비교하며 탐색 범위를 절반씩 줄입니다.
예시 코드
a = [1,3,5,7,9]; target = 7
l, r = 0, len(a)-1
while l <= r:
m = (l+r)//2
if a[m] == target:
print(m)
break
elif a[m] < target:
l = m+1
else:
r = m-1
설명: 정렬된 리스트에서는 절반씩 버려 가며 매우 빠르게 값을 찾을 수 있습니다.
알고리즘 응용
16. 슬라이딩 윈도우 최대 합
문제 목표: 길이 k인 연속 구간의 합 중 최대값을 구하시오.
예시: 입력: [2,1,5,1,3,2], k=3 → 출력: 9
힌트: 처음 구간 합을 구한 뒤 한 칸씩 밀면서 갱신합니다.
예시 코드
a = [2,1,5,1,3,2]; k = 3
s = sum(a[:k]); best = s
for i in range(k, len(a)):
s += a[i] - a[i-k]
best = max(best, s)
print(best)
설명: 매번 다시 더하지 않고, 들어오는 값은 더하고 빠지는 값은 빼는 방식으로 최적화합니다.
알고리즘 응용
17. 순열 생성
문제 목표: 리스트 원소의 모든 순열을 생성하시오.
예시: 입력: [1,2,3] → 출력: 6개의 순열
힌트: itertools.permutations를 사용할 수 있습니다.
예시 코드
from itertools import permutations
a = [1,2,3]
print(list(permutations(a)))
설명: 순열은 원소들의 모든 가능한 순서 배열을 의미합니다.
알고리즘 응용
18. LIS 길이 구하기 기초
문제 목표: 최장 증가 부분 수열의 길이를 구하시오.
예시: 입력: [10,9,2,5,3,7,101,18] → 출력: 4
힌트: 기초 단계에서는 DP로 접근할 수 있습니다.
예시 코드
a = [10,9,2,5,3,7,101,18]
dp = [1]*len(a)
for i in range(len(a)):
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j]+1)
print(max(dp))
설명: 각 위치를 마지막으로 하는 증가 부분 수열의 최대 길이를 저장하며 갱신합니다.
알고리즘 응용
19. BFS 큐 기초
문제 목표: 그래프를 너비 우선 탐색으로 순회하시오.
예시: 그래프: 1-[2,3], 2-[4], 3-[4], 4-[]
힌트: 리스트보다 deque가 더 적합하지만 원리를 보기 위해 리스트 큐로도 구현 가능합니다.
예시 코드
g = {1:[2,3], 2:[4], 3:[4], 4:[]}
q = [1]; seen = {1}
order = []
while q:
v = q.pop(0)
order.append(v)
for nv in g[v]:
if nv not in seen:
seen.add(nv)
q.append(nv)
print(order)
설명: 먼저 들어간 정점을 먼저 꺼내며 가까운 정점부터 차례대로 방문합니다.
알고리즘 응용
20. 스택으로 괄호 검사
문제 목표: 괄호 문자열이 올바른지 판별하시오.
예시: 입력: '(()())' → 출력: True
힌트: 여는 괄호를 push하고 닫는 괄호가 나오면 pop합니다.
예시 코드
s = '(()())'
st = []
ok = True
for ch in s:
if ch == '(':
st.append(ch)
else:
if not st:
ok = False
break
st.pop()
print(ok and not st)
설명: 닫는 괄호가 나왔을 때 대응되는 여는 괄호가 없으면 잘못된 문자열입니다.