kjp0411 님의 블로그
자료구조 - 배열과 리스트, 구간 합, 투 포인터, 슬라이딩 윈도우 본문
자료구조는 데이터를 효율적으로 저장, 접근, 수정하기 위한 그릇입니다.
기본 자료구조인 배열과 리스트는 비슷한 점도 많지만 다른 점도 많습니다.
파이썬에서는 리스트가 배열의 특성도 함께 내포하고 있어 크게 구분하여 사용하지는 않습니다.
배열과 리스트의 핵심 이론
배열: 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조를 의미
- 배열의 값은 인덱스를 통해 참조할 수 있음
- 선언한 자료형의 값만 저장할 수 있음
배열의 특징
- 인덱스를 사용하여 값에 바로 접근할 수 있음
- 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어려움
- (값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요)
- 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없음
- 구조가 간단하므로 코딩 테스트에서 많이 사용됨
리스트: 값과 포인터를 묶은 노드라는 것을 포인더로 연결한 자료구조를 의미
리스트의 특징
- 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야 하므로 값에 접근하는 속도가 느림
- 포인터로 연결되어 있으므로 데이터를 삽입거나 삭제하는 연산 속도가 빠름
- 선언할 때 크기를 별도로 지정하지 않아도 됨
- (리스트의 크기는 정해져 있지 않으며, 크기가 변하기 쉬운 데이터를 다룰 때 적절함)
- 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡함
001 문제 : 숫자의 합 구하기
https://www.acmicpc.net/problem/11720
문제 분석하기
해당 문제는 파이썬의 리스트 자료구조를 통해 쉽게 해결할 수 있습니다.
주어진 숫자를 리스트의 형태로 저장한 뒤 해당 리스트를 index를 이용해 탐색하면서 각 자릿수의 값을 더하면 됩니다.
자릿수를 더할 때는 정수형으로 변환해 더합니다.
코드 구현하기
# https://www.acmicpc.net/problem/11720
N = int(input())
numbers = list(input())
sum = 0
for i in numbers:
sum += int(i)
print(sum)
파이썬에서의 형 변환
| int, float, str, chr, bool | ||
| int 형 변환 | int(data) | # float, bool 변환 가능 |
| float 형 변환 | float(data) | # int, bool 변환 가능 |
| str 형 변환 | str(data) | # int, float, bool, chr 변환 가능 |
| chr 형 변환 | chr(data) | # int, bool 변환 가능 |
| bool 형 변환 | bool(data) | # int, float, str, chr 변환 가능 |
※ bool 형 변환인 경우 int, float에서 변환할 때는 데이터가 0인지 아닌지에 따라,
chr와 str에서 변환할 때는 값이 비어 있는지 아닌지에 따라 True, False를 반환합니다.
002 문제 : 평균 구하기
https://www.acmicpc.net/problem/1546
문제 분석하기
최고 점수를 기준으로 전체 점수를 다시 계산해야 하므로 모든 점수를 입력받은 후에 최고점을 별도로 저장해야 합니다.
문제에서 제시한 한 과목의 점수를 계산하는 식은 총합과 관련된 식으로 변환할 수 있습니다.
따라서 일일이 변환 점수를 구할 필요 없이 한 번에 변환한 점수의 평균 점수를 구할 수 있습니다.
변환 점수의 평균을 구하는 식(점수가 A, B, C인 경우)
(A / M * 100 + B / M * 100 + C / M * 100) / 3 = (A + B + C) * 100 / M / 3
코드 구현하기
# https://www.acmicpc.net/problem/1546
N = int(input())
grades = list(map(int, input().split()))
max_grade = max(grades)
average = sum(grades) * 100 / max_grade / N
print(average)
003 문제 : 구간 합 구하기 1
https://www.acmicpc.net/problem/11659
문제 분석하기
문제에서 수의 개수와, 합을 구해야 하는 횟수는 최대 100,000입니다.
여기서 구간마다 합을 매번 계산하면 0.5초 안에 모든 계산을 끝낼 수 없습니다.
이럴 때 바로 구간 합을 이용해야 합니다.
합 배열 S 정의
S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]
합 배열 S를 만드는 공식
S[i] = s[i-1] + A[i]
구간 합을 구하는 공식
s[j] - s[i-1]
A[2] ~ A[5] 구간 합을 합 배열로 구하는 과정
S[5] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5]
S[1] = A[0] + A[1]
S[5] - S[1] = A[2] + A[3] + A[4] + A[5]
코드 구현하기
# https://www.acmicpc.net/problem/11659
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
numbers = list(map(int, input().split()))
prefix_sum = [0]
temp = 0
for i in numbers:
temp = temp + i
prefix_sum.append(temp) # 합 배열 만들기
for _ in range(M):
i, j = map(int, input().split())
print(prefix_sum[j] - prefix_sum[i - 1]) # 합 배열에서 구간 합 구하기
004 문제 : 구간 합 구하기 2
https://www.acmicpc.net/problem/11660
문제 분석하기
먼저 질의의 개수가 100,000이므로 이 문제 역시 질의마다 합을 구하면 안되고, 구간 합 배열을 이용해야 합니다.
구간 합 배열이 1차원에서 2차원으로 확장된 것으로 생각하여 구간 합 배열을 구성하면 됩니다.
2차원 구간 합 배열 D[X][Y] 정의
D[X][Y] = 원본 배열의 (0, 0)부터 (X, Y)까지의 사각형 영역 안에 있는 수의 합
D[i][j]의 값을 채우는 구간 합 공식
D[]
코드 구현하기
# https://www.acmicpc.net/problem/11660
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = [[0] * (N + 1)]
D = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N):
A_row = [0] + [int(x) for x in input().split()]
A.append(A_row)
for i in range(1, N + 1):
for j in range(1, N + 1):
D[i][j] = D[i-1][j] + D[i][j-1] - D[i-1][j-1] + A[i][j]
for _ in range(M):
x1, y1, x2, y2 = map(int, input().split())
result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]
print(result)
005 문제 : 구간 합 구하기 2
https://www.acmicpc.net/problem/10986
문제 분석하기
N의 최댓값이 10⁶ 이라 연산량이 작게 느껴질 수 있습니다.
하지만 10⁶의 수에 대하여 모든 구간 합을 구해야 하므로 1초 안에 연산하기는 어렵습니다.
여기서도 구간 합 배열을 이용해야 합니다.
나머지 합 문제 풀이의 핵심 아이디어
- (A + B) % C는 ((A % C) + (B % C)) % C와 같다.
- 다시 말해 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합에 나머지 연산을 한 값은 동일하다.
- 구간 합 배열을 이용한 식 S[j] - S[i]는 원본 리스트의 i+1 부터 j까지의 구간 합이다.
- S[j] % M의 값과 S[i] % M의 값이 같나면 (S[j] - S[i]) % M은 0이다.
- 즉, 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트하고 S[j]와 S[i]가 같은 (i, j)쌍을 찾으면
- 원본 리스트에서 i + 1부터 j까지의 구간 합이 M으로 나누어떨어진다는 것을 알 수 있다.
코드 구현하기
# https://www.acmicpc.net/problem/10986
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * N
C = [0] * M
S[0] = A[0]
answer = 0
for i in range(1, N):
S[i] = S[i-1] + A[i]
for i in range(N):
remainder = S[i] % M
if remainder == 0:
answer += 1
C[remainder] += 1
for i in range(M):
if C[i] > 1:
answer += (C[i] * (C[i] - 1) // 2)
print(answer)
006 문제 : 연속된 자연수의 합 구하기
https://www.acmicpc.net/problem/2018
문제 분석하기
이 문제는 시간 복잡도 분석으로 사용할 알고리즘의 범위부터 줄여야 합니다.
문제에 주어진 시간 제한은 2초입니다. 그런데 N의 최댓값은 10,000,000으로 매우 크게 잡혀 있습니다.
이런 상황에서 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 시간을 초과하므로 O(n)의 시간 복잡도 알고리즘을 사용해야 합니다.
이런 경우 자주 사용하는 방법이 투 포인터입니다.
연속된 자연수의 합을 구하는 문제이므로 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현합니다.
코드 구현하기
# https://www.acmicpc.net/problem/2018
N = int(input())
count, start_idx, end_idx, sum_value = 1, 1, 1, 1
while end_idx != N:
if sum_value == N:
count += 1
end_idx += 1
sum_value += end_idx
elif sum_value > N:
sum_value -= start_idx
start_idx += 1
else:
end_idx += 1
sum_value += end_idx
print(count)https://www.acmicpc.net/problem/1940
코드 구현하기
# https://www.acmicpc.net/problem/1940
import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
A = list(map(int, input().split()))
A.sort()
count = 0
i = 0
j = N-1
while i < j:
if A[i] + A[j] < M:
i += 1
elif A[i] + A[j] > M:
j -= 1
else:
count += 1
i += 1
j -= 1
print(count)https://www.acmicpc.net/problem/1253
코드 구현하기
# https://www.acmicpc.net/problem/1253
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort()
count = 0
for k in range(N):
find = A[k]
i = 0
j = N - 1
while i < j:
if A[i] + A[j] == find:
if i != k and j != k:
count += 1
break
elif i == k:
i += 1
elif j == k:
j -= 1
elif A[i] + A[j] < find:
i += 1
else:
j -= 1
print(count)https://www.acmicpc.net/problem/12891
코드 구현하기
# https://www.acmicpc.net/problem/12891
checkList = [0] * 4
myList = [0] * 4
checkSecret = 0
# 함수 정의
def myadd(c): # 새로 들어온 문자를 처리하는 함수
global checkList, myList, checkSecret
if c == 'A':
myList[0] += 1
if myList[0] == checkList[0]:
checkSecret += 1
elif c == 'C':
myList[1] += 1
if myList[1] == checkList[1]:
checkSecret += 1
elif c == 'G':
myList[2] += 1
if myList[2] == checkList[2]:
checkSecret += 1
elif c == 'T':
myList[3] += 1
if myList[3] == checkList[3]:
checkSecret += 1
def myremove(c): # 제거되는 문자를 처리하는 함수
global checkList, myList, checkSecret
if c == 'A':
if myList[0] == checkList[0]:
checkSecret -= 1
myList[0] -= 1
elif c == 'C':
if myList[1] == checkList[1]:
checkSecret -= 1
myList[1] -= 1
elif c == 'G':
if myList[2] == checkList[2]:
checkSecret -= 1
myList[2] -= 1
elif c == 'T':
if myList[3] == checkList[3]:
checkSecret -= 1
myList[3] -= 1
S, P = map(int, input().split())
Result = 0
A = list(input())
checkList = list(map(int, input().split()))
for i in range(4):
if checkList[i] == 0:
checkSecret += 1
for i in range(P):
myadd(A[i])
if checkSecret == 4:
Result += 1
for i in range(P, S):
j = i - P
myadd(A[i])
myremove(A[j])
if checkSecret == 4:
Result += 1
print(Result)https://www.acmicpc.net/problem/11003
코드 구현하기
# https://www.acmicpc.net/problem/11003
from collections import deque
N, L = map(int, input().split())
mydeque = deque()
now = list(map(int, input().split()))
# 새로운 값이 들어올 때마다 정렬 대신 현재 수보다 큰 값을 덱에서 제거해 시간 복잡도를 줄임
for i in range(N):
while mydeque and mydeque[-1][0] > now[i]:
mydeque.pop()
mydeque.append((now[i], i))
if mydeque[0][1] <= i - L:
mydeque.popleft()
print(mydeque[0][0], end=' ')'Coding Test > Python' 카테고리의 다른 글
| 자료구조 - 버블 정렬, 선택 정렬 (0) | 2025.09.12 |
|---|---|
| 자료구조 - 스택과 큐 (0) | 2025.09.11 |
| 미리 보는 코딩 테스트 오답 노트 (0) | 2025.09.09 |
| 코딩 테스트 준비하기 (1) | 2025.09.08 |
| 프로그래머스 문제 : 신규 아이디 추천 (0) | 2025.06.30 |