집 짓는 개발블로그

👀  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..