1. 문자열
1) 컴퓨터에서의 문자 표현
컴퓨터에서의 문자 표현, 각 문자에 대응되는 숫자를 정하고 이를 사용하는 방법이 사용된다.
ASCII 코드
7-bit 인코딩으로 문자를 128 문자를 표현함
33개의 출력 불가능한 제어문자(줄바꿈 등) + 95개의 출력 가능한 문자(32~126)
※ 참고: 확장 아스키 문자
1B내의 8-bit를 모두 활용하여 표준 문자 외에도 악센트, 도형, 특수문자 및 기호를 128개 추가할 수 있게 하는 부호.
컴퓨터 생산자 또는 개발자가 할당하여 사용하게 되므로 서로 다른 프로그램이나 컴퓨터 사이에 교환되지 못한다. (표준이 아님)
다국어 처리를 위해 새로운 표준이 필요하게 되었다.
Unicode (유니코드)
유니코드를 저장하는 바이트 순서는 표준화되지 못했기 때문에, 외부 인코딩이 필요하다.
- big-endian, little-endian ⇢ 어쨌든, 순서가 다르게 되어 있으면 서로 해석할 수 없다.
- 유니코드 인코딩 (UTF; Unicode Transformation Format)
- UTF-8 (웹): 1byte 단위
- Python 3 버전부터는 기본적으로 UTF-8 인코딩. 다른 인코딩 방식으로 처리할 때만 인코딩 방식을 지정해주면 된다: 첫 줄에,
#-*- coding: utf-8-*-
따위를 적어준다.
- Python 3 버전부터는 기본적으로 UTF-8 인코딩. 다른 인코딩 방식으로 처리할 때만 인코딩 방식을 지정해주면 된다: 첫 줄에,
- UTF-16 (윈도우, 자바): 2byte 단위
- UTF-32 (유닉스): 4byte 단위
- UTF-8 과 UTF-16은 가변 길이, UTF-32는 4바이트 짜리
- UTF-8 (웹): 1byte 단위
2) 문자열의 분류
- java: 가변 길이. 몇 글자인지 따로 관리함. 유니코드(UTF-16, 2byte)로 저장.
- Python은 자바와 비슷하다.
- c언어: 널문자(
\0
)를 넣어서 문자열의 끝을 표시함. 아스키 코드로 저장.
Python에서의 문자열 처리
- 유니코드(UTF-8)로 저장.
- char 타입 없음
- 텍스트 데이터의 취급방법이 통일
- ', ", ''', """
+
: concatenation*
: 반복- 거꾸로 하기:
1) 슬라이싱 사용하기:s[::-1]
2) reversed() 함수 사용하기
s = 'Reverse this'
r = reversed(s) # 반전된 오브젝트 -> reversed 객체
print(''.join(r))
2. 패턴 매칭
긴 문자열 안에서 작은 문자열(패턴) 찾기
1) Brute-force
처음부터 끝까지 돌면서 패턴 내 문자와 일일이 비교한다. 틀리면 전체 문자열에서 탐색을 시작할 부분을 한 칸 뒤로 밀고, 패턴의 처음 부분부터 다시 비교한다.
최악의 경우, 시간 복잡도는 $O(M*N)$이 된다. (전체 문자열 길이 x 패턴 길이)
2) KMP 알고리즘
접두사와 접미사 개념을 사용함. 패턴 문자열의 앞부분과 뒷부분이 같으면, 틀려서 문자열을 다시 비교해야 할 때 공통부분만큼은 뛰어넘을 수 있다.
시간 복잡도: 파이(n)
3) 보이어-무어 알고리즘
끝에서부터(오 → 왼) 비교하여 패턴의 문자가 불일치할 때,
i) 해당 문자가 패턴 안에 있다면 일치하는 패턴 속 문자부터 비교함
ii) 해당 문자가 패턴 안에 없다면, 패턴 길이 만큼 건너뜀
시간 복잡도: 파이(n)
3. 문자열 암호화
- 시저 암호 (Caesar cipher): 알파벳을 일정 수만큼 평행이동함으로써 암호화하는 방법
- 단일 치환 암호: 각 문자마다 대응되는 문자를 정해둔 문자 변환표를 이용하여 암호화하는 방법
- bit 열의 암호화
- XOR 연산 이용: 1과 대응시키면 반전
- 두 번 적용하면 해독 된다.
※ 참고
zip(*iterable)
pairs = [(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')]
nums, chars = zip(*pairs)
nums -> (1, 2, 3, 4)
chars -> ('a', 'b', 'c', 'd')
SWEA_1216. 회문2
"""
파이썬의 zip(*iterable)
예)
pairs = [(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')]
nums, chars = zip(*pairs)
nums -> (1, 2, 3, 4)
chars -> ('a', 'b', 'c', 'd')
"""
# 노션 스터디 게시글 보고 공부한 내용
def pal(wrd, m): # 회문 판별하는 함수 만들기 (길이 반만큼만 돌면 된다.)
for i in range(m//2):
if wrd[i] != wrd[-1-i]:
return False
return True
for _ in range(10):
tc = int(input())
arr = [input() for _ in range(100)]
r_arr = [''.join(i) for i in zip(*arr)]
# 컬럼 고정, 행별로 도는 과정을 단순화하기 위해 다른 배열을 하나 만듦
ans = 0
for m in range(100, 1, -1):
# 회문 길이를 가장 바깥 for문으로. i와 j 바뀌어가면서 봐야 하니까.
for i in range(100):
if ans:
break
for j in range(100-m+1):
# 인덱스 범위 값 설정하는 방법 기억해두기:
# (전체 길이)-(단어 길이)까지 앞머리 인덱스 가능
if pal(arr[i][j:j+m], m) or pal(r_arr[i][j:j+m], m): # 동시에 비교
ans = m
break
print(f'#{tc} {ans}')
'알고리즘' 카테고리의 다른 글
1차원 배열 (0) | 2022.03.14 |
---|---|
2차원 배열 (0) | 2022.03.14 |
스택(Stack) (0) | 2022.03.11 |
최단 경로 알고리즘: Dijkstra, Bellman-Ford (0) | 2022.03.10 |
재귀(recursion): 부분집합의 합, 순열 (0) | 2022.03.10 |