https://programmers.co.kr/learn/courses/30/lessons/60058 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr * 해결 못 함 # 문자열 p를 u, v로 분리하는 함수 def divide(p): open = 0 close = 0 for i in range(len(p)): if p[i] == '(': open += 1 else: close += 1 if open == close: return p[:i + 1], p[i + 1:] # 문자열 u가 올바른 괄호 문자열인지 확인하..
Python
다이나믹 프로그래밍: 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘 최적 부분 구조: 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성 대부분의 재귀 알고리즘은 최적 부분 구조 문제를 풀 수 있음 중복된 하위 문제들의 결과를 저장해뒀다가 풀이해나감 알고리즘 풀이 가능한 문제들의 특징 풀이 가능한 문제 및 알고리즘 다이나믹 프로그래밍 - 최적 부분 구조 - 중복된 하위 문제들 - 0-1 배낭 문제 - 피보나치 수열 - 다익스트라 알고리즘 그리디 알고리즘 - 최적 부분 구조 - 탐욕 선택 속성 - 분할 가능 배낭 문제 - 다익스트라 알고리즘 분할 정복 - 최적 부분 구조 - 병합 정렬 - 퀵 정렬 다익스트라 알고리즘 - 최적 ..
분할 정복: 다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임 직접 해결할 수 있을 정도로 간단한 문제가 될 때 까지 문제를 재귀적으로 쪼개나간 다음(분할), 그 하위 문제의 결과(정복)들을 조합하여 원래 문제의 결과로 만듦(조합) 재귀를 활용하는 대표적인 알고리즘, 최적 부분 구조 169. Majority Element - 브루트 포스 -> 하나하나 count() 메소드로 세다가 과반수인 요소 나오면 리턴 - 다이내믹 프로그래밍 -> 리스트 순회하며 처음 출현한 요소는 count()메소드로 세고, 나왔던 요소는 과반수인지 확인 - 분할 정복 -> 재귀적으로 쪼갠 후 과반수 후보 하나만 상위로 계속 리턴 ※ 비교 연산자로 true | false 반환하여 1 | 0으로 활용 - 리스트를 정렬하면 정..
그리디 알고리즘: 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘 대부분 뛰어난 결과를 도출하지 못하지만, 드물게 최적해 보장 최적해를 찾을 수 있으면 그것을 목표로 삼고, 그것이 어렵다면 주어진 시간 내에 최적에 가까운 해를 찾음 탐욕 선택 속성 + 최적 부분 구조 에 해당하는 문제에 좋다 탐욕 선택 속성: 앞의 선택이 이후 선택에 영향을 주지 않는 것 최적 부분 구조: 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우 예) 다익스트라, 허프만 코딩, ID3 DP vs Greedy DP: 하위 문제에 대한 최적 솔루션을 찾고, 이 결과들을 결합한 정보로 전역 최적 솔루션 선택 Greedy: 각 단계마다 로컬 최적해를 찾는 문제로 접근..
슬라이딩 윈도우: 고정 사이즈의 윈도우가 이동하며 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘 정렬 여부와 관계없이 사용 좌 또는 우 한 방향으로만 이동 교과서에 정의된 내용이 아니며, 투 포인터와 혼용하여 쓰기도 하고, 원래 네트워크에서 사용되던 알고리즘 이름 정렬 여부 윈도우 사이즈 이동 투 포인터 대부분 O 가변 좌우 포인터 양방향 슬라이딩 윈도우 X 고정 좌 또는 우 단방향 239. Sliding Window Maximum - 브루트 포스 - 큐로 최적화 -> 윈도우 이동하여 최댓값 계산 시, 이전 윈도우의 최댓값이 빠질 때만 새로 계산 ※ 고정된 윈도우 크기로 탐색하면서 필요한 계산 수행 (가능하면 계산 최소화하여 구현) 76. Minimum Window Substring - 브루..
부울 연산자: NOT, AND, OR (기본), XOR (보조) 기본 연산자를 조합해 보조 연산 가능 XOR: TT, FF 일때는 F 반환, TF, FT 일때는 T 반환 # XOR x = y = True (x and not y) or (not x and y) >>> False 비트 연산자 ~ : (2의 보수) - 1, 십진수로는 -x-1, 부울 변수 True에 적용하면 -1-1 = -2 True & False # Bitwise AND >>> False True | False # Bitwise OR >>> True True ^ True # Bitwise XOR >>> False ~ True # Bitwise NOT >>> -2 # 십진수와 마찬가지로 연산 bin(0b0110 + 0b0010) >>> '0b..
이진 검색: 정렬된 배열에서 타겟을 찾는 검색 알고리즘 값을 찾아내는 시간 복잡도가 O(logn) 704. Binary Search - 재귀로 이진 검색 * 파이썬은 재귀 호출 횟수 제한이 1000번으로 정해져있으므로 유의 (sys 모듈로 변경가능하지만 대부분 지원하지 않음) - 반복으로 이진 검색 - 이진 검색 모듈 bisect - index() * 최악의 경우 O(n)으로, 앞에서부터 탐색하므로 뒤에 위치할수록 느려진다 bisect.bisect(iterable, value)는 bisect.bisect_right(iterable, value)와 같으며 value 값이 iterable에 정렬되어 삽입된다면 위치할 인덱스 값 리턴 -> value 값과 동일한 값이 이미 iterable에 있다면 그 값 우측..
정렬 알고리즘: 목록의 요소를 특정 순서대로 넣는 알고리즘, 대게 숫자식 순서와 사전식 순서로 정렬 버블 정렬(O(n^2)): 배열의 요소를 끝까지 순차적으로 탐색하며 연달아 있는 2개의 요소의 순서가 맞지 않으면 스왑 병합 정렬(O(nlogn)): 배열을 더 이상 분할이 안될때까지 반씩 나누고, 요소들을 정렬하면서 이어붙힌다 대부분의 경우 퀵 정렬보다 느리지만 일정한 속도와 안정 정렬인 점 때문에 많이 쓰인다 퀵 정렬(O(nlogn)): 분할 정복 알고리즘에 피벗 개념을 추가해 피벗보다 작으면 왼쪽, 크면 오른쪽에 배치되게 분할 이미 정렬된 배열이 입력되는 등의 비효율적인 상황에서는 O(n^2) 가장 간단한 분할 알고리즘인 로무토 파티션은 피벗이 가장 오른쪽 요소 안정 정렬: 입력된 순서가 다른 기준으..
트라이: 검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조 특히 자연어 처리 분야에서 문자열 탐색을 위한 자료구조로 널리 쓰인다 검색을 뜻하는 'retrieval'에서 따옴 다진 트리의 형태 각 문자열 길이만큼만 탐색하면 원하는 결과 찾을 수 있다 208. Implement Trie (Prefix Tree) - TrieNode 클래스 생성해 딕셔너리로 노드 값 정보, 불리안으로 해당 노드에서 단어 완성 여부 정보를 각 노드에 담는다 -> 삽입이나 검색하려는 문자열 갯수만큼 반복하여 각 노드의 딕셔너리 확인하며 필요한 작업 수행 336. Palindrome Pairs - 부르트 포스 -> 시간 초과 O(n^2) - 트라이 구현 -> 입력..
힙: 힙의 특성(최소 힙에서는 부모가 항상 자식보다 작거나 같다)을 만족하는 거의 완전한 트리 파이썬에는 최소 힙만 구현(heapq 모듈) 우선순위 큐에서 가장 작은 값을 가져올때 매번 최소 힙의 루트를 가져오면 된다 부모 자식 간의 관계만 정의하므로 정렬된 구조가 아님 자식이 둘인 힙은 이진 힙이라 하며, 이진 트리와 마찬가지 이유로 대부분 이진 힙이 널리 사용됨 배열에 순서대로 표현하기 좋으며, 편한 계산을 위해 인덱스는 1부터 사용 다익스트라 알고리즘, 힙 정렬, 최소 신장 트리, 프림 알고리즘, 중앙값의 근삿값 힙 연산(최소 힙): 삽입(업힙) -> O(logn), 추출(다운힙) -> O(logn), 이진 힙은 조회할 때 O(1) 삽입: 요소를 최하위 레벨의 가장 왼쪽으로 삽입 -> 부모와 비교 ..
