내가 볼려고 작성한 알고리즘 공부.
💾 문자열 (String)
✅ 1. 문자열이란?
문자열(String)은 문자들의 나열이며, 컴퓨터 프로그래밍에서 가장 기본이자 빈번하게 다뤄지는 자료형이다. 문자열은 배열처럼 인덱스로 접근할 수 있으며, 다양한 알고리즘과 자료구조의 기반이 된다.
📌 주요 특징
| 특징 | 설명 |
|---|
| 불변성 (immutable) | 파이썬 문자열은 변경 불가 → 슬라이싱, join 등으로 재구성 |
| 인덱스/슬라이싱 가능 | s[0], s[1:4] 등 배열처럼 사용 가능 |
| 다양한 내장 함수 | .split(), .find(), .count(), .replace() 등 풍부함 |
문자열은 단순 텍스트 처리뿐 아니라, 패턴 매칭, 정렬, 암호화, 파싱, 압축 등 다양한 분야에서 사용된다.
✅ 2. 문자열 처리 기법
2.1 아스키 코드 & 문자 변환
1
2
| ord('A') # 65
chr(97) # 'a'
|
2.2 정렬과 비교
1
2
3
| s = "dcba"
print(sorted(s)) # ['a', 'b', 'c', 'd']
print('abc' < 'abd') # True
|
문자열은 사전 순으로 비교되며, 리스트처럼 정렬 가능하다.
2.3 슬라이싱과 역순 처리
1
2
| s = "hello"
print(s[::-1]) # 'olleh'
|
✅ 3. 문자열 탐색 알고리즘
3.1 KMP (Knuth-Morris-Pratt)
문자열에서 부분 문자열이 존재하는지 빠르게 찾는 알고리즘. 접두사와 접미사 정보를 활용한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| def get_pi(pattern):
pi = [0] * len(pattern)
j = 0
for i in range(1, len(pattern)):
while j > 0 and pattern[i] != pattern[j]:
j = pi[j-1]
if pattern[i] == pattern[j]:
j += 1
pi[i] = j
return pi
def kmp(text, pattern):
pi = get_pi(pattern)
result = []
j = 0
for i in range(len(text)):
while j > 0 and text[i] != pattern[j]:
j = pi[j-1]
if text[i] == pattern[j]:
j += 1
if j == len(pattern):
result.append(i - j + 1)
j = pi[j-1]
return result
|
3.2 라빈-카프 (Rabin-Karp)
문자열을 해시값으로 바꾸어 비교하는 탐색 방식. 충돌이 없으면 매우 빠름.
1
2
3
4
5
6
7
8
| def rabin_karp(text, pattern):
n, m = len(text), len(pattern)
hpattern = hash(pattern)
for i in range(n - m + 1):
if hash(text[i:i+m]) == hpattern:
if text[i:i+m] == pattern:
return i
return -1
|
3.3 트라이 (Trie)
트라이(Trie) 는 문자열을 트리 형태로 저장하는 자료구조로, 자동완성, 접두어 검색, 사전 구축에 유리하다.
- 각 노드는 하나의 문자
- 루트에서 자식 노드를 따라가며 문자열 저장/탐색
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class TrieNode:
def __init__(self):
self.children = {}
self.end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.end = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.end
def starts_with(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
|
✅ 4. 문자열 압축 & 복원
4.1 런-랭스 인코딩 (Run-Length Encoding)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| def rle_encode(s):
result = ""
prev = s[0]
count = 1
for c in s[1:]:
if c == prev:
count += 1
else:
result += prev + str(count)
prev = c
count = 1
result += prev + str(count)
return result
print(rle_encode("aaabbccccd")) # a3b2c4d1
|
✅ 5. 문자열 연습 문제 추천
✅ 6. 문제 풀이
1
2
3
4
5
6
7
8
9
10
| from collections import defaultdict
s = input().upper()
d = defaultdict(int)
for i in s:
d[i]+=1
s_d = sorted(d.items(), key = lambda x:x[1], reverse=True)
if len(s_d)>1 and s_d[0][1] == s_d[1][1]:
print('?')
else:
print(s_d[0][0])
|
Coutner을 이용해서 푸는 방식(GPT 답변)
1
2
3
4
5
6
7
8
| from collections import Counter
s = input().upper()
counter = Counter(s)
most_common = counter.most_common(2)
if len(most_common) > 1 and most_common[0][1] == most_common[1][1]:
print('?')
else:
print(most_common[0][0])
|
collections.Counter란?
- Counter는 파이썬 표준 라이브러리 collections 모듈에 있는 클래스 중 하나로, iterable(반복 가능한 객체)의 요소 개수를 셀 때 매우 유용하게 사용된다.
- dict를 상속받은 클래스이기 때문에 딕셔너리처럼 동작하지만, 자동으로 요소의 빈도수(count) 를 저장해주는 기능이 추가됨. 주요 기능
- 요소 개수 세기
1
2
| Counter('apple')
# Counter({'p': 2, 'a': 1, 'l': 1, 'e': 1})
|
most_common(n): 가장 많이 나온 요소 n개 반환1
2
3
| c = Counter('banana')
c.most_common(2)
# [('a', 3), ('n', 2)]
|
elements(): 요소를 반복자로 반환 (빈도수만큼)1
2
3
| c = Counter({'a': 2, 'b': 1})
list(c.elements())
# ['a', 'a', 'b']
|
- 사칙 연산 지원 (Counter 간 덧셈, 뺄셈 등)
1
2
3
4
| c1 = Counter(a=3, b=1)
c2 = Counter(a=1, b=2)
print(c1 + c2) # Counter({'a': 4, 'b': 3})
print(c1 - c2) # Counter({'a': 2})
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| from collections import Counter
c = Counter(input())
odd = 0
for k,v in sorted(c.items()):
if v%2==1:
odd+=1
m = k
if odd <=1 :
answer = ''
for k,v in sorted(c.items()):
answer = answer + (k*(v//2))
print(answer + (m if odd else '') +answer[::-1] )
else:
print("I'm Sorry Hansoo")
|
이슈 : 런타임 에러 (TypeError)
- 원인: exit() 함수 사용
- 해결: exit() 제거
| 항목 | exit() | sys.exit() |
|---|
| 어디서 쓰기 좋음? | 대화형 쉘 (IDLE, Jupyter) | 스크립트, 알고리즘 문제 환경 |
| 백준에서 안전함? | ❌ 비추천 (런타임 에러 가능) | ✅ 안전함 |
| 프로그래머스에서? | ✅ 대부분 OK | ✅ OK |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
tmp = True
n = int(input())
l = sorted([input().strip() for _ in range(n)])
for i in range(n-1):
if l[i+1].startswith(l[i]):
print('NO')
tmp = False
break
if tmp: print('YES')
|
트라이(Trie)방식 (GPT답변)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| import sys
input = sys.stdin.readline
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def insert(root, number):
node = root
for ch in number:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
if node.is_end: # 누군가 끝났는데 그 뒤에 또 오면 접두어 됨
return False
if node.children: # 내가 끝났는데 아직 누가 뒤에 있음
return False
node.is_end = True
return True
t = int(input())
for _ in range(t):
n = int(input())
numbers = [input().strip() for _ in range(n)]
numbers.sort() # 사전순 정렬하면 빠른 접두어 충돌 탐지에 도움
root = TrieNode()
consistent = True
for num in numbers:
if not insert(root, num):
consistent = False
break
print("YES" if consistent else "NO")
|
- 백준 9251 - LCS (최장 공통 부분 수열)
1
2
3
4
5
6
7
8
9
10
| s1 = input().strip()
s2 = input().strip()
dp = [[0]*(len(s1)+1) for _ in range(len(s2)+1)]
for i in range(1,len(s1)+1):
for j in range(1,len(s2)+1):
if s1[i-1] == s2[j-1]:
dp[j][i] = dp[j-1][i-1]+1
else:
dp[j][i] = max(dp[j][i-1],dp[j-1][i])
print(dp[-1][-1])
|