본문 바로가기
반응형

Problem Solving242

백준 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.
백준 10799번 쇠막대기 - C++ 풀이 1. 여는 괄호를 만나면 막대를 쌓는다. 2. 레이저의 닫는 괄호를 만나면 쌓인 막대 개수만큼 조각이 생성된다. 3. 막대의 닫는 괄호를 만나면 조각이 1개 생성된다. 1. 여는 괄호를 만나면 막대를 쌓는다. 여는 괄호를 만나면 막대의 시작점이므로 막대를 쌓아준다. 쌓인 막대의 개수를 저장해둘 것이다. 이때 여는 괄호가 막대의 시작이 아니라 레이저일 수도 있는데, 막대 개수를 -1부터 카운트하면 따로 예외 처리하지 않아도 된다. 2. 레이저의 닫는 괄호를 만나면 쌓인 막대 개수만큼 조각이 생성된다. 레이저의 닫는 괄호를 만나면, 쌓인 막대 개수만큼 조각이 생성된다. 직전 괄호가 여는 괄호라면 레이저인 것으로 판단할 수 있다. 3. 막대의 닫는 괄호를 만나면 조각이 1개 생성된다. 레이저의 닫는 괄호가 아.. 2022. 6. 17.
반응형

티스토리툴바