본문 바로가기
반응형

알고리즘207

백준 1450번 냅색문제 - C++ 풀이 1. 전체 물건을 두 그룹으로 나눈 뒤, 각 그룹에서 가능한 모든 조합을 탐색하여 기록해둔다. 2. A그룹에서 무게 w를 만들 수 있다면, B그룹에서 무게 C-w 이하를 만들 수 있어야 한다. 3. A그룹에서 만들 수 있는 모든 무게에 대해, 이분 탐색을 이용하여 B그룹에서 C-w이하를 만드는 조합의 수를 구한다. 1. 전체 물건을 두 그룹으로 나눈 뒤, 각 그룹에서 가능한 모든 조합을 탐색하여 기록해둔다. 모든 조합의 수는 2^N, N=30이므로 브루트 포스로는 제한시간 내에 통과할 수 없다. 이런 경우 두 그룹으로 쪼개 조합의 가짓수를 줄이는 방법을 사용할 수 있다. 두 그룹 A, B로 나눈 뒤, 각 그룹에서 가능한 모든 조합을 탐색하여 기록해두자. 이 과정의 시간복잡도는 O(2^N/2). 2. A그.. 2022. 7. 1.
백준 12837번 가계부 (Hard) - C++ 풀이 1. 세그먼트 트리를 이용하여 update / sum 쿼리를 수행한다. 1. 세그먼트 트리를 이용하여 update / sum 쿼리를 수행한다. 계속 변화하는 배열에서 구간 쿼리를 수행하는 문제는 세그먼트 트리를 이용하여 해결할 수 있다. 1번 쿼리가 들어올 경우 p번째 값을 x만큼 업데이트하는 연산을, 2번 쿼리가 들어올 경우 p번째 원소부터 q번째 원소까지의 구간합을 구해주면 된다. #include #include using namespace std; typedef long long ll; struct Segtree { int n; vector tree; Segtree (vector& X) { n = X.size(); tree.resize(n*4); init(X, 0, n-1, 1); } void in.. 2022. 6. 29.
백준 1285번 동전 뒤집기 - C++ 풀이 1. 각 행을 뒤집을지 여부를 고정한다. 2. 각 열을 뒤집을지 말지 여부를 tail 개수가 최소가 되도록 그리디 하게 정한다. 1. 각 행을 뒤집을지 여부를 고정한다. 행이 최대 20개, 열이 최대 20개이므로 각 행과 열에 대해 뒤집을지 말지 여부를 결정하는 경우의 수는 2^40가지이다. 따라서 브루트 포스로는 시간 내에 해결할 수 없다. 먼저 행에 대해서만 뒤집을지 여부를 결정해주자. 경우의 수는 2^20가지로 줄어든다. 2. 각 열을 뒤집을지 말지 여부를 tail 개수가 최소가 되도록 그리디하게 정한다. 행을 뒤집을지 말지 여부를 결정하고 나면, 이제 각 열의 뒤집을지 말지 여부는 그리디 하게 정할 수 있게 된다. 각 열끼리는 서로 영향을 미치지 않으므로, 각 열에 대해 뒤집는 경우와 뒤집지 않는.. 2022. 6. 28.
백준 15684번 사다리 조작 - C++ 풀이 1. i번 세로줄과 (i+1)번 세로줄 사이에 가로줄을 놓으면 i와 (i+1)의 위치가 바뀐다. 2. 백트래킹으로 최대 3개의 가로선을 놓는 경우를 모두 시도해본다. 1. i번 세로줄과 (i+1)번 세로줄 사이에 가로줄을 놓으면 i와 (i+1)의 위치가 바뀐다. i번 세로줄과 (i+1)번 세로줄 사이에 가로줄을 놓으면, 원래 결과 (i, i+1)에서 (i+1, i)로 결과가 바뀐다. 두 세로줄의 위치를 스왑한 것과 같은 효과를 얻게 된다. 이 사실을 이용하여 그어진 가로줄의 목록을 가지고 사다리 게임의 결과를 계산할 수 있다. (아래 코드에서 check() 함수 구현을 참고) 2. 백트래킹으로 최대 3개의 가로선을 놓는 경우를 모두 시도해본다. 백트래킹을 이용하여 최대 3개의 가로선을 긋는 경우를 모두 .. 2022. 6. 24.
백준 10974번 모든 순열 - C++ 풀이 1. DFS를 사용하여 모든 순열을 구한다. 2. DFS 과정에서 각 숫자의 사용 여부는 비트 마스크로 나타낼 수 있다. 1. DFS를 사용하여 모든 순열을 구한다. DFS를 돌면서, 매 depth마다 선택한 적 없는 숫자 중 하나의 숫자를 선택하면 모든 순열을 구할 수 있다. 2. DFS 과정에서 각 숫자의 사용 여부는 비트 마스크로 나타낼 수 있다. 이때 각 숫자를 이전 depth에서 선택했었는지 여부를 비트 마스크로 나타내어 준다. #include #include using namespace std; int N; vector permu; void DFS(int depth, int mask) { if (depth == N) { for (auto x : permu) cout 2022. 6. 23.
반응형

티스토리툴바