반응형 분류 전체보기282 백준 1943번 동전 분배 - C++ 풀이 1. 동전들의 금액 합이 홀수인 경우 절대 둘로 나눌 수 없다. 2. dp(idx, price): [idx...]번 동전들로 price원을 만들 수 있는가 3. dp(idx, price) = max(dp(idx+1, price - coin*cnt)) (0 ≤ cnt ≤ idx번 동전개수) 1. 동전들의 금액 합이 홀수인 경우 절대 둘로 나눌 수 없다. 만약 동전들의 금액 합이 홀수인 경우 절대 둘로 나눌 수 없다. 짝수인 경우에는 sum/2를 만들 수 있는지 확인해보면 된다. 1. dp(idx, price): [idx...]번 동전들로 price원을 만들 수 있는가 dp(idx, price)를 위와 같이 정의하자. 우리가 최종적으로 구하려는 값은 dp(0, sum/2)이다. (이때 sum은 주어진 동전들.. 2023. 8. 12. [RxSwift] 리액티브 프로그래밍 Reactive Programming, Rx, 그리고 RxSwift에 대해 알아보자. Reactive Programming 반응형 프로그래밍은 데이터 스트림과 변화의 전파와 관련된 선언적 프로그래밍 패러다임이다. (출처: Wikipedia - Reactive Programming) 리액티브 프로그래밍의 목적은 데이터 스트림을 통해 데이터의 변화를 전파시키고, 변화에 따라 자동으로 반응하는 방식으로 프로그래밍을 구성하는 것이다. 이때 데이터 스트림이란 시간에 따라 연속적으로 발생하는 데이터의 흐름을 나타내는 개념으로, 데이터 시퀀스라고 생각할 수 있다. 초기값이 0인 A라는 변수가 매초마다 1씩 증가한다고 가정하자. 이를 데이터 스트림으로 만들면 처음에 0이, 1초 후에는 1이, 2초 후에는 2가 흐르게 .. 2023. 8. 12. 백준 4179번 불! - C++ 풀이 1. 각 칸에 불이 번지는 시각을 BFS로 시뮬레이션하여 구해둔다. 2. 지훈이의 이동을 BFS로 시뮬레이션한다. 1. 각 칸에 불이 번지는 시각을 BFS로 시뮬레이션하여 구해둔다. 불이 매 초마다 상하좌우로 한 칸씩 퍼져나가므로, BFS를 이용하여 시뮬레이션 할 수 있다. 각 칸에 불이 번지는 시각을 구해두자. 이는 최초 불로부터의 거리와 같다. 2. 지훈이의 이동을 BFS로 시뮬레이션한다. 지훈이 또한 매 초마다 상하좌우로 이동할 수 있으므로, BFS를 이용하여 시뮬레이션 할 수 있다. 지훈이가 각 칸에 도착하는 시각 또한 최초 위치에서의 거리와 같다. 따라서 이제 지훈이가 특정 칸에 도착하는 시각과 그 칸에 불이 번지는 시각을 비교하면, 불이 번지기 전에 특정 칸에 도착했는지를 알 수 있다. 불이 .. 2023. 8. 10. 백준 1890번 점프 - C++ 풀이 1. dp[r][c] : (r, c)에서 도착지점까지 가는 경로의 수 2. dp[r][c] = dp[r + board[r][c]][c] + dp[r][c + board[r][c]] 1. dp[r][c] : (r, c)에서 도착지점까지 가는 경로의 수 dp[r][c]를 위와 같이 정의하자. 기저사례는 도착지점인 경우가 되겠다. 2. dp[r][c] = dp[r + board[r][c]][c] + dp[r][c + board[r][c]] 각 칸에서 board[r][c]만큼 아래쪽으로 가는 방법과 오른쪽으로 가는 방법이 있으므로 이 두가지 방법으로 이동했을 때의 경로의 수를 더해주면 된다. 이때 점프 거리가 보드 밖으로 넘어가지 않는지 체크해주어야 하고, 만약 board[r][c] = 0인 경우 그 자리에서 .. 2023. 8. 9. 백준 1406번 에디터 - C++ 풀이 1. 모든 쿼리는 커서를 기준으로 이루어진다. 2. 커서보다 왼쪽에 있는 문자들과 오른쪽에 있는 문자들을 각각 스택으로 관리한다. 1. 모든 쿼리는 커서를 기준으로 이루어진다. 포인트는 모든 쿼리가 커서를 기준으로 이루어진다는 것이다. 2. 커서보다 왼쪽에 있는 문자들과 오른쪽에 있는 문자들을 각각 스택으로 관리한다. 따라서 커서 직전, 직후 문자들만 쿼리 대상이다. 이에 적합한 자료구조인 스택을 사용한다. 커서보다 왼쪽에 있는 문자들을 한 스택에 모아두고, 커서보다 오른쪽에 있는 문자들을 또 다른 스택으로 묶어 관리한다. 접근 가능한 top이 커서 쪽이 되는 순서로 저장해야 한다. 그러면 이제 모든 쿼리를 간단하게 구현할 수 있다. 왼쪽, 오른쪽 문자들이 담긴 스택을 각각 lst, rst라 하자. L:.. 2023. 8. 9. 이전 1 2 3 4 5 6 7 ··· 57 다음 반응형
