Advanced Data Structure & String

<Advanced Data Structure & String>

    1. Advancecd Data Structure

     2. String

---

Advanced Data Structure

 

Stack

First In Last Out

 

스택 구조는 기존 List를 활용

→ 동적 배열이기 때문에 push와 pop이 O(1)

 

 

Queue

Fisrt In First Out

Queue 구조를 기존 List로 만들 경우, List는 한쪽 방향으로 열려 있는 동적 배열

→ 연결 List 자료 구조가 필요

• 양쪽으로 자유로운 입출력
• 중간 참조는 오래 걸리나, Queue 구조에선 상관 없음
• Collection Library의 Deque 사용

from collections import deque               # deque import    

queue = deque([10, 5, 12])                  # deque 생성

queue.appendleft(16)                        # 왼쪽 삽입
queue.pop()                                 # 오른쪽 삭제

queue.append(20)                            # 오른쪽 삭제
queue.popleft()                             # 왼쪽 삭제

queue				# deque([10, 5, 20])

 

Heapq

• 최소/최댓값을 빠르게 구하고 싶을 때,

    - min/max 함수 사용 → O(N)

    - 이진 검색을 위해선 내부가 정렬되어 있어야 함

• 내부가 항상 정렬된 자료구조

    - 입력할 때마다 sorted 사용 → 값 삽입/삭제: O(NlogN)

    - 리스트 정렬 후 값을 중간에 삽입/삭제 → O(N)

 

import heapq

queue = [5, 2, 8, 4]

heapq.heapify(queue)                # Heap 초기화, O(NLOGN)
queue                               # Heap[k] <= heap[2*k+1], heap[2*k+2]
# [2, 4, 8, 5]

queue[0]                            # Heap top: 가장 작은 값 위치, Min Heap
# 2

heapq.heappush(queue, 3)            # Heap Push, 0(log N)

heapq.heappush(queue, 6)

queue[0]
# 2

item = heapq.heappop(queue)         # Heap Pop, O(log N)
item, queue[0]
# (2, 3)

item = heapq.heappushpop(queue, 7)  # Push 하고 Pop 하는 것보다 빠름
item, queue[0]
# (3, 4)

 

Defaultdict

• Python 기본 dictionary는 Key가 없을 경우 에러 발생

→ 에러 발생을 막기 위해선 get 메소드의 default 값 지정 필요

 

from collections import defaultdict    # 기본값 int()

characters = defaultdict(int)          # int는 lambda 0을 뜻함

for char in text:
	characters[char] += 1

 

Counter

• 뭔가를 세는 데 최적화된 데이터 구조

from collections import Counter

characters = Counter(text)

print(characters)

• Dictionary처럼 생성 및 관리

c = Counter({"Korean": 2, "English": 3})
c												
# Counter({'English': 3, 'Korean': 2})

c.keys()                                    # 일반적인 dict와 차이 없음
# Dict_keys(['Korean', 'English'])

c.values()
# Dict_values([2, 3])

c["Korean"]
# 2

list(c.elements())                          # 모든 요소 반환
# ['Korean', 'Korean', 'English', 'English', 'English']

• 집합 연산 지원

>>> from collections import Counter

a = Counter([1, 1, 2, 2, 2, 3])
b = Counter([2, 3, 3, 4])

a + b                                # 횟수 더하기
# Counter({2: 4, 3: 3, 1: 2, 4: 1})

a & b                                # 교집합
# Counter({2: 1, 3: 1})

a | b                                  # 합집합
# Counter({2: 3, 1: 2, 3: 2, 4: 1})

a - b                                  # 차집합
# Counter({1: 2, 2: 2})

 

Named Tuple

• 각 Tuple 원소에 이름 붙이기 가능
• Class가 아닌 Tuple 이므로 Unpacking 가능

from collections import namedtuple

Coords3D = namedtuple("Coords3D", ['x', 'y', 'z'])

point = Coords3D(10, 20, z=30)

print(point.x)                    # Attribute 이름으로 참조
print(point[1])                   # Index로 참조
print(*point)                     # Tuple Unpacking

point[1] += 1                   # Error 발생

 

Dataclass

• Pythonic 한 데이터 클래스를 위해선 dataclasses의 dataclass 데코레이터 활용

>>> from dataclasses import dataclass

@dataclass
class Coords3D:
	x: float
	y: float
	z: float = 0

	def norm(self) -> float:
		return (self.x ** 2 + self.y ** 2 + self.z ** 2) ** .5


point = Coords3D(10, 20, z=30)
print(point)		# Coords3D(x=10, y=20, z=30)

print(point.norm()) # 37.416573867739416

---

String

 

파이썬 String의 특징

• 원시 자료형이자, 불변 타입 → Out-Place 연산
• 큰 따옴표 " 혹은 작은따옴표 ' 로 표기된다
• 따옴표를 3개 연달아 쓰면 여러 줄을 넣을 수 있다
• Indexing 및 Slicing이 가능하다
• 덧셈 및 곱셈이 가능하다
• in & not in 연산이 가능하다 → Tuple과의 차이점
• Unicode로 처리된다 → 다양한 언어 사용 가능

 

Special Characters

• Escape 문자 ＼를 사용하여 특수 문자 활용

문자	설명
＼ [Enter]	다음 줄과 연속임을 표현
＼＼	＼ 문자
＼'	' 문자
＼"	" 문자
＼b	백스페이스
＼n	줄 바꾸기
＼t	TAB 키
＼e	ESC 키

 

 

Raw String

• r"<TEXT>"
• ＼를 무시하고 문자 그대로 취급 가능
• 주로 정규 표현식에서 사용

 

String Functions

함수 형태	기능
len(spring)	문자 개수 반환
string.upper()	대문자로 반환
string.lower()	소문자로 반환
string.capitalize()	문자열 시작 문자를 대문자로 반환
string.title()	단어 시작을 대문자로 반환
string.strip()	좌우 공백 제거
string.lstrip()	왼쪽 공백 제거
string.rstrip()	오른쪽 공백 제거
string.isdgit()	숫자 형태인지 확인
string.isupper()	대문자로만 이루어져 있는지 확인
string.islower()	소문자로만 이루어져 있는지 확인
string.count(pattern)	문자열 string 내에 pattern 등장 횟수 반환
string.find(pattern)	문자열 string 내에 pattern 첫 등장 위치 반환 (앞에서 부터)
string.rfind(pattern)	문자열 string 내에 pattern 첫 등장 위치 반환 (뒤에서 부터)
string.startswith(pattern)	문자열 string이 pattern으로 시작하는지 확인
string.endswith(pattern)	문자열 string이 pattern으로 끝나는지 확인
string.split()	공백을 기준으로 문자열 나누기
string.split(pattern)	pattern을 기준으로 문자열 나누기
string.join(iterable)	String을 중간에 두고 iterable 원소들 합치기

 

 

String Formatting

• %-formating

    - C나 Java에서 주로 쓰이는 방식

"Art: %5d, Price per Unit: %8.2f" %(453, 59.06)       # 'Art:   453, Price per Unit:    59.06'

%datatype	설명
%s	문자열 (str)
%d	정수 (int)
%f	부동소수점 (float)
%o	8진수
%x	16진수

    - "%[Padding]datatype" 형태로 패딩 가능

"%4d+%4d+%4d" % (1, 10, 100)

'1+  10+ 100'

    - "%[Padding].[precision]datatype" 형태로 정확도 지정

"%.3f+%.3f+%.3f" % (123.4, 12.34, 1.234)	# '1234.400+12.340+1.234'

• String.format Method

    - "0".format(variables)

    - 순서 설정

"{1}: {3} - {2}".format(a, b, c)		# 'a: c - b'

    - 패딩 설정

"{0:3f}+{1:.3f}+{2:.3f}".format(123.4, 12.34, 1.234)		# '123.400+12.340+1.234'

• F-string

    - Python 3.6 이상부터 지원

    - 변수 위치에 원하는 변수를 위치하면 됨

a, b, c = 10, 1.725, 'sample'

f"{a+10}: {b:.2f} - {c}"                # Python 평가식 적기 가능, 정확도 Padding 가능
# '20: 1.72 - sample'

 

정규 표현식 (Regular Expression)

• 특정한 규칙을 가진 문자열의 집합을 표현하는 데 사용하는 형식 언어
• 많은 텍스트 편집기와 프로그래밍 언어에서 문자열 검색과 치환에 활용
• 일반 텍스트 패턴 → 정확히 일치되는 문자열만 찾음 (.find와 동일)
• 특수 문자

    - 정규식에서만 쓰이는 문자

    - 공백, 영단어 등

    - 일반 문자와 섞어 씀

특수 글자	설명	Regex
＼w	영숫자 + "_"	[A-Za-z0-9_]
＼W	(영숫자 + "_") 를 제외한 문자	[^A-Za-z0-9_]
＼d	숫자	[0-9]
＼D	숫자가 아닌 문자	[^0-9]
＼s	공백 문자	[ ＼t＼r＼n＼v＼f]
＼S	공백이 아닌 문자	[^ ＼t＼r＼n＼v＼f]
＼b	단어 경계	(?<=＼W)(?=＼w)|(?<=＼w)(?=＼W)

 

 

Meta Character

• 메타 문자: 정규식의 문법적인 요소를 담당하는 문자
• . ^ $ * + ? { } [ ] ＼ | ( )
• 이 문자들은 특수한 의미의 문자이므로 사용 불가능

    - 문자 그대로 matching 하고 싶다면 Escape 문자 ＼를 붙여 사용

 

 

Regular Expression: Character Class

• 문자 클래스 [ ]

    - [ 와 ] 사이의 문자들 중 하나와 매칭

    - '-'를 사용하여 범위를 지정 가능

    ex) [a-z]  [A-Z0-9]  [＼d＼s]

• 부정 [^ ]

    - [^ 와 ] 사이에 없는 문자를 매칭

    - '-' 를 사용하여 범위를 지정 가능

    ex) [^a-z]  [^A-Z0-9]  [^＼s]

 

Regular Expression: Repetition

• 문자 .

    - 아무 문자나 하나를 매칭

    - 줄 바꿈 문자는 ＼n 제외 (공백은 포함!)

• 0회 이상 *

    - 앞의 문자를 0개 이상 포함

    ex) ab*c → ac, abc, abbc, abbbbc ...

• 1회 이상 +

    - 앞의 문자를 1개 이상 포함

    ex) ab+c → abc, abbc, abbbc ...

• 0 또는 1회 ?

    - 앞의 문자가 없을 수도 있음

    ex) ab?c → ac, abc

• 반복 횟수 지정 {m, n}

    - m번 이상 n번 이하 반복

    - 숫자가 하나만 주어졌을 경우

        º {m}: m번 반복

        º {m,}: m번 이상 반복

        º {, n}: n번 이하 반복

• Lazy Matching ?

    - * + {}와 같은 반복 연산은 최대한 길게 반복

    - 최대한 짧게 매칭 하기 위해선 뒤에 ? 삽입

    ex) *?, +?, {n, m}?

    - 별로 권장하지는 않는다 (의도치 않은 작동이 일어날 수도)

Regular Expression: Boundary

• 선택 |

    - 여러 식 중 하나를 선택

• 단어 경계 ＼b

    - 단어의 경계 지점인지 확인

• 줄의 시작 ^

    - 줄이나 문자열의 시작점

    - Multiline flag 필요

• 줄의 끝 $

    - 줄이나 문자열의 끝

    - Multiline flag 필요

Regular Expression: Capture

• 그룹 캡처 ( )

    - 괄호이므로 우선순위가 있음

    - 해당 문자열을 캡처한다

    - 캡처된 텍스트를 불러올 수 있다

    - ＼1, ＼2, ＼3, ... , ＼[NUMBER]

• 비 그룹 캡처 (?:)

    - 괄호이므로 우선순위가 있음

    - 캡처를 하지는 않는다

    - 그냥 괄호다

Regular Expression: Condition

• 뒷 패턴 확인 D(?=R)

    - R이 바로 뒤에 있는 D를 매칭

    - R 부분은 포함되지 않음

• 앞 패턴 확인 (?<=R)D

    - R이 바로 앞에 있는 D를 매칭

    - R 부분은 포함되지 않음

 

 

Regular Expression in Python

파이썬 표준 re패키지를 사용

• 탐색: 처음 매칭 되는 문자열 탐색

match = re.search(pattern, string, re.MULTILINE)

print(match.group(0))

• 모두 탐색: 모든 매칭되는 문자열 탐색

for match in re.finditer(pattern, string, re.MULTILINE):
	print(match.group(0))

• 치환: 매칭되는 패턴 치환

repl = r"치환됨-＼1"

print(re.sub(pattern, repl, string, flags=re.MULTILINE))

• 나누기: 매칭되는 패턴을 기준으로 나누기

splited = re.split(pattern, string, flags=re.MULTILINE)

print(splited)

 

Regular Expression Compile

정규 표현식을 평가하는 것은 오래 걸림→ 정규 표현식을 미리 컴파일 (훨씬 빠름)

 

compiled = re.compile(pattern, flags=re.MULTILINE)

for string in dataset:
	match = compiled.search(string)
    print(match.group(0))