본문 바로가기
반응형

전체 글282

백준 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.
[iOS] SwiftUI Text Fade 애니메이션 구현하기 아래 이미지와 같이 Text의 값이 바뀔 때 기존 값은 Fade Out 되고, 새로운 값은 Fade In 되는 애니메이션을 구현하고 싶었다. 페이드 인/아웃이 opcaity 변화이므로 .transition(.opacity)를 적용하고, count 값을 변경할 때 withAnimation을 사용하면 원하는 결과가 나올 것이라고 생각했는데, 결과는.. Text("\(count)") .transition(.opacity) withAnimation(.easeInOut(duration: 0.3)) { count += 1 } opacity는 그대로고 이상하게 움찔거리는 애니메이션만 적용되었다ㅠㅠ opacity transition이 제대로 작동하지 않은 이유는 transition은 뷰가 삭제/생성될 때만 적용되기 때.. 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.
반응형

티스토리툴바