3/7

 

목차

 

python isalnum()

# 문자열
s="A man, a plan, a canal: Panama"
s.isalnum()
# FALSE

# 특수문자
s="!!@@SDF"
s.isalnum()
# FALSE

 

BackTracking

설명

문제가 한정 조건을 가진 경우 원소의 순서는 해결 방법과 무관하다. 이런 문제는 변수 집합으로 이뤄지는데, 한정 조건을 구성하려면 각각의 변수들은 값이 있어야 한다. 퇴각검색은 모든 조합을 시도해서 문제의 해를 찾는다. 이것이 장점이 될 수 있는 이유는 퇴각검색 구현 방법들이 많은 부분 조합들을 배제하기 때문이다. 결국 풀이 시간이 단축된다.

 

퇴각검색

구현

깊이 우선 탐색과 유사하게 한쪽으로 갈수 없을 때 까지 간 이후로, 더이상 갈 곳이 없으면 이전 분기점으로 이동한다.

 

조합

def combinations(n, k):
    """
    1부터 n까지 숫자 중 k개를 선택하는 모든 조합 찾기
    
    Args:
        n: 전체 숫자 개수
        k: 선택할 개수
    
    Returns:
        모든 조합의 리스트
    
    result = []
    
    def backtrack(start, current_combination):
        """
        
        
        Args:
            start: 탐색을 시작할 숫자
            current_combination: 현재까지 선택한 숫자들
        
        
        # TODO: base case - k개를 모두 선택했으면 결과에 추가
        if len(current_combination)==k:
            result.append(current_combination[:])
        
        # TODO: start부터 n까지 숫자를 하나씩 시도
        ## TODO: 백트랙킹 3단계 구현
        ## 1. 선택(Choose)
        ## 2. 탐색(Explore)
        ## 3. 취소(Unchoose)
        for i in range(start,n+1):
            if i>=start:
                current_combination.append(i)
                backtrack(i+1,current_combination)
                current_combination.pop()

 

 

 

활용

플래너 프롤로그 같은 프로그래밍언어, 구문분석 분야에 적용

 

해시 집합

중복을 허용하지 않는 고유한 요소들의 집합을 관리하기 위해 해시 테이블을 기반으로 구현한 자료구조이다.

해시 함수를 통해 데이터의 저장 위치를 결정하므로 검색, 삽입, 삭제 평균 O(1)의 빠른 시간 복잡도로 수행 할 수 있어

데이터의 유무 확인에 매우 효율적이다.

 

def find_duplicates_hash(nums):
    """
    방법3: 해시 집합 사용
    시간 복잡도: O(n)
    공간 복잡도: O(n)
    """
    seen = set()
    duplicates = set()
    
    # TODO: 각 원소를 순회하면서
    ## 이미 seen에 있으면 duplicates에 추가
    ## 없으면 seen에 추가
    for n in nums:
        if n in seen:
            duplicates.add(n)
        else:
            seen.add(n) 
    
    return list(duplicates)

 

유클리드 호제법

GCD(a , b)=GCD(b , a%b)

LCM(a , b)= (aXb) / GCD(a,b)