24. 제네릭 프로그래밍#
슬라이드
본문 내용을 요약한 슬라이드를 다운로드할 수 있다.
주요 내용
제네릭 프로그래밍 소개
제네릭 되추적 알고리즘
24.1. 제네릭 프로그래밍이란?#
제네릭 프로그래밍generic programming은 하나의 자료형에만 의존하지 않고 공통 속성을 갖는 여러 자료형daya type에 대해 동일하게 작동하는 알고리즘을 작성하는 기법 일반을 의미한다. 따라서 제네릭 프로그래밍 기법으로 작성된 알고리즘은 하나의 문제만이 아닌 공통 속성을 갖는 여러 문제를 대상으로 적용할 수 있다.
제네릭 프로그래밍 기법으로 알고리즘을 구현하는 방식은 다양하다. 여기서는 다음 두 가지 방식을 소개한다.
모듈 활용: 파이썬처럼 고계 함수higher-order function를 지원하는 프로그래밍언어의 경우 활용
다형성polymorphism 활용: 다양한 자료형을 마치 하나의 자료형 처럼 다루는 기법. 자바, 파이썬 등에서 제공하는 제네릭 클래스 활용.
24.2. 모듈 활용#
다음 두 알고리즘은 사실상 동일한 되추적 알고리즘을 사용한다.
n-여왕말 문제:
backtracking_search_queens(num_queens, assignment)함수m-색칠 문제:
backtracking_search_colors(num_nodes, num_colors, constraints, assignment)함수
두 알고리즘의 근본적인 차이점은 유망성을 확인하는 방식에 있다.
n-여왕말 문제:
promissing_queens()함수m-색칠 문제:
promissing_colors()함수
그런데 유망성 확인 함수를 되추적 알고리즘의 인자로 사용할 수 있다. 이것이 가능한 이유는 파이썬 프로그래밍언어가 고계 함수, 즉 함수를 인자 또는 반환값으로 사용할 수 있는 함수를 지원하기 때문이다.
아래 backtracking_search() 함수는 n-여왕말 문제와 m-색칠 문제의 두 되추적 알고리즘을 하나로 통일시킨다.
from typing import List, Dict, Callable
def backtracking_search(variables: List[int],
domains: Dict[int, List[int]],
promissing: Callable[[int, Dict[int, int]], bool],
assignment: Dict[int, int] = {}):
# 재귀 종료 조건: 모든 변수에 대한 값이 지정된 경우
if len(assignment) == len(variables):
return assignment
# 재귀 실행: 아직 값이 정해지지 않은 (대상) 변수가 존재하는 경우
unassigned = [v for v in variables if v not in assignment]
first = unassigned[0]
for value in domains[first]:
# 주의: 기존의 assignment를 보호하기 위해 복사본 활용
# 되추적이 발생할 때 이전 할당값을 기억해 두기 위해서임.
local_assignment = assignment.copy()
local_assignment[first] = value
# local_assignment 값이 유망하면 되추적 기법 재귀 적용
if promissing(first, local_assignment):
result = backtracking_search(variables, domains, promissing, local_assignment)
# 모든 (대상) 변수의 값이 정해졌을 때 재귀 종료
if result is not None:
return result
return None
backtracking_search() 함수에 사용된 매개변수는 다음과 같다.
variables: 문제 정의에 사용되는 (대상) 변수들의 리스트. 정수들의 리스트 (List[int]) 사용.domains: 각각의 (대상) 변수들이 가질 수 있는 값들의 리스트로 구성된 사전. 정수들의 리스트를 값으로 사용 (Dict[int, List[int]]).promissing: 유망성 확인 함수assignment: 되추적 알고리즘 실행 동안 값이 지정된 (대상) 변수들의 값으로 구성된 사전 (Dict[int, int]).
promissing 매개변수의 자료형으로 지정된 Callable[[int, Dict[int, int]], bool]의 의미는 다음과 같다.
함수 인자 사용:
Callable두 개의 인자 사용:
[int, Dict[int, int]]첫째 인자: 정수(
int)둘째 인자: 키와 값 모두 정수를 사용하는 사전 객체(
Dict[int, int])
반환값 자료형:
bool
자료형 힌트
파이썬 최신 버전은 함수의 매개변수를 지정할 때 인자로 사용되기를 기대하는 값들의 자료형을 명시할 수 있다. 보다 자세한 내용은 자료형 힌트 지원를 참고한다.
이제 4-여왕말 문제와 4-색칠 문제를 위 backtracking_search() 함수를 이용하여 동시에 해결할 수 있음을 보인다.
예제: 4-여왕말 문제 해결
문제 정의에 필요한 (대상) 변수와 도메인은 다음과 같다.
변수: 네 개의 여왕말
variables : List[int] = [1, 2, 3, 4]
도메인: 하나의 여왕말이 위치할 수 있는 가능한 모든 칸. 항상 네 종류의 값 사용 가능.
domains: Dict[int, List[int]] = {}
columns = [1, 2, 3, 4] # 네 개의 열 또는 색
for var in variables:
domains[var] = columns
여기서는 4-여왕말 문제 해결에 사용되는 유망성 함수는 다음과 같으며
constraint_queens 모듈에 선언되어 있다고 가정한다.
from typing import List, Dict
def promissing(variable: int, assignment: Dict[int, int]):
"""
새로운 변수 variable에 값을 할당 하면서 해당 변수와 연관된 변수들 사이의 제약조건이
assignment에 대해 만족되는지 여부 확인
n-여왕말 문제의 경우: 제약조건이 모든 변수에 대해 일정함.
즉, 새로 위치시켜야 하는 퀸이 기존에 이미 자리잡은 퀸들 중 하나와
동일 행, 열, 대각산 상에 위치하는지 여부를 확인함
"""
# q1r, q1c: 첫째 퀸이 놓인 마디의 열과 행
for q1r, q1c in assignment.items():
# q2r = 첫째 퀸 아래에 위치한 다른 모든 퀸들을 대상으로 조건만족여부 확인
for q2r in range(q1r + 1, len(assignment) + 1):
q2c = assignment[q2r] # 둘째 퀸의 열
if q1c == q2c: # 동일 열에 위치?
return False
if abs(q1r - q2r) == abs(q1c - q2c): # 대각선상에 위치?
return False
# 모든 변수에 대해 제약조건 만족됨
return True
이제 4-여왕말 문제를 해결할 수 있다.
from constraint_queens import promissing
backtracking_search(variables, domains, promissing=promissing)
{1: 2, 2: 4, 3: 1, 4: 3}
예제: 4-색칠 문제 해결
문제 정의에 필요한 (대상) 변수와 도메인은 다음과 같다.
변수: 다섯 개의 노드
variables : List[int] = [1, 2, 3, 4, 5]
도메인: 하나의 노드가 가질 수 있는 가능한 모든 색. 항상 네 종류의 색 사용 가능.
domains: Dict[int, List[int]] = {}
columns = [1, 2, 3, 4] # 네 개의 열 또는 색
for var in variables:
domains[var] = columns
아래 그래프와 같은 4-색칠 문제 해결에 사용되는 유망성 판단 함수는 다음과 같으며
constraint_colors 모듈에 저장되어 있다고 가정한다.
|
|
from typing import List, Dict
def promissing(variable: int, assignment: Dict[int, int]):
"""
새로운 변수 variable에 값을 할당 하면서 해당 변수와 연관된 변수들 사이의 제약조건이
assignment에 대해 만족되는지 여부 확인
m-색칠 문제의 경우: 이웃마디의 상태에 따라 제약조건이 달라짐.
즉, 마디 variable에 할당된 색이 이웃마디의 색과 달라야 함.
이를 위해 각각의 마디가 갖는 이웃마디들의 리스트를 먼저 확인해야 함.
"""
# 마디 별 이웃마디의 리스트
constraints = {
1 : [2, 3, 4, 5],
2 : [1, 3, 4, 5],
3 : [1, 2, 4],
4 : [1, 2, 3, 5]
}
for var in constraints[variable]:
if (var in assignment) and (assignment[var] == assignment[variable]):
return False
return True
4-색칠 문제 해결
from constraint_colors import promissing
backtracking_search(variables, domains, promissing=promissing)
{1: 1, 2: 2, 3: 3, 4: 4, 5: 3}
결과를 그림으로 나타내면 다음과 같다.
|
|
24.3. 다형성 활용#
n-여왕말과 m-색칠 문제에서 변수 또는 도메인 값들이 숫자가 아닌 문자열 등 다른 자료형이 사용될 수 있음.
체스판의 열은 원래 1에서 8까의 숫자 대신에 a 부터 h 사이의 알파벳으로 표시됨.
지도를 색칠할 때 영역은 번호 보다는 이름으로 표현함.
하지만 자료형이 달라진다 하더라도 되추적 알고리즘 자체가 변하지는 않음. 다만, 유망성을 확인하는 함수가 사용되는 자료형에 따라 조금 수정될 필요는 있음.
예를 들어, n-여왕말 문제의 유망성에서 대각선상에 위치하는지 여부를 판정할 때 숫자를 다루는 경우와 문자열을 다루는 경우는 조금 다를 수밖에 없음.
클래스 활용
서로 연관된 속성과 함수들을 하나의 클래스로 묶어서 활용할 수도 있음.
되추적 알고리즘과 유망성 확인 함수를 하나의 클래스로 묶어서 사용
문제에 따라 클래스의 인스턴스를 다르게 생성
주의사항
되추적 알고리즘(
backtracking_search())는 변하지 않음.유망성 확인 메서드(
promissing())는 문제(인스턴스)별로 달라짐.
제네릭 클래스
문제마다 사용되는 자료형이 다를 수 있음.
열 또는 색상: 1, 2, 3, 4 대신에 a, b, c, d 등 문자열 사용할 수도 있음.
되추적 알고리즘은 사용되는 자료형에 상관없이 작동함.
따라서 일반적인 유형에 대해 작동하는 제네릭 클래스의 메서드로 구현 가능
제네릭 클래스의 사용법은 다음과 같음.
from typing import Generic, TypeVar # 제네릭 변수. 여기서는 두 개의 제네릭 변수 지정 # 해당 클래스의 인스턴스를 선언하면 적절한 자료형으로 자동 대체됨. V = TypeVar('V') D = TypeVar('D') # 아래 제네릭클래스에서 사용되는 변수 또는 값의 일부가 V 또는 D 자료형과 연관됨 class 제네릭클래스(Generic[V, D]): 클래스본문
추상클래스와 추상메서드
유망성 확인 함수인
promissing()메서드는 추상메서드(abstract method)로 지정한 후 문제에 따라 다르게 정의해야 함.
추상메서드: 클래스 내에서 함수로 선언만 되고 정의되지 않은 상태로 남겨진 메서드
추상클래스: 추상메서드를 한 개 이상 포함한 클래스
추상클래스와 추상메서드 사용법은 다음과 같음.
전제조건:
abc모듈에서ABC클래스와abstractmethod장식자 불러오기추상클래스는
ABC클래스를 상속해야 함.
from abc import ABC, abstractmethod class 추상클래스명(ABC): @abstractmethod def 추상메서드(self, 매개변수, ..., 매개변수): ... # 기타 메서드 및 속성
되추적 알고리즘 구현: 클래스 활용
이후에 사용되는 코드는 고전 컴퓨터 알고리즘 인 파이썬 의 3장 코드를 단순화하였음.
제네릭 클래스 선언
제네릭 클래스 선언에 필요한 제네릭 변수 지정
V: 주어진 문제에 사용되는 변수들의 자료형.예를 들어 1, 2, 3 등의 int 또는 서울, 경기, 인천 등의 str
활용:
variables: List[V]
D: 주어진 문제에 사용되는 도메인에 포함된 값들의 자료형.예를 들어 1, 2, 3 등의 int 또는 a, b, c, 빨강, 녹색, 파랑 등의 str
활용:
domains: List[D]
from typing import Generic, TypeVar, Dict, List, Optional
from abc import ABC, abstractmethod
V = TypeVar('V')
D = TypeVar('D')
Constraint클래스 선언유망성 확인함수를 추상메서드로 가짐.
Generic클래스와ABC클래스 모두 상속
class Constraint(Generic[V, D], ABC):
@abstractmethod
def promissing(self, variable: V, assignment: Dict[V, D]) -> bool:
...
Backtracking클래스 선언되추적 알고리즘을 메서드로 가짐.
Generic클래스 상속
주의:
Optional: 경우에 따라None이 값으로 사용될 수 있음을 암시함.Optional[T]의 의미: 기본적으로 자료형 T의 값을 사용하지만None이 사용될 수도 있음.
class Backtracking(Generic[V,D]):
# 제약조건을 지정하면서 인스턴스 생성
def __init__(self,
variables: List[V],
domains: Dict[V, List[D]],
constraint: Constraint[V,D]) -> None:
self.variables: List[V] = variables
self.domains: Dict[V,List[D]] = domains
self.constraint = constraint
# promissing 메서드가 Constraint 클래스에서 선언되었기에 따로 인자로 받지 않음.
def backtracking_search(self,
assignment: Dict[V,D] = {}) -> Optional[Dict[V,D]]:
if len(assignment) == len(self.variables):
return assignment
unassigned: List[V] = [v for v in self.variables if v not in assignment]
first: V = unassigned[0]
for value in self.domains[first]:
local_assignment = assignment.copy()
local_assignment[first] = value
if constraint.promissing(first, local_assignment):
result = self.backtracking_search(local_assignment)
if result is not None:
return result
return None
8-여왕말 문제 해결하기
8개의 퀸과 8개의 열 사용하기
열을 a, b, …, h 로 사용
퀸이 위치하는 열을 번호가 아닌 문자열로 처리하기에
promissing()메서드 정의가 이전과 조금 달라짐.동일한 열 또는 동일한 대각선 상에 있는지 여부는 순서가 중요함.
enumerate()함수를 활용하여 항목의 인덱스를 활용할 수 있음.
# 변수: 여덟 개의 퀸 1, 2, ..., 8
variables : List[int] = [1, 2, 3, 4, 5, 6, 7, 8]
# 도메인: 여덟 개의 퀸이 위치할 수 있는 가능한 모든 열. 문자열 사용
domains: Dict[int, List[str]] = {}
columns = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
for var in variables:
domains[var] = columns
# columns의 순서 지정하기
col2ind = {column : index+1 for (index, column) in enumerate(columns)}
문제에 맞는
Constraint클래스의 인스턴스 생성하려면 먼저Constraint클래스를 상속하는 구상클래스를 선언해야 함.이유: 추상 클래스는 바로 인스턴스를 만들 수 없음.
promissing()메서드를 구현해야 함.이전에 사용한 constraint_queens 모듈의
promissing()함수와 동일.
주의: 열의 순서가 중요하기에
col2ind사전을 활용함
class ConstraintQueens(Constraint[int, str]):
# promissing 메서드 정의해야 함.
def promissing(self, variable: int, assignment: Dict[int, str]) -> bool:
# q1r, q1c: 첫째 퀸이 놓인 마디의 열과 행
# 키값이 문자열이기에 해당 문자열의 인덱스를 대신 사용함. 즉, col2ind 활용
for q1r, q1c in assignment.items():
q1c = col2ind[assignment[q1r]] # 첫째 퀸의 열
# q2r = 첫째 퀸 아래에 위치한 다른 모든 퀸들을 대상으로 조건만족여부 확인
for q2r in range(q1r + 1, len(assignment) + 1):
q2c = col2ind[assignment[q2r]] # 둘째 퀸의 열
if q1c == q2c: # 동일 열에 위치?
return False
if abs(q1r - q2r) == abs(q1c - q2c): # 대각선상에 위치?
return False
# 모든 변수에 대해 제약조건 만족됨
return True
constraint = ConstraintQueens()
backtracking = Backtracking(variables, domains, constraint)
backtracking.backtracking_search()
4-여왕말 문제
# 변수: 네 개의 퀸 1, 2, 3, 4
variables : List[int] = [1, 2, 3, 4]
# 도메인: 네 개의 퀸이 위치할 수 있는 가능한 모든 열. 문자열 사용
domains: Dict[int, List[str]] = {}
columns = ['a', 'b', 'c', 'd']
for var in variables:
domains[var] = columns
# columns의 순서 지정하기
col2ind = {column : index+1 for (index, column) in enumerate(columns)}
constraint = ConstraintQueens()
backtracking = Backtracking(variables, domains, constraint)
backtracking.backtracking_search()
4-색칠 문제
색상을 번호가 아닌 RGB(빨강, 녹색, 파랑)으로 표현
이전에 사용한 constraint_colors 모듈의
promissing()함수와 동일.n-여왕말 문제와는 달리 도메인 값의 순서가 중요하지 않음.
# 변수: 네 개의 퀸 또는 네 마디의 번호, 즉, 1, 2, 3, 4
variables : List[int] = [1, 2, 3, 4]
# 도메인: 네 개의 퀸이 위치할 수 있는 가능한 모든 열 또는 각각의 마디에 사용될 수 있는 가능한 모든 색상
domains: Dict[int, List[str]] = {}
columns = ['R', 'G', 'B']
for var in variables:
domains[var] = columns
문제에 맞는 Constraint 클래스를 구상클래스로 상속하기
class ConstraintColors(Constraint[int, str]):
# promissing 메서드 정의해야 함.
def promissing(self, variable: int, assignment: Dict[int, str]) -> bool:
# 각 마디에 대한 이웃마디의 리스트
constraints = {
1 : [2, 3, 4],
2 : [1, 3],
3 : [1, 2, 4],
4 : [1, 3]
}
for var in constraints[variable]:
if (var in assignment) and (assignment[var] == assignment[variable]):
return False
return True
constraint = ConstraintColors()
backtracking = Backtracking(variables, domains, constraint)
backtracking.backtracking_search()