목록분류 전체보기 (105)
yoongrammer
목차 인터페이스 분리 원칙 (ISP: Interface Segregation Principle) 클라이언트는 사용하지 않는 인터페이스에 강제로 의존해서는 안된다. 로버트 C. 마틴 인터페이스 분리 원칙(ISP)은 클라이언트가 자신이 이용하지 않는 메서드에 의존하지 않아야 한다는 원칙입니다. ISP를 지킴으로써 큰 덩어리의 인터페이스를 구체적이고 작은 단위로 분리시키며 클라이언트가 꼭 필요한 메서드만 이용할 수 있게 합니다. ISP 적용 전 ISP를 위반하는 예를 보겠습니다. Vechicle은 go(), fly() 메서드를 가진 추상 클래스입니다. from abc import ABC, abstractmethod class Vehicle(ABC): @abstractmethod def go(self): pas..
목차 리스코프 치환 원칙 (LSP: Liskov Substitution Principle) S가 T의 하위 유형이면 프로그램에서 자료형 T의 객체는 해당 프로그램의 원하는 속성을 변경하지 않고 자료형 S의 객체로 교체(치환)할 수 있어야 한다. 바바라 리스코프(Babara Liskov) 로버트 C마틴은 이것을 다음과 같이 요약했습니다. 자식 클래스는 부모 클래스를 대체할 수 있어야 한다. 이 원칙의 핵심은 부모 클래스를 사용하는 위치에 자식 클래스를 대신 사용했을 때 코드가 원래 의도대로 작동해야 한다는 것을 의미합니다. LSP 위반 사례 일반적으로 많이 드는 예시가 바로 직사각형을 상속한 정사각형 클래스의 예시입니다. class Rectangle: def __init__(self, width, heig..
목차 개방-폐쇄 원칙 (OCP: Open-Closed Principle) 소프트웨어 엔티티(클래스, 모듈, 함수 등)는 확장에 대해서는 열려 있어야 하지만 변경에 대해서는 닫혀 있어야 한다. Bertrand Mayer 계방 폐쇄 원칙은 기존 코드를 변경하지 않으면서(Close) 기능을 추가(Open)할 수 있도록 설계가 되어야 한다는 원칙입니다. 이 원칙을 지키기 위해서 주로 객체지향의 추상화와 다형성을 활용합니다. OCP 적용 전 class File: def __init__(self, name): self.name = name def __repr__(self): return f'File(name={self.name})' class FileStorage: def save_to_ORACLE(self, fi..
목차 단일 책임 원칙 (SRP: Single Responsibility Principle) 클래스를 변경하는 이유는 단 한 가지여야 한다. 로버트 C. 마틴 단일 책임 원칙(SRP: Single Responsibility Principle)은 다섯 가지 SOLID 애자일 원칙 중 하나입니다. 클래스를 변경하는 이유가 한 가지이기 위해서는 하나의 액터에 대한 책임만 가지고 있어야 합니다. 여기서 책임은 하나의 특정 액터를 위한 기능 집합이고, 액터란 기능(=클래스 ,모듈)을 사용하는 주체입니다. SRP 적용 전 class Car(): def start(self): pass def stop(self): pass def drive(self): pass def wash(self): pass def changeT..
목차 문자열 검색 알고리즘 : Boyer Moore - Good Suffix Heuristics 알아보기 Bad character heuristics은 한 칸만 이동하는 경우가 있습니다. 이 경우 최대 이동 거리를 도출하기 위한 방법으로 Good Suffix Heuristics를 사용합니다. Good Suffix는 패턴의 문자 일부와 일치하는 텍스트의 부분 문자열을 말합니다. Good Suffix Heuristics는 세 가지 상황이 있으며 각 상황에 맞는 오프셋을 제공합니다. Case1. Good Suffix가 패턴의 다른 곳에도 있는 경우 다른 곳에 있는 일치하는 패턴 문자를 Good Suffix와 일치하도록 패턴을 이동시킵니다. 아래 그림에서 Bad character heuristics를 사용한다면..
목차 문자열 검색 알고리즘 : Boyer Moore - Bad Character Heuristic 알아보기 boyer-moore 알고리즘은 문자열 검색 알고리즘으로써 패턴의 전처리로 얻은 정보를 가지고 패턴을 가능한 많이 이동시켜 텍스트와 비교 횟수를 줄입니다. boyer-moore 알고리즘은 보통 상황에서 문자열은 앞부분보다는 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용합니다. 그래서 기존 패턴 검색 알고리즘과 달리 boyer moore 알고리즘은 역방향 접근 방식을 사용합니다. 패턴의 마지막 문자부터 시작하여 오른쪽에서 왼쪽으로 비교를 시작합니다. 이동 위치를 정하기 위해 boyer-moore 알고리즘은 두 가지 휴리스틱을 사용합니다. Bad Character Heuristic Good Su..
목차 문자열 검색 알고리즘 : Rabin-Karp 알아보기 Rabin-Karp 알고리즘은 해시 함수를 사용하여 문자열을 검색하는 알고리즘입니다. 해시 함수를 사용하여 문자열을 숫자 값인 해시 값으로 변경합니다. ex) hash("hello") = 5. 해시 값이 다르다면 두 문자열은 다르다는 것이 보장됩니다. 하지만 문자열이 달라도 해시 값이 같을 수 있습니다. 우리는 이것을 Spurious Hit라고 부릅니다. Spurious Hit 때문에 해시 값이 같을 경우 추가로 문자열이 같은지 비교하는 작업이 필요합니다. 이 특징을 사용하여 Rabin-Karp 알고리즘은 패턴의 해시값을 텍스트의 부분 문자열의 해시 값과 일치하는지 비교하는 작업을 합니다. 따라서 Rabin-Karp 알고리즘은 다음 문자열에 대한..
목차 KMP(Knuth Morris Pratt) 알고리즘 알아보기 navie 알고리즘은 최악의 경우 O(m(n-m+1))의 시간이 걸립니다. (n 패턴의 길이, m 텍스트 길이) 문자 하나하나 씩 비교하기 때문에 불필요한 문자 비교가 있을 수 있습니다. 다음은 navie 알고리즘으로 텍스트 T[]="banananobano"에서 패턴 P[]="nano"를 찾는 과정입니다. 이 동작에서 일부는 낭비입니다. i=2에서 T[3] = 'a', T[4]='n' 이라는 것을 확인했으니 i=3, 4에서 패턴 n과 비교하는 것은 불필요합니다. KMP 알고리즘은 lps(Longest Proper Prefix which is Suffix) 배열을 사용하여 문자열 검색 시 불필요한 문자 간 비교를 없애 성능을 개선시킨 알고리..
목차 Naive Pattern Searching 알아보기 naive pattern searching은 패턴 검색 알고리즘 중에서 가장 간단한 알고리즘입니다. 단순히 문자를 처음부터 끝까지 하나하나 비교해가며 패턴을 찾기 때문에 작은 문자열에서 패턴을 찾을 때 유용합니다. 구현 길이가 n인 텍스트 T안에 모든 위치에서 길이가 m인 패턴 P와 매치 여부를 검토합니다. 패턴의 길이는 텍스트의 길이보다 작거나 같아야 합니다. (m ≤ n) T[0 ... n-1] P[0 ... m-1] 패턴 P는 텍스트 T의 처음부터 n-m+1까지 이동하며 매치가 되는지 검토합니다. 패턴이 발견되면 패턴의 위치를 출력하고 다음 일치 위치를 찾습니다. 구현하면 다음과 같습니다. void naivePatternSearch (char..
목차 플로이드 와셜 알고리즘 (Floyd-Warshall Algorithm) 알아보기 플로이드 와셜 (Floyd-Warshall) 알고리즘은 최단 경로(Shortest path) 문제 중에 모든 정점 쌍(All-pairs)에 대해 최단 거리를 구하는 알고리즘입니다. 플로이드 와셜 알고리즘은 Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, 또는 WFI algorithm 이라고도 합니다. 특징 Dynamic Programming을 사용합니다. 유향 또는 무향 가중 그래프에서 최단 경로를 찾을 수 있으며 음수 사이클이 있는 경우는 찾지 못합니다. 그래프에 음수 사이클 여부를 확인할 수 있습니다. 구현 플로이드 와셜 알고리즘은 각각..