왜 배열과 문자열에서 시작할까
많은 알고리즘 문제는 여러 개의 값을 다루는 일에서 출발합니다. 시험 점수 목록, 하루별 방문자 수, 상품 가격표, 문장 속 글자들처럼 값이 하나가 아니라 여러 개일 때가 많습니다. 이때 가장 먼저 만나는 자료 형태가 배열과 문자열입니다.
배열은 여러 값을 순서대로 담아 둔 상자 줄이라고 생각하면 됩니다. 첫 번째 상자, 두 번째 상자처럼 위치가 있고, 우리는 그 위치를 이용해 값을 꺼냅니다. 문자열은 글자들이 순서대로 이어진 값입니다. 겉으로는 하나의 문장처럼 보이지만, 알고리즘에서는 문자들이 나열된 배열처럼 다루는 경우가 많습니다.
예를 들어 다음 입력을 봅시다.
scores = [70, 85, 90, 60]
word = "apple"scores는 숫자 배열입니다. word는 문자열이지만, 필요할 때는 'a', 'p', 'p', 'l', 'e'처럼 문자 하나씩 볼 수 있습니다.
이 장의 목표는 어려운 기법을 배우는 것이 아닙니다. 배열과 문자열을 안전하게 읽고, 한 번 훑으면서 답을 만들고, 같은 계산을 반복하지 않도록 정리하는 기본 체력을 만드는 것입니다.
AI 생성 이미지
인덱스, 길이, 범위를 먼저 이해하기
배열에서 각 값의 위치를 인덱스라고 합니다. 대부분의 프로그래밍 언어에서 인덱스는 0부터 시작합니다.
arr = [10, 20, 30, 40]이 배열의 길이는 4입니다. 하지만 마지막 인덱스는 4가 아니라 3입니다.
arr[0] = 10
arr[1] = 20
arr[2] = 30
arr[3] = 40초보자가 가장 자주 만나는 오류는 배열의 범위를 벗어난 위치를 읽는 것입니다.
arr[4] # 잘못된 접근길이가 4인 배열에서 사용할 수 있는 인덱스는 0부터 3까지입니다. arr[4]는 다섯 번째 값을 뜻하지만, 그런 값은 없습니다. 실제 프로그래밍 언어에서는 이런 접근이 오류를 만들거나, 의도하지 않은 값을 읽는 문제로 이어질 수 있습니다.
반복문을 쓸 때도 같은 문제가 생깁니다. 다음처럼 0부터 length(arr)까지 모두 돈다고 생각하면 위험합니다.
for i from 0 to length(arr):
print(arr[i])length(arr)가 4라면 마지막에 arr[4]를 읽으려고 하기 때문입니다. 안전한 범위는 다음과 같습니다.
for i from 0 to length(arr) - 1:
print(arr[i])또는 "배열의 각 값을 하나씩 꺼낸다"는 방식으로 생각할 수도 있습니다.
for value in arr:
print(value)인덱스가 꼭 필요하지 않다면 이 방식이 더 안전합니다. 반대로 "앞뒤 값을 비교해야 한다", "현재 위치가 필요하다"면 인덱스를 써야 합니다.
예를 들어 이웃한 두 값을 비교하려면 arr[i]와 arr[i + 1]을 봐야 합니다. 이때 i + 1이 마지막 인덱스를 넘지 않게 해야 합니다.
for i from 0 to length(arr) - 2:
if arr[i] < arr[i + 1]:
print("오른쪽 값이 더 큼")길이가 4인 배열이라면 i는 0, 1, 2까지만 움직이면 됩니다. 그래야 마지막 비교가 arr[2]와 arr[3]이 되고, 존재하지 않는 arr[4]를 보지 않습니다.
배열 문제를 풀 때는 먼저 세 가지를 확인하는 습관을 들이세요.
배열의 길이는 얼마인가?
사용할 수 있는 인덱스 범위는 어디부터 어디까지인가?
i + 1,i - 1처럼 옆 위치를 볼 때 범위를 벗어나지 않는가?
이 세 가지만 확인해도 많은 실수를 줄일 수 있습니다.
한 번 순회하며 답 만들기
배열 문제의 가장 기본 패턴은 처음부터 끝까지 한 번 훑으며 답을 갱신하는 것입니다. 앞에서 배운 표현으로 말하면 보통 시간 복잡도는 O(n)입니다. 배열의 길이가 n일 때 모든 원소를 한 번씩 보기 때문입니다.
대표적인 예는 합계 구하기입니다.
arr = [3, 5, 2, 8]손으로 계산하면 다음과 같습니다.
처음 합계 = 0
3을 더함 → 3
5를 더함 → 8
2를 더함 → 10
8을 더함 → 18의사코드로 쓰면 다음과 같습니다.
sum = 0
for value in arr:
sum = sum + value
return sum최댓값도 비슷합니다. 다만 처음 기준값을 잘 정해야 합니다.
arr = [3, 5, 2, 8]처음에는 첫 번째 값을 최댓값이라고 가정합니다.
max_value = arr[0]
for i from 1 to length(arr) - 1:
if arr[i] > max_value:
max_value = arr[i]
return max_value여기서 중요한 생각은 "처음부터 진짜 최댓값을 알 수는 없지만, 지금까지 본 값 중 가장 큰 값은 기억할 수 있다"는 점입니다. 배열을 왼쪽에서 오른쪽으로 보면서 더 큰 값을 만나면 답을 바꿉니다.
단, 이 방법은 배열에 값이 하나 이상 있을 때 사용할 수 있습니다. 빈 배열이라면 arr[0] 자체가 없으므로, 문제에서 빈 배열이 들어올 수 있는지 먼저 확인해야 합니다.
최솟값도 방향만 반대입니다.
min_value = arr[0]
for i from 1 to length(arr) - 1:
if arr[i] < min_value:
min_value = arr[i]
return min_value개수 세기도 자주 나옵니다. 예를 들어 배열에서 짝수의 개수를 구해 봅시다.
arr = [1, 4, 6, 7, 9, 10]각 값을 보면서 조건에 맞으면 개수를 1 늘립니다.
count = 0
for value in arr:
if value % 2 == 0:
count = count + 1
return count이 패턴은 매우 중요합니다. 많은 문제는 겉으로 복잡해 보여도 "무엇을 기억하면서 한 번 훑을 것인가?"로 바꿀 수 있습니다.
합계를 구할 때는
sum을 기억합니다.최댓값을 구할 때는
max_value를 기억합니다.최솟값을 구할 때는
min_value를 기억합니다.조건을 만족하는 개수를 구할 때는
count를 기억합니다.특정 값이 있는지 확인할 때는
found같은 참/거짓 값을 기억합니다.
예를 들어 배열에 0이 하나라도 있는지 확인하려면 다음처럼 쓸 수 있습니다.
found = false
for value in arr:
if value == 0:
found = true
break
return foundbreak는 더 볼 필요가 없을 때 반복을 멈추는 도구입니다. 이미 0을 찾았다면 나머지 값을 확인하지 않아도 답은 변하지 않습니다.
문자열은 문자 배열처럼 다룬다
문자열은 문자들이 순서대로 모인 값입니다.
text = "hello"이 문자열은 다음처럼 볼 수 있습니다.
text[0] = 'h'
text[1] = 'e'
text[2] = 'l'
text[3] = 'l'
text[4] = 'o'문자열에서도 길이와 인덱스 범위는 배열과 같습니다. 길이가 5라면 마지막 인덱스는 4입니다.
문자열 문제의 기본도 순회입니다. 예를 들어 문자열에서 문자 'a'가 몇 번 나오는지 세어 봅시다.
text = "banana"count = 0
for ch in text:
if ch == 'a':
count = count + 1
return count문자열에서는 대소문자 처리가 자주 등장합니다. 컴퓨터는 'A'와 'a'를 다른 문자로 봅니다. 따라서 대소문자를 구분하지 말라고 하면 먼저 같은 형태로 바꾸는 것이 좋습니다.
text = to_lowercase(text)그다음 비교하면 됩니다.
count = 0
text = to_lowercase(text)
for ch in text:
if ch == 'a':
count = count + 1
return count공백 처리도 중요합니다. 문자열 "a b c"는 눈으로 보면 세 글자처럼 느껴질 수 있지만, 실제로는 공백도 하나의 문자입니다.
text = "a b c"문자 단위로 보면 다음과 같습니다.
text[0] = 'a'
text[1] = ' '
text[2] = 'b'
text[3] = ' '
text[4] = 'c'따라서 "공백을 포함해서 길이를 세는가?", "공백은 무시해야 하는가?"를 문제에서 꼭 확인해야 합니다. 공백을 제외하고 문자 개수를 세고 싶다면 다음처럼 조건을 넣을 수 있습니다.
count = 0
for ch in text:
if ch != ' ':
count = count + 1
return count문자열도 배열처럼 한 글자씩 보면서 필요한 정보를 갱신하면 됩니다. 문자 개수 세기, 특정 문자가 있는지 찾기, 대소문자 통일하기처럼 기본적인 작업은 대부분 한 번의 순회로 해결할 수 있습니다.
인덱스를 쓸 때와 값을 바로 꺼낼 때
배열과 문자열을 순회하는 방법은 크게 두 가지로 생각할 수 있습니다.
첫 번째는 값을 바로 꺼내는 방식입니다.
for value in arr:
print(value)이 방식은 단순히 모든 값을 확인할 때 좋습니다. 합계 구하기, 조건에 맞는 개수 세기, 특정 값 찾기처럼 현재 값만 보면 되는 문제에서 편합니다.
두 번째는 인덱스를 사용하는 방식입니다.
for i from 0 to length(arr) - 1:
print(i, arr[i])이 방식은 위치가 필요할 때 사용합니다. 예를 들어 "가장 큰 값이 몇 번째에 있는가?"를 구하려면 값뿐 아니라 인덱스도 기억해야 합니다.
max_value = arr[0]
max_index = 0
for i from 1 to length(arr) - 1:
if arr[i] > max_value:
max_value = arr[i]
max_index = i
return max_index또 이웃한 값과 비교할 때도 인덱스가 필요합니다.
for i from 0 to length(arr) - 2:
if arr[i] == arr[i + 1]:
print("같은 값이 이웃해 있음")정리하면, 현재 값만 필요하면 값을 바로 꺼내고, 위치나 주변 값이 필요하면 인덱스를 쓰면 됩니다. 이 구분만 잘해도 코드가 훨씬 덜 복잡해집니다.
작은 문제를 직접 풀어 보기
이제 앞에서 본 패턴을 간단한 문제에 적용해 봅시다.
문제는 다음과 같습니다.
정수 배열이 주어질 때, 10보다 큰 수가 몇 개인지 구하라.먼저 무엇을 기억해야 할지 생각합니다. 개수를 구해야 하므로 count가 필요합니다.
count = 0그다음 배열을 처음부터 끝까지 봅니다. 값이 10보다 크면 개수를 1 늘립니다.
count = 0
for value in arr:
if value > 10:
count = count + 1
return count문자열 문제도 같은 방식입니다.
문자열이 주어질 때, 모음 a, e, i, o, u가 몇 번 나오는지 구하라.대소문자를 구분하지 않는다고 하면 먼저 소문자로 바꿉니다. 그리고 각 문자가 모음인지 확인합니다.
text = to_lowercase(text)
count = 0
for ch in text:
if ch == 'a' or ch == 'e' or ch == 'i' or ch == 'o' or ch == 'u':
count = count + 1
return count조금 더 읽기 쉽게 표현하면 모음 목록을 따로 두고 확인할 수도 있습니다.
vowels = ['a', 'e', 'i', 'o', 'u']
text = to_lowercase(text)
count = 0
for ch in text:
if ch in vowels:
count = count + 1
return count여기서도 핵심은 같습니다. 처음부터 끝까지 보면서, 지금 본 값이 조건에 맞는지 확인하고, 필요한 답을 갱신합니다.
배열과 문자열 문제를 푸는 순서
배열과 문자열 문제를 만나면 바로 코드를 쓰기보다 다음 순서로 생각해 보세요.
입력이 배열인지 문자열인지 확인합니다.
길이와 인덱스 범위를 확인합니다.
모든 값을 봐야 하는지, 중간에 멈출 수 있는지 생각합니다.
순회하면서 무엇을 기억해야 하는지 정합니다.
i + 1,i - 1처럼 옆 위치를 볼 때 범위를 확인합니다.빈 배열이나 빈 문자열이 들어올 수 있는지 확인합니다.
특히 "무엇을 기억할 것인가?"가 중요합니다. 합계라면 sum, 개수라면 count, 지금까지의 최댓값이라면 max_value, 찾았는지 여부라면 found처럼 작은 변수를 하나 두고 갱신해 나가면 됩니다.
배열과 문자열 문제는 알고리즘 학습의 출발점입니다. 앞으로 더 어려운 자료구조와 알고리즘을 만나더라도, 결국 많은 문제는 데이터를 순서대로 살펴보고 필요한 정보를 갱신하는 과정으로 돌아옵니다. 이 장에서 익힌 인덱스, 길이, 범위, 순회 감각은 계속해서 반복해서 쓰이게 됩니다.
이 노트는 보도·비평·교육·연구 목적으로 작성되었습니다. 저작권 문의가 있으시면 에서 알려주세요.