티스토리

다듬고 고침

검색하기

블로그 홈

다듬고 고침

please-amend.tistory.com/m

공부기록 남기는 블로그

구독자: 1

방명록 방문하기

반응형

주요 글 목록

백준 9184번 신나는 함수 실행 - C++ 풀이 1. 메모이제이션을 통해 시간을 줄일 수 있다. 2. 재귀 함수를 똑같이 구현하되, 이미 구했던 값이라면 재귀호출을 하지 않고 저장해둔 값을 바로 리턴한다. 1. 메모이제이션을 통해 시간을 줄일 수 있다. 단순한 재귀 호출을 통해 w(a, b, c)를 구할 경우 중복되는 호출이 많아진다. 20 이하의 a, b, c 에 대해서만 구해주면 되므로 총 구해야 하는 함수값은 20^3개 뿐이다. 모든 (a, b, c)에 대해 w(a, b, c) 값을 저장해두자. 2. 재귀 함수를 똑같이 구현하되, 이미 구했던 값이라면 재귀호출을 하지 않고 저장해둔 값을 바로 리턴한다. 재귀 함수를 똑같이 구현하되, 만약 이미 구했던 값이라면 재귀호출을 하지 않고 저장해두었던 값을 바로 리턴해주면 된다. #include #incl.. 공감수 0 댓글수 0 2023. 9. 4.
백준 2563번 색종이 - C++ 풀이 1. 도화지를 100X100 그리드로 나눈다. 2. 각 색종이를 추가하면서 그리드에 색종이가 붙어있음을 표시한다. 3. 모든 그리드를 탐색하면서 색종이가 붙은 그리드의 개수를 센다. 1. 도화지를 100X100 그리드로 나눈다. 색종이가 붙은 영역의 넓이를 구해야 한다. 넓이 계산을 쉽게 하기 위해 각 칸의 넓이가 1이 되도록 그리드를 그린다. 100X100으로 나누면 된다. 2. 각 색종이를 추가하면서 그리드에 색종이가 붙어있음을 표시한다. 각 색종이의 위치가 주어진다. 모든 색종이의 크기는 10X10으로 동일하므로, 색종이가 붙는 100개의 그리드를 순회하면서 해당 그리드에 색종이가 붙었음을 기록해둔다. 3. 모든 그리드를 탐색하면서 색종이가 붙은 그리드의 개수를 센다. 모든 색종이를 붙였으면 이제 .. 공감수 0 댓글수 0 2023. 9. 4.
백준 3584번 가장 가까운 공통 조상 - C++ 풀이 1. O(N)의 LCA 알고리즘을 사용하여 구한다. 1. O(N)의 LCA 알고리즘을 사용하여 구한다. 단순한 LCA(Lowest Common Ancestor) 구하기 문제이다. N = 10,000 밖에 되지 않기 때문에 희소 테이블을 사용하지 않는 O(N)의 LCA로도 충분하다. #include #include #include using namespace std; const int MAX = 10'001; int N; int depth[MAX], parent[MAX]; vector children[MAX]; void dfs(int curr) { for (auto child: children[curr]) { depth[child] = depth[curr] + 1; dfs(child); } } int NC.. 공감수 0 댓글수 0 2023. 8. 21.
백준 2224번 명제 증명 - C++ 풀이 1. 전건과 후건을 각각 그래프의 노드로 생각하고, 전건에서 후건으로 가는 간선을 추가한다. 2. 만약 정점 P에서 정점 Q로 가는 경로가 존재한다면 P => Q를 증명할 수 있다. 3. 플로이드와샬을 사용하여 모든 순서쌍 (p, q)에 대해 p에서 q로 가는 경로가 있는지 확인한다. 1. 전건과 후건을 각각 그래프의 노드로 생각하고, 전건에서 후건으로 가는 간선을 추가한다. 주어지는 명제들의 전건과 후건을 각각 그래프의 노드라고 생각하자. 그리고 전건과 후건을 방향 간선(전건->후건)으로 잇는다. 2. 만약 정점 P에서 정점 Q로 가는 경로가 존재한다면 P => Q를 증명할 수 있다. 완성된 그래프에서 만약 정점 P에서 정점 Q로 가는 경로가 존재한다면, P => Q를 증명할 수 있다는 의미이다. 3... 공감수 0 댓글수 0 2023. 8. 21.
백준 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은 주어진 동전들.. 공감수 0 댓글수 0 2023. 8. 12.
백준 4179번 불! - C++ 풀이 1. 각 칸에 불이 번지는 시각을 BFS로 시뮬레이션하여 구해둔다. 2. 지훈이의 이동을 BFS로 시뮬레이션한다. 1. 각 칸에 불이 번지는 시각을 BFS로 시뮬레이션하여 구해둔다. 불이 매 초마다 상하좌우로 한 칸씩 퍼져나가므로, BFS를 이용하여 시뮬레이션 할 수 있다. 각 칸에 불이 번지는 시각을 구해두자. 이는 최초 불로부터의 거리와 같다. 2. 지훈이의 이동을 BFS로 시뮬레이션한다. 지훈이 또한 매 초마다 상하좌우로 이동할 수 있으므로, BFS를 이용하여 시뮬레이션 할 수 있다. 지훈이가 각 칸에 도착하는 시각 또한 최초 위치에서의 거리와 같다. 따라서 이제 지훈이가 특정 칸에 도착하는 시각과 그 칸에 불이 번지는 시각을 비교하면, 불이 번지기 전에 특정 칸에 도착했는지를 알 수 있다. 불이 .. 공감수 0 댓글수 0 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인 경우 그 자리에서 .. 공감수 0 댓글수 0 2023. 8. 9.
백준 1406번 에디터 - C++ 풀이 1. 모든 쿼리는 커서를 기준으로 이루어진다. 2. 커서보다 왼쪽에 있는 문자들과 오른쪽에 있는 문자들을 각각 스택으로 관리한다. 1. 모든 쿼리는 커서를 기준으로 이루어진다. 포인트는 모든 쿼리가 커서를 기준으로 이루어진다는 것이다. 2. 커서보다 왼쪽에 있는 문자들과 오른쪽에 있는 문자들을 각각 스택으로 관리한다. 따라서 커서 직전, 직후 문자들만 쿼리 대상이다. 이에 적합한 자료구조인 스택을 사용한다. 커서보다 왼쪽에 있는 문자들을 한 스택에 모아두고, 커서보다 오른쪽에 있는 문자들을 또 다른 스택으로 묶어 관리한다. 접근 가능한 top이 커서 쪽이 되는 순서로 저장해야 한다. 그러면 이제 모든 쿼리를 간단하게 구현할 수 있다. 왼쪽, 오른쪽 문자들이 담긴 스택을 각각 lst, rst라 하자. L:.. 공감수 0 댓글수 0 2023. 8. 9.
백준 3079번 입국심사 - C++ 풀이 1. t초동안 심사할 수 있는 사람 수의 최댓값은 ∑(t / Tk)이다. 2. 파라매트릭 서치를 사용하여 M명을 모두 처리할 수 있는 최소 시간을 구한다. 1. t초동안 심사할 수 있는 사람 수의 최댓값은 ∑(t / Tk)이다. t초동안 심사할 수 있는 사람 수를 최대로 하려면, 각 심사대가 쉬지 않고 일을 해야 한다. 따라서 각 심사대가 t / Tk명을 처리할 수 있고 이를 모두 더하면 t초 동안 심사할 수 있는 사람의 수의 최댓값을 구할 수 있다. 시간복잡도는 O(N). 2. 파라매트릭 서치를 사용하여 M명을 모두 처리할 수 있는 최소 시간을 구한다. M명을 모두 처리할 수 있는 최소 시간을 min_t라고 하면, t >= min_t인 경우 항상 모든 사람 심사가 가능하고 t < min_t인 경우 항상.. 공감수 0 댓글수 0 2023. 8. 5.
백준 15665번 N과 M (11) - C++ 풀이 1. 숫자를 하나씩 총 M개 뽑는다. 2. 숫자를 뽑을 때는 작은 숫자부터 뽑아본다. 3. 후보 숫자 목록에 중복이 없도록 후보 숫자들을 배열이 아닌 set으로 관리한다. 1. 숫자를 하나씩 총 M개 뽑는다. N개의 후보 숫자 중에서 총 M개 뽑으면 수열이 완성된다. M개를 다 뽑았으면 완성된 수열을 출력해주는 것을 반복한다. 2. 숫자를 뽑을 때는 작은 숫자부터 뽑아본다. 수열을 사전 순으로 증가하는 순서로 완성해야 한다. 따라서 뽑을 때 더 작은 숫자를 먼저 뽑아야 한다. (0으로 시작하는 수열을 1로 시작하는 수열보다 먼저 출력해야 하므로 0부터 뽑아보는 것이다.) 3. 후보 숫자 목록에 중복이 없도록 후보 숫자들을 배열이 아닌 set으로 관리한다. 그런데 중복되는 수열을 출력하면 안된다. 중복되는.. 공감수 0 댓글수 0 2023. 8. 3.
백준 2529번 부등호 - C++ 풀이 1. 부등호 조건에 맞게 중복 없이 숫자를 하나씩 뽑는다. 2. k+1개를 다 뽑았으면 최대, 최소 정수를 업데이트한다. 1. 부등호 조건에 맞게 중복 없이 숫자를 하나씩 뽑는다. 백트래킹으로 풀 수 있다. 부등호 조건에 맞으면서 중복 사용이 없도록 숫자를 하나씩 뽑아나간다. 2. k+1개를 다 뽑았으면 최대, 최소 정수를 업데이트한다. 부등호가 k개이므로 총 k+1개의 숫자를 뽑아야 한다. 다 뽑았으면 완성된 정수를 구하여 최대, 최소 정수를 업데이트한다. 이때는 문자열을 활용하면 편하다. #include using namespace std; int k; char signs[10]; int pick[10]; bool is_used[10]; string max_ans = "0000000000", min_.. 공감수 0 댓글수 0 2023. 8. 3.
백준 14719번 빗물 - C++ 풀이 1. 각 열마다 고이는 빗물의 양을 구해 합친다. 2. i열에 고이는 빗물의 양은 [:i-1]에서 가장 높은 블록과 [i+1:]에서 가장 높은 블록이 결정한다. 3. 그 중 더 낮은 블록 높이까지 빗물이 고이게 된다. 1. 각 열마다 고이는 빗물의 양을 구해 합친다. 각 열마다 고이는 빗물의 양을 구한 뒤 합치는 방식으로 전체 고이는 빗물의 양을 구해준다. 이때 양 끝 열(제일 왼쪽과 오른쪽)에는 절대 빗물이 고일 수 없다. 2. i열에 고이는 빗물의 양은 [:i-1]에서 가장 높은 블록과 [i+1:]에서 가장 높은 블록이 결정한다. 빗물이 고이기 위해서는 그릇의 형태가 되어야 한다. 즉, 양쪽이 i열보다 더 높은 블록으로 막혀있어야 한다. (양 끝 열에는 절대 빗물이 고일 수 없는 이유이다.) 또한 그.. 공감수 0 댓글수 0 2023. 7. 24.
백준 4097번 수익 - C++ 풀이 1. dp[i] = i일로 끝나는 구간 중 최고수익 구간의 수익 2. dp[i] = i-1일로 끝나는 최고수익 구간에 i일을 추가하거나 i일로 구간을 새로 시작하는 경우 중 최댓값 1. dp[i] = i일로 끝나는 구간 중 최고수익 구간의 수익 dp[i]를 위와 같이 정의하자. 예를 들어, dp[3]은 1-3일인 구간, 2-3일인 구간, 3-3일인 구간 중 최고 수익인 구간의 수익이다. 2. dp[i] = i-1일로 끝나는 최고수익 구간에 i일을 추가하거나 i일로 구간을 새로 시작하는 경우 중 최댓값 구간은 연속된 일자로 이루어져 있다는 성질을 이용한다. i일로 끝나는 구간은 1. i-1로 끝나는 구간에 i일을 추가하거나, 2. i일로 시작하면서 끝나는 구간(i일로만 이루어진) 둘 중 하나이다. 이 두 .. 공감수 0 댓글수 0 2023. 7. 17.
백준 20303번 할로윈의 양아치 - C++ 풀이 1. 각 연결요소에 속하는 노드의 개수와 사탕의 총합을 구해준다. 2. 각 연결요소를 물건으로 생각한다. (노드 개수 = 무게, 사탕의 총합 = 가치) 3. 배낭의 최대 용량이 K-1인 냅색 문제로 바꾸어 푼다. 1. 각 연결요소에 속하는 노드의 개수와 사탕의 총합을 구해준다. 친구끼리는 모두 한꺼번에 사탕을 빼앗기게 되므로 개인이 아니라 친구집합 단위로만 의미가 있다. 각 아이를 노드, 친구관계를 간선으로 생각하면 친구집합은 그래프의 각 연결요소가 된다. 이제 DFS/BFS 혹은 유니온파인드를 사용하여 모든 연결요소를 구해주자. 이때 각 연결요소에 속하는 노드(아이)의 개수와 각 노드에 걸린 사탕의 총합도 구한다. 2. 각 연결요소를 물건으로 생각한다. (노드 개수 = 무게, 사탕의 총합 = 가치) 이.. 공감수 0 댓글수 0 2023. 7. 14.
백준 27172번 수 나누기 게임 - C++ 풀이 1. 약수&배수 관계인 수들의 결투만 의미가 있다. 2. 어떤 수 x의 모든 약수는 1 ~ sqrt(x)까지 순회하여 찾을 수 있다. 3. 각 xi에 대해 xi의 모든 약수들과 결투한다. 1. 약수&배수 관계인 수들의 결투만 의미가 있다. 두 수가 서로 약수와 배수 관계인 경우에만 점수에 변화가 생긴다. 따라서 주어진 수들의 약수&배수 관계에만 집중하자. 2. 어떤 수 x의 모든 약수는 1 ~ sqrt(x)까지 순회하여 찾을 수 있다. 어떤 수 x의 모든 약수는 1부터 sqrt(x)까지로 모두 나누어떨어지는지 확인하는 방식으로 구할 수 있다. 만약 x가 i로 나누어 떨어진다면, i와 x/i는 x의 약수이다. 이때 i = x/i인 경우는 주의하여 처리하여야 한다. 2. 각 xi에 대해 xi의 모든 약수들과.. 공감수 0 댓글수 0 2023. 7. 9.
백준 21736번 헌내기는 친구가 필요해 - C++ 풀이 1. 현재 상황을 그래프로 나타낸다. 2. 도연이의 시작위치에서 시작하는 BFS/DFS를 수행한다. 3. 방문한 노드가 'P'인 경우 카운트한다. 1. 현재 상황을 그래프로 나타낸다. 주어진 상황은 그래프로 변환할 수 있다. 벽이 아닌 칸을 노드로 생각하고, 상하좌우로 인접한 칸들을 간선으로 잇는다. 2. 도연이의 시작위치에서 시작하는 BFS/DFS를 수행한다. 도연이와 A라는 노드가 연결되어 있다면, 도연이는 A를 만날 수 있다는 뜻이다. 도연이와 연결된 노드를 모두 찾기 위해 'I' 노드에서 시작하는 BFS/DFS로 그래프를 탐색하자. 3. 방문한 노드가 'P'인 경우 카운트한다. 각 노드를 방문하면서 해당 노드가 'P', 즉 사람인 경우 도연이가 해당 사람을 만날 수 있음을 의미하므로 카운트 + 1.. 공감수 0 댓글수 0 2023. 7. 9.
백준 20529번 가장 가까운 세 사람의 심리적 거리 - C++ 풀이 1. 33명의 사람을 16개의 mbti로 분류하는 경우, 최소한 한 mbti에는 반드시 3명이상 속하게 된다. 2. 32명 초과인 경우 심리적 거리의 최솟값은 0이다. 3. 32명 이하인 경우 심리적 거리의 최솟값은 브루트포스로 구할 수 있다. 1. 33명의 사람을 16개의 mbti로 분류하는 경우, 최소한 한 mbti에는 반드시 3명이상 속하게 된다. 비둘기집의 원리란 "n+1 마리의 비둘기가 n개의 비둘기 집에 나누어들어간다면, 적어도 한 집에는 반드시 두 마리 이상의 비둘기가 들어가게 된다"는 원리이다. 이것을 현재 문제에도 적용할 수 있다. 사람 = 비둘기, mbti 종류 = 비둘기집으로 생각하면 된다. mbti가 16종류가 있으므로, 만약 사람이 16+1=17명 있다면, 적어도 한 mbti에는 .. 공감수 0 댓글수 0 2023. 7. 6.
백준 14940번 쉬운 최단 거리 - C++ 풀이 1. BFS를 사용하여 두 지점 사이의 거리를 구할 수 있다. 2. BFS의 출발 노드를 목표지점으로 설정하여 모든 칸까지의 거리를 한번에 계산한다. 1. BFS를 사용하여 두 지점 사이의 거리를 구할 수 있다. 각 칸을 노드로 생각하고 갈 수 있는 땅끼리는 연결하여 그래프를 만든다. 이제 BFS를 사용하면 두 지점 사이의 거리를 구할 수 있다. 2. BFS를 사용하여 목표지점에서 모든 칸까지의 거리를 한번에 계산한다. 각 칸에서 출발하여 목표지점까지 도달하는 BFS를 수행한다면, 총 n^2개의 칸에 대해 O(n^2)의 시간복잡도가 소요되므로 총 시간복잡도는 O(n^4)가 되어 시간초과를 받을 수 있다. 거꾸로 목표지점에서 출발하여 모든 칸을 방문하는 BFS를 진행하면 한번에 계산이 가능하다. 각 노드를.. 공감수 0 댓글수 0 2023. 7. 6.
백준 10800번 컬러볼 - C++ 풀이 1. 공들을 크기 오름차순으로 정렬한다. 2. i번째 공이 사로잡을 수 있는 공들의 크기합 = (i번째 공보다 작은 공들의 크기합) - (i번째 공보다 작고 색이 같은 공들의 크기합) 1. 공들을 크기 오름차순으로 정렬한다. 먼저 공들을 크기 기준으로 오름차순 정렬해준다. 2. i번째 공이 사로잡을 수 있는 공들의 크기합 = (i번째 공보다 작은 공들의 크기합) - (i번째 공보다 작고 색이 같은 공들의 크기합) i번째 공보다 크기가 작고 색이 달라야 하므로, (i번째 공보다 작은 공들) - (i번째 공보다 작고 색이 같은 공들)을 구하면 된다. 포인터를 하나 두고, 포인터가 가리키는 공의 크기가 현재 공의 크기와 같아지기 전까지 포인터를 오른쪽으로 이동시키면서 1. 전체 크기 합과 2. 색깔별 크기 합.. 공감수 3 댓글수 0 2022. 10. 5.
백준 16954번 움직이는 미로 탈출 - C++ 풀이 1. 상태 노드를 나타내기 위해 필요한 값은 {시간, 행, 열} 값이다. 2. BFS를 사용하여 {0, 7, 0}에서 {t, 0, 7}에 도착할 수 있는지 확인한다. 1. 상태 노드를 나타내기 위해 필요한 값은 {시간, 행, 열} 값이다. 시간이 지남에 따라 미로가 바뀌고 있으므로, 상태 노드를 나타내기 위해 필요한 값은 행, 열, 그리고 시간 값이다. 2. BFS를 사용하여 {0, 7, 0}에서 {t, 0, 7}에 도착할 수 있는지 확인한다. BFS를 사용하여 시작 노드 {0, 7, 0}에서 {t, 0, 7}에 도착할 수 있는지 확인한다. 언제 도착했는지는 상관이 없기 때문에 r=0, c=7인 노드인지만 확인하면 된다. #include #include using namespace std; typedef.. 공감수 1 댓글수 0 2022. 9. 30.
백준 13305번 주유소 - C++ 풀이 1. i-1번 도시에서 i번 도시로 이동하기 위한 기름을, 1~(i-1)번 도시 중 가장 싼 곳에서 넣고 온다. 1. i-1번 도시에서 i번 도시로 이동하기 위한 기름을, 1~(i-1)번 도시 중 가장 싼 곳에서 넣고 온다. 기름통의 크기가 무제한이므로, 그리디하게 각 도시에 도착하기 전에 가장 싼 주유소에서 기름을 넣고 오면 최적이다. 일반화하면, i-1번 도시에서 i번 도시로 이동하기 위한 기름을, 1~(i-1)번 도시 중 가장 싼 주유소에서 넣고 오면 된다. 이때 i-1번 도시에서 i번 도시까지의 거리를 dist[i], 1~(i-1)번 도시 중 가장 싼 주유소의 가격을 min_price[i]라고 하면 비용은 dist[i] * min_price[i]이다. #include using namespace .. 공감수 0 댓글수 0 2022. 9. 27.
백준 2616번 소형기관차 - C++ 풀이 1. sum[i] = arr[i...i+K-1]의 구간합 2. dp(idx, n): [idx번 객차~마지막 객차]가 있을 때 n개의 소형 기관차로 끌 수 있는 최대 손님의 수 3. dp(idx, n) = max(dp(idx+1, n), sum[idx] + dp(idx+K, n-1)) 1. sum[i] = arr[i...i+K-1]의 구간합 먼저 모든 길이 K인 구간의 구간합을 구해둔다. 누적합을 사용하여 O(N)에 구할 수 있다. sum[i] = sum[i-1] - arr[i-1] + arr[i+K-1] 2. dp(idx, n): [idx번 객차~마지막 객차]가 있을 때 n개의 소형 기관차로 끌 수 있는 최대 손님의 수 dp(idx, n)을 위와 같이 정의한다. 총 구해야 하는 상태 값은 50,000 *.. 공감수 5 댓글수 0 2022. 9. 26.
백준 1726번 로봇 - C++ 풀이 1. 로봇의 상태를 나타내기 위해서는 {행, 열, 방향} 세 가지 값이 필요하다. 2. 출발 상태 노드에서 도착 상태 노드까지 가는 최단 거리를 BFS를 사용하여 구한다. 1. 로봇의 상태를 나타내기 위해서는 {행, 열, 방향} 세 가지 값이 필요하다. 로봇의 상태를 나타내기 위해서는 {행, 열, 방향} 이 세 가지 값이 필요하다. 이것을 세 정보를 가지고 상태 노드를 구성할 수 있다. 2. 출발 상태 노드에서 도착 상태 노드까지 가는 최단 거리를 BFS를 사용하여 구한다. go k, turn left/right 연산을 통해 도달할 수 있는 상태 노드를 간선으로 이어 인접 노드로 만든다. 완성된 그래프에서 출발 상태에서 도착 상태로 가는 최단 거리를 구해준다. 모든 간선의 가중치가 1이므로 BFS를 사용.. 공감수 0 댓글수 0 2022. 9. 23.
백준 1309번 동물원 - C++ 풀이 1. dp(idx, prev) : (idx-1) 번째 행의 상태가 prev일 때 idx번 행~마지막까지 채우는 방법의 수 2. prev = 0 이면, dp(idx, prev) = dp(idx+1, 0) + dp(idx+1, 1) + dp(idx+1, 2) 3. prev > 0 이면, dp(idx, prev) = dp(idx+1, 0) + dp(idx+1, 3-prev) 1. dp(idx, prev) : (idx-1)번째 행의 상태가 prev일 때 idx번 행~마지막까지 채우는 방법의 수 dp(idx, prev)를 위와 같이 정의하자. 사자가 세로로 붙어있을 수 없으므로 prev값이 필요하다. 이때 사자가 가로로 붙어있을 수 없으므로 한 행 내의 사자 상태는 아예 없거나, 오른쪽 칸에만 있거나, 왼쪽 칸에.. 공감수 0 댓글수 0 2022. 9. 22.
백준 2931번 가스관 - C++ 풀이 1. 모든 배관에 대해, 끊긴 길의 방향을 모두 찾는다. 2. 끊긴 모든 방향을 다시 이을 수 있는 배관의 위치와 종류를 찾는다. 1. 모든 배관에 대해, 끊긴 길의 방향을 모두 찾는다. 모든 배관에 대해, 끊긴 길의 방향을 모두 찾아둔다. 아래와 같은 상황에서 (2,2)의 | 모양 배관을 보면, 아래 방향으로는 길이 끊겨있다. 이는 곧 (3,2)에서 윗방향으로 잇는 배관이 필요하다는 뜻이므로 기록해둔다. 마찬가지로 (4,2)의 | 모양 배관을 보면, 윗방향으로 길이 끊겨있다. (3,2)에서 아랫방향으로 잇는 배관이 필요하다는 뜻이다. 2. 끊긴 모든 방향을 다시 이을 수 있는 배관의 위치와 종류를 찾는다. 딱 한 개의 배관만 제거했다고 했으므로, 배관이 필요한 칸은 한 개뿐이다. 해당 칸에 필요한 방향.. 공감수 1 댓글수 0 2022. 9. 22.
백준 6588번 골드바흐의 추측 - C++ 풀이 1. n 이하의 모든 소수 i에 대해 (n-i)가 소수인지 판별한다. 1. n 이하의 모든 소수 i에 대해 (n-i)가 소수인지 판별한다. 에라토스테네스의 체를 이용하여 백만 이하의 모든 소수를 구한다. n이하의 모든 소수 i에 대해 n-i가 소수인지 판별하면 된다. 이때 i를 오름차순으로 순회하고, 답이 나올 경우 순회를 종료시키면 b-a가 가장 큰 답을 구할 수 있다. 백만 이하의 소수 개수는 약 8만 개이므로, 이 풀이의 시간 복잡도는 O(80,000*T)이다. 이때 T(테스트 케이스 수)가 10^5이므로 시간 초과가 날 것 같았는데 시간 초과가 나지 않았다. 이에 관련된 질문과 답을 아래 게시글에서 발견하였다. 글 읽기 - 이 문제 제한시간이 1초인데 왜 되나요? 댓글을 작성하려면 로그인해야 합니.. 공감수 0 댓글수 0 2022. 9. 20.
백준 2583번 영역 구하기 - C++ 풀이 1. 직사각형이 없는 칸을 그래프의 노드로 생각하고, 인접한 모든 노드를 간선으로 잇는다. 2. 완성된 그래프에서 각 연결 요소의 크기와 연결 요소의 개수를 센다. 1. 직사각형이 없는 칸을 그래프의 노드로 생각하고, 인접한 모든 노드를 간선으로 잇는다. 유의미한 칸은 직사각형이 없는 칸이다. 직사각형이 없는 칸을 그래프의 노드로 생각하고, 인접한 모든 노드를 간선으로 이어 그래프로 만들어준다. 2. 완성된 그래프에서 각 연결 요소의 크기와 연결 요소의 개수를 센다. 이제 각 영역은 연결 요소와 같다. DFS/BFS로 연결 요소의 개수를 세는 동시에 각 연결 요소의 크기도 구해준다. 연결 요소의 개수는 총 DFS/BFS의 호출 횟수이고, 각 연결 요소의 크기는 한 DFS/BFS에서 방문한 노드의 개수와 .. 공감수 0 댓글수 0 2022. 9. 19.
백준 17779번 게리맨더링 2 - C++ 풀이 1. 모든 (x, y, d1, d2) 쌍에 대해 선거구 나누기를 하여 최적화한다. 1. 모든 (x, y, d1, d2) 쌍에 대해 선거구 나누기를 하여 최적화한다. 가능한 모든 (x, y, d1, d2) 쌍은 N^4개, 선거구 나누기 시뮬레이션에 O(N^2)의 시간 복잡도가 소요되므로, 전체 시간 복잡도는 O(N^6). 이때 N=20이므로 브루트 포스로 해결할 수 있다. 선거구 나누기 시뮬레이션은 주어진 조건을 잘 구현하면 되고, 경계선으로 둘러싸인 5번 선거구는 DFS로 처리해주었다. #include #include #include using namespace std; const int INF = 987654321; int N; int A[20][20]; int board[20][20]; bool va.. 공감수 0 댓글수 0 2022. 9. 18.
백준 2170번 선 긋기 - C++ 풀이 1. 선분들을 시작점 오름차순으로 정렬한다. 2. 스위핑하면서 모든 선분의 길이를 더한다. 1. 선분들을 시작점 오름차순으로 정렬한다. 스위핑을 통해 해결할 수 있는 문제이다. 왼쪽부터 스위핑하면서 선분의 총 길이를 계산해줄 것이다. 이 작업을 위해 먼저 주어진 선분들을 시작점 오름차순으로 정렬한다. 2. 스위핑하면서 모든 선분의 길이를 더한다. 이제 왼쪽부터 스위핑하면서 모든 선분의 길이를 더한다. 중간에 겹치는 선분들을 하나의 선분으로 만들어주면서 이동해주면 된다. 현재 처리중인 선분의 시작점과 끝점 좌표를 각각 s, e, 다음 선분의 시작점과 끝점 과표를 각각 ns, ne라고 하자. 시작점 오름차순으로 정렬해주었기 때문에 s ≤ ns임은 보장되어 있다. 따라서 ns < e 이면, 현재 선분과 다음 .. 공감수 0 댓글수 0 2022. 9. 15.
백준 2023번 신기한 소수 - C++ 풀이 1. 길이 n짜리 신기한 소수의 집합을 P(n)이라고 하면 P(n) = (P(n-1)*10 + i) 중 소수인 것의 집합 (단, i는 0 ≤ i ≤ 9) 1. 길이 n짜리 신기한 소수의 집합을 P(n)이라고 하면 P(n) = (P(n-1)*10 + i) 중 소수인 것의 집합 (단, i는 0 ≤ i ≤ 9) 길이 n짜리 신기한 소수 x가 있다고 하자. 그럼 x[0...(n-2)] 또한 신기한 소수이다. 따라서 재귀를 이용하여 구할 수 있다. 길이 n짜리 신기한 소수의 집합을 P(n)이라고 하면, P(n) = P(n-1)*10+i 중에서 소수인 것의 집합이 된다. 기저 사례는 n=1인 경우이고, 10 미만의 소수 {2, 3, 5, 7}을 리턴해주면 된다. #include #include using names.. 공감수 0 댓글수 0 2022. 9. 14.

반응형

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.