https://programmers.co.kr/learn/courses/30/lessons/67257/ 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 내 풀이: from itertools import permutations # 수식을 해당 연산자에 대해 연산한 후의 수식 리턴 def calculate(operator, expression): new_exp = [] i = 0 while i < len(expression): if expression[i] == operator: new_exp.append(st..
CS
https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 내 풀이: from collections import defaultdict from ite..
https://programmers.co.kr/learn/courses/30/lessons/17677 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 내 풀이: from collections import defaultdict def make_table(str): table = defaultdict(int) for i in range(len(str) - 1): if str[i:i + 2].isalpha(): table[str[i:i + 2].lower()] += 1 return table ..
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가 올바른 괄호 문자열인지 확인하..
다이나믹 프로그래밍: 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘 최적 부분 구조: 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성 대부분의 재귀 알고리즘은 최적 부분 구조 문제를 풀 수 있음 중복된 하위 문제들의 결과를 저장해뒀다가 풀이해나감 알고리즘 풀이 가능한 문제들의 특징 풀이 가능한 문제 및 알고리즘 다이나믹 프로그래밍 - 최적 부분 구조 - 중복된 하위 문제들 - 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에 있다면 그 값 우측..
