pythaac의 개발노트

추천 알고리즘 종류 협업 필터링 (Collaborative Filtering) Memory-based Approach - User-based Filtering - Item-based Filtering Model-based Approach - Matrix Factorization 콘텐츠 기반 필터링 (Contents-based Filtering) 정의 유저-아이템 간 상호작용 데이터를 활용하는 방법 - ex) 이 영화를 좋아하는 다른 사람이 좋아하는 영화 콘텐츠 기반 필터링과 비교 - 정의 : 콘텐츠 특성을 기반으로 추천하는 방법 - ex) 내가 좋아하는 감동, 장르 등을 활용 특징 장점 일반적으로 Content-based보다 성능이 좋음 도메인에 의존되지 않음 쉽게(학습없이, 산술연산으로) 만들 수 있음..

알고리즘의 고비, DP 학부생 때 알고리즘 수업을 들을 때 DP는 너무 쉬운 과목이었습니다. 메모이제이션으로 계산양을 줄인다는 이야기 외에는 이해를 못했기 때문입니다. 석사과정에서 알고리즘은 한학기 내내 DP 문제만 다루는 내용이었습니다. 그 때서야 저는 점화식이 눈에 들어왔고, substruct를 정의해내야 한다는 사실을 알았으며, 2차 배열이 많이 활용된다는 정도 이해하였습니다. 알고리즘에서 DP는 어려운 단원에 속하고, 그렇기 때문에 몇 년 전에는 풀었던 문제도 다시 풀면 못풀고 잊어버리는 듯 합니다. 지금 코딩테스트를 공부하면서, 얼핏 이해했다고 생각한 DP를 활용하지 못하는 제 자신을 보면서 확실한 이해가 필요하다고 생각했습니다. BOJ 2616 소형기관차 제가 간과했던 사실 중 하나는 점화식의..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 g 이상인 값을 s와 매칭할 수 있는 최대 개수 책에서 구현된 코드 # 그리디 알고리즘 from typing import List class Solution: def findContentChildren(self, g: List[int], s: List[int]) -> int: g.sort() s.sort() child_i = cookie_j = 0 # 만족하지 못할 때까지 그리디 진행 while child_i = g[child_i]: child_i += 1 cookie_j += 1 return child_i # 이진 탐색 ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 주유소를 원형 큐에서 시계방향으로 돌 때, 현재 채울 수 있는 gas와 다음 주유소의 cost로 모든 주유소에 도달할 수 있는 시작점 출력 책에서 구현된 코드 from typing import List class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: # 모든 주유소 방문 가능 여부 판별 if sum(gas) < sum(cost): return -1 start, fuel = 0, 0 for i in range(len(gas)): # 출발점이 안되는 지점 판별 if gas[i] + fuel < cost[i]..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 n개 안에 겹치는 문자가 없도록 배열, 불가능할 경우 "idle"을 삽입하여 최소 길이 출력 책에서 구현된 코드 import collections from typing import List class Solution: def leastInterval(self, tasks: List[str], n: int) -> int: counter = collections.Counter(tasks) result = 0 while True: sub_count = 0 # 개수 순 추출 for task, _ in counter.most_common(n + 1): sub_count += 1 result += 1 counter.s..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 (내 키, 앞에 줄 선 사람 중 내 키 이상인 사람)이 주어질 때 재정렬 책에서 구현된 코드 import heapq from typing import List class Solution: def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]: heap = [] # 키 역순, 인덱스 삽입 for person in people: heapq.heappush(heap, (-person[0], person[1])) result = [] # 키 역순, 인덱스 추출 while heap: person = heapq.heappop(heap) resul..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 주식 가격이 시간순으로 주어질 때 최대 이익 출력 책에서 구현된 코드 from typing import List class Solution: def maxProfit(self, prices: List[int]) -> int: # 0보다 크면 무조건 합산 return sum(max(prices[i + 1] - prices[i], 0) for i in range(len(prices) - 1)) 기억해야할 기법 "그리디 알고리즘으로 접근해야한다"는 힌트를 어디서 얻을 수 있을까 문제를 잘 해석하면 모든 이익의 합산이다 sell & buy를 동시에 할 수 있다는 것을 캐치하면 쉬운 문제였다 나는 나중에 팔았을 때 ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 요약 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘 (코딩 테스트에서의 정의를 의미하는듯? -> 항상 글로벌 최적을 찾기는 어려울 듯) 그리디 알고리즘 드물게 최적해를 보장하는 경우도 있음 보통 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼음 최적해를 찾을 수 있는 두 가지 조건 탐욕 선택 속성 (Greedy Choice Property) - 앞의 선택이 이후 선택에 영향을 주지 않음 - 즉, 문제 해결 과정 중 substructure마다 독립적인 문제 해결 최적 부분 구조 (Optimal Substructure) - 문제의 최적 해결 방법이 부분 문제에 대한..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 문자열 s에 대해 k개를 변경하여 만들 수 있는 가장 긴 반복문자열의 길이 출력 책에서 구현된 코드 class Solution: def characterReplacement(self, s: str, k: int) -> int: left = right = 0 counts = collections.Counter() for right in range(1, len(s) + 1): counts[s[right - 1]] += 1 # 가장 흔하게 등장하는 문자 탐색 max_char_n = counts.most_common(1)[0][1] # k 초과시 왼쪽 포인터 이동 if right - left - max_char_n..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 t의 모든 문자, 개수가 포함된 s의 최소 윈도우 출력 책에서 구현된 코드 import collections class Solution: def minWindow(self, s: str, t: str) -> str: need = collections.Counter(t) missing = len(t) left = start = end = 0 # 오른쪽 포인터 이동 for right, char in enumerate(s, 1): missing -= need[char] > 0 need[char] -= 1 # 필요 문자가 0이면 왼쪽 포인터 이동 판단 if missing == 0: while left < right..