Doby's Lab

이번 문제에서 크게 어려웠던 점은 없었으나 각 문제에 대한 포인트를 항상 블로그에 담아두려 하기 때문에 가져왔다. 문제에서 헷갈릴 수 있는 건 visited의 리셋이었다. 비의 높이에 따라 bfs를 해주며 건물의 개수를 cnt하며 배열에 따로 담았었다. 하지만, cnt를 담은 배열을 디버깅해보니 처음을 제외하고는 전부 0이었다. 이 부분에서 visited를 초기화시키지 않았구나라는 것을 알고 reset 함수를 작성하고, 비에 높이에 따라 건물 cnt가 끝날 때마다 reset 함수를 콜 해주었다. [코드] #include #include #include #include using namespace std; int map[101][101] = { 0, }; bool visited[101][101] = { 0..

이번 문제는 당연하게 나머지 정리(MOD의 연산)를 이용해 풀 수 있을 거라 생각했다. 왜냐하면 거듭제곱을 할수록 수는 기하급수적으로 엄청 커질 것이기 때문에 즉각적으로 이를 처리할 수 있는 나머지 정리를 사용하는 것이 필수적이라 생각했다. 하지만, 거듭제곱의 연산 또한 2,147,483,647 이하의 수가 주어지기 때문에 시간 초과를 발생시킬 것이라 확신했다. 어떠한 솔루션이 떠오르지 않았고, 이 문제는 '분할 정복을 이용한 거듭제곱' 이란 키워드로 분류되어있었기 때문에 분할 정복에 대해 알아보기로 했다. 이번 문제에서 사용된 나머지 정리 연산 규칙성 (A * B) mod N = (A mod N * B mod N) mod N 가정: 어떠한 값을 A라 두고, 나누는 수가 N이라고 했을 때 A mod N은..

이번 문제는 BFS로 풀려고 했다. [당시 썼던 BFS 코드] void bfs(int row, int col) { queue q; q.push(make_pair(row, col)); while (!q.empty()) { int y = q.front().first; int x = q.front().second; q.pop(); for (int i = 0; i = 1 && dy = 1 && dx > 앞 길에 'A'가 있는데 1, 1에서 출발한 길에선 아직 'A'가 나오지 않아서 가야 하지만 다른 길에서 이미 'A'가 나와서 가지 못하는 것으로 판단하는 것을 말한다. [DFS를 사용한 이유] ..

이번 문제는 이분 탐색이라는 전제가 없었다면 풀 수 없었을 것이다. 이분 탐색이라는 전제가 있어도 논리에 접근하기 까다로운 문제였다. 걸리는 시간을 여러 값으로 추정하며 이분 탐색으로 도달하는 문제다. 논리에 접근했던 방법 처음엔 최소 시간이 걸리는 검색대에 사람들이 몰리게 해야겠다는 생각이 들었다. >> 검색대의 시간들을 배열에 담아 정렬시켰다. 그래서 걸리는 시간(mid)이 주어지면 그 시간 안에 최소 시간 검색대에 몇 명의 사람이 올 수 있는지 카운트해주었다. >> sum을 선언하고 sum이 mid가 될 때까지 걸리는 시간을 더해준 후에 mid가 되면 다음 시간 검색대에서 같은 과정을 반복해주었다. for (int i = 0; i < times.size(); i++) { ll sum = 0; whi..

이번 문제 풀이는 못 풀어서 다른 사람의 답을 참고했음에도 성취감을 느낄 수 있었다. 주석처리가 이번 문제의 성취감 포인트였던 거 같다. 기존의 문제 풀이 방식 for문을 사용하여 1일 때, BFS를 사용하면 한 번에 모든 0인 노드를 다 순회하기 때문에 다른 접근법이 필요했다. 떠올랐던 방법이 for문을 사용하여 1일 때, BFS를 사용하지 않고, 큐에다가 그 노드를 push 한다. 그리고 난 뒤에 BFS를 실행시키면 답에 접근할 수 있었다. 하지만, 또 다른 문제가 발생한다. 현재까지의 접근법으로 작성한 코드는 이렇다. // 궁금증 1: 굳이 이번 문제에 visited가 필요했을까 // 궁금증 2: bfs의 if 조건문에서 map이 1인 경우는 따져도 되지 않을까 #include #include #i..

'점화식을 어떻게 세울 것인가'가 큰 관건이었다. '큰 문제를 작은 문제로 나누자'라는 키워드는 이제 금방 떠오르고, 나눌 수 있었지만 이들이 어떤 관계를 갖는지는 알 수가 없었다. R이면 G와 B 중에 하나를 골라야 하고, G이면 R과 B 중에 하나를 골라야 하는데 색을 고를 수 있는 경우가 3가지일 뿐인 더러 관계를 가질 수는 있긴 한 지가 의문이었다. 그래서 풀이를 보고, 다른 DP문제였던 2579번(계단 오르기)의 풀이를 보면서 느꼈지만 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 ..

아직도 DP의 문제를 푸는 데에 있어서 어려움을 겪는다. 그래도 전보다 나아진 것은 다음과 같다. 1. 작은 문제는 무엇이며 이 작은 문제들이 모여서 어떠한 큰 문제를 풀어야 하는지 탐색하려 한다. 2. 작은 문제들의 관계성에 중심을 두고 있다. 3. 어느 정도 코드의 구조를 알게 되었다. (감각의 관점) 그래서 이번 문제는 각 정수의 합을 나타낼 수가 몇 개가 있는지 적어보며 관계성을 파악하려 했다. 하지만, 규칙은 알 수가 있어도 어떠한 관계인가?라는 질문에는 정확한 대답을 내놓을 수 없었다. 풀이를 찾아보다가 다음의 풀이를 발견하게 되었다. https://blog.naver.com/PostView.nhn?blogId=vjhh0712v&logNo=221470862600 백준 알고리즘 9095번 문제풀..

DP의 접근 방법이 꽤 어려웠다. 아무래도 점화식을 어떻게 세우는지 접근을 하지 못 했다. (BFS로 풀릴 거 같아서 BFS로 푼 풀이는 맨 아래에 첨부해두었다.) 그래서 다른 사람의 코드를 참고했다. (Bottom-Up 방식) #include #include #include using namespace std; int cache[100001] = { 0, }; int main() { int n; cin >> n; for (int i = 2; i > n; bfs(n); sort(answer.begin(), answer.end()); cout