먼저, 많은 알고리즘 중 배낭 문제를 꼽은 이유는 다음과 같다... 최근에 응시한 코테에 나왔는데 풀지 못했다. 문제를 보자마자 배낭 문제라는 것을 알았고, 심지어 DP 문제라는 것도 알았다. 하지만 1차원 배열을 써야 하는지, 2차원 배열을 써야하는지 상세한 풀이 방법이 생각나지 않았다.대충, 점화식의 형태도 기억이 났지만, 결과적으로는 풀지 못했다. 그래서 다시 한 번 공부를 하면서, 다음 번에는 꼭 한 번에 풀 수 있도록 하고자 한다. 🔍 배낭 문제란?배낭 문제는 유한한 용량을 가진 배낭과 여러 개의 물건들이 주어졌을 때, 배낭에 담을 수 있는 물건들의 조합을 찾아 그 가치의 합이 최대가 되도록 하는 문제이다. 각 물건은 고유한 가치와 무게를 가지며, 물건을 쪼개서 넣을 수 없다는 제약(0-1 ..
코딩테스트 문제를 풀 때, 입력의 크기 n에 대해 시간초과가 나지 않도록 알고리즘을 고려해야 한다.이 사실을 알고 있지만, 항상 특정 시간복잡도에 대해 n의 크기를 어느정도까지 가져갈 수 있는지를 까먹어 해당 글을 작성하게 됐다. 1️⃣ 입력의 크기에 따른 시간복잡도입력의 크기시간복잡도대표 알고리즘n \[O(n!)\]완전탐색n \[O(2^n)O(n^2*2^n)\]Bitmask DPn \[O(\sqrt{2}^n)\]MITMn \[O(n^3)\]Matrix Chain Multiplication(행렬 곱셈)n \[O(n^2)\] n \[O(n\sqrt{n})O(n\log^{2}n)\]모스(Mo's) 알고리즘n \[O(n\log n)\]정렬, LIS(최장 증가 부분 수열)n \[O(n)\]DP, DFS, Tre..
해당 글에서는 텀 프로젝트 문제를 Python을 이용해 풀이하고자 한다. 9466번: 텀 프로젝트이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을www.acmicpc.net 원래는 이 문제를 풀 생각이 아니었지만, 아래에 있는 Union-Find를 통해 무방향 그래프의 사이클을 구하는 알고리즘에 대해 공부하다가, 방향 그래프에서 사이클을 구하는 방법이 궁금해져 찾아보다가 해당 문제를 풀게 됐다. [알고리즘] Union-Find(유니온 파인드)로 무방향 그래프에서 사이클(cycle) 찾기1️⃣ 유니온 파인드란?Union-Find는 서로소 집합을 찾는 알고리즘으로, 서로..
해당 글에서는 큰 수 만들기 문제를 Python을 이용해 풀이하고자 한다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔷 문제 설명 더보기 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장..
