집 짓는 개발블로그

👀  Memoization과 Tabulation(DP)   https://www.codetree.ai/missions/2/problems/fibonacci-number/introduction 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai  DP를 안다면 Memoization과 Tabulation, Top-down과 Bottom-up이라는 단어들도 들어봤을 것이다.그와 동시에 DP를 제대로 공부해본 적이 없는 나같은 사람이라면 뭐가 뭔지 잘 모를 것이다.   결론부터 말하자면, Memoization이 Top-Down이고 Tabulation이 Bottom..

👀  Dictionary  https://www.codetree.ai/missions/8/problems/hashmap-basic/description 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai  시간초과 날 것 같으면 무조건 떠올리게 되는 딕셔너리에 대해 알아본다. 파이썬의 dict는 HashMap 자료구조로 되어있고, 데이터를 (key, value) 쌍 형태로 관리한다. HashMap의 가장 큰 특징은 1) 순서가 없고 2) key로 value에 접근하는 시간복잡도가 매우 작다. 다음 링크의 게시물을 참고했을 때 시간복잡도는 Access에 N/..

👀  백트래킹(Backtracking)  정처기 보고 땡땡이친 사이에 우리 학교 이용권이 사라질 위기에 처했다.누추한 글이라도 기간 안에 인증되기를🙏 (plz)  https://www.codetree.ai/missions/2/problems/n-permutations-of-k-with-repetition/introduction 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 오늘은 백트래킹에 대한 글이다.백트래킹의 핵심은 재귀를 돌리는 도중에, 다음 depth의 함수를 호출한 뒤 '갱신 취소' 하는 것이라고 생각한다.    다음과 같은 코드를 이해하지..

👀  다이나믹 프로그래밍(DP) 쓰는 김에 드디어 DP를 제대로 공부해봤다.  코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 기본 문제인 격자 안에서 한 칸씩 전진하는 DP 문제의 해설을 읽으면서 기본 개념을 이해하고, 같은 유형의 문제들을 풀면서 학습하는 방식인 것 같다.  문제를 보다가 이거 점화식 나오겠는데? 싶으면 점화식을 세워보면 된다. 대략의 풀이 순서는 이렇다.1) 값 저장을 위한 빈 DP 테이블 만들기 (주로 편의를 위해 0으로 채워둠)2) DP 테이블에 초기조건부터 저장 (initialize 등의 이름으로 별도의 함수를 만들기도 함)3..

https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr소요시간: 30분이렇게 알고리즘 뭐 쓰라고 써있는데도 한참 헤맬때 마음이 참 아프다. ^^    제출한 코드(통과는 되는데 함정이 있음)import heapqdef solution(genres, plays): ans = [] # 장르별로 2개씩 # 순서: 1) 많이 재생된 장르(재생수 총합) 2) 장르 내에서는 많이 재생된 노래 먼저 3) if 하나면 하나만 수록하기 genre_t..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

def combinations(n, new_arr, c): if len(new_arr) == n: arrs.append(new_arr) return for i in range(c, len(arr)): combinations(n, new_arr + [arr[i]], i)위 코드에서 combinations(1, [], 2) 를 실행하면 전역변수 arrs가 [[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7]] 가 된다.  이제 마지막 줄에 return 하나만 붙여보자.def combinations(n, new_arr, c): if len(new_arr) == n: arrs.append(new_ar..

https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr    처음 제출한 코드import heapqdef solution(operations): heap = [] for operation in operations: if operation.startswith("I"): num = int(operation.split()[1]) heapq.heappush(heap, num) elif o..