이것저것 코딩하는 블로그

0. 문제 link: https://www.codetree.ai/missions/6/concepts/35/problems/dp-knapsack-2/introduction 코드트리 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 도둑이 보석방을 털러 갔다고 하자. (사견이지만 프로그래밍 문제에는 부도덕한 놈들이 많다..해킹하는 놈 터는 놈 등등..) 이 때 도둑 가방의 크기는 n이며, 이보다 더 무겁게 담을 수는 없다. 보석은 종류별로 단 하나씩만 있다. 도둑방에 있는 보석의 무게와 가격이 주어졌을 때, 도둑이 훔쳐올 수 있는 보석들의 가격의 합의 최대를 구하는 문제이다. 1. 풀이 이는 동적계획법으로..

0. 문제 link: https://www.codetree.ai/missions/6/concepts/35/problems/minimum-edit/description 코드트리 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai (추천글을 하도 써서 광고를 의심받을 것 같긴 한데..진짜 좋다..광고비는 따로 안 받는다) (당연함 누가 이런 하루에 5명오는 블로그에 광고를 걸어) 편집 거리란, 문자열 A, B가 주어졌을 때, 문자열 A를 문자열 B로 바꾸기 위해 필요한 최소 변경 횟수를 의미한다. 변경은 하나의 문자를 변경하거나, 삭제하거나, 원하는 위치에 삽입하는 경우가 있다. 1) 변경, 삭제만 가능할 ..

0. 문제 link: https://www.codetree.ai/missions/6/concepts/35/problems/dp-lcs-2/introduction 코드트리 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai LCS (Longest Common Subsequence) 란 최장 공통 부분 수열이다. 부분 수열이란 문자열 내에서 순서대로 뽑아서 나올 수 있는 수열을 의미한다. 그 중 두 문자열에게 공통으로 부분 수열인 경우 공통 부분 수열이라고 하며, 이 중 길이가 가장 긴 경우를 최장 공통 부분 수열이라고 한다. 예를 들면 ABABA와 BAAB의 LCS는 BAB이다. 여기서 구하고자 하는 것은..

0. 문제 link: https://www.codetree.ai/missions/6/concepts/35/problems/dp-lis-2/description 코드트리 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 유료 사이트여서 누구나 접근할 수는 없지만, 자료구조 개념을 정리하기 유용하다. 코딩 테스트, cs 면접을 준비한다면 추천한다. 부분 수열이란, 간단히 말하자면 모든 원소의 부분집합을 만들되, 원소의 순서를 지키는 것을 의미한다. 예를 들면, [10, 30, 50, 40] 에서 [10, 30]은 부분 수열이지만 [10, 30, 40]은 부분 수열이 아니다. 감소하는 부분 수열은 부분 수열..

0. 문제 codetree의 은행 문제이다. link: https://www.codetree.ai/missions/6/concepts/35/problems/dp-modeling-bank/description 코드트리 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 유료 사이트이긴 하지만 자료구조 개념을 정리하기 유용하다. 코딩 테스트, cs 면접을 준비한다면 추천한다. 가치가 1, 4, 5, 9개인 4개의 동전이 있을 때, 주어진 금액 n을 거슬러주기 위한 필요한 최소 동전의 수를 구해보려고 한다. 1. 풀이 Dynamic Programming (동적 계획법) 을 이용한 문제다. 간단히 설명하면, 하..

0. lower bound / upper bound란? 만약 내가 찾는 값(타겟)이 배열에 여러 개 있다면, 이진 탐색을 실행했을 때 어떤 위치가 나오게 될 지 모른다. 따라서 우리는 이런 경우를 방지하고자 lower bound, upper bound를 사용한다. lower bound란 타겟 이상의 값이 최초로 나오는 위치를 의미한다. upper bound란 타겟을 초과하는 값이 최초로 나오는 위치를 의미한다. 따라서 타겟은 lower bound와 upper bound 사이에 있을 것이므로, 타겟이 여러 개일 때 타겟의 갯수를 세는 것이 가능해진다. 만약 타겟이 배열 내에 없다면, upper bound - lower bound = 0이 될 것이다. 타겟 이상의 값과 타겟 초과의 값이 동일하다는 것은 타겟..