Doby's Lab

이번 문제 풀이는 못 풀어서 다른 사람의 답을 참고했음에도 성취감을 느낄 수 있었다. 주석처리가 이번 문제의 성취감 포인트였던 거 같다. 기존의 문제 풀이 방식 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

[틀렸던 코드] #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector arr; vector answer; for (int i = 0; i > idx; if (idx == 0) { sort(arr.begin(), arr.end()); if (!arr.empty()) { answer.push_back(arr.back()); arr.pop_back(); } else { answer.push_back(0); } } else { arr.push_back(idx); } } for (in..

우선순위 큐란 큐의 한 종류로 말 그대로 우선순위대로 큐에 데이터를 집어넣는다. (여기서 말하는 우선순위란 값의 크기의 오름차순 혹은 내림차순 등 사용자가 정할 수 있다.) 일반적인 큐는 배열같은 선형적인 구조로 생각할 수 있다. 하지만, 우선순위 큐는 트리의 관점에서 접근해야 한다. 우선순위 큐는 배열 혹은 연결 리스트로도 구현이 가능하지만 이를 사용하지 않는 이유가 있다. 데이터를 삽입하거나 삭제하는 과정에서 배열이나 연결 리스트의 메모리를 밀고 당기는데에서 성능 저하를 일으키기 때문에 일반적으로 힙을 사용하여 구현하기 때문이다. (힙이 트리로 이루어졌기 때문) 그리고, 힙에서 데이터를 삽입하거나 삭제할 때는 시간 복잡도가 O(log N)이다. (+ 힙 정렬이 N개의 데이터를 하나씩 다 빼오기(삭제)..

주석 조건 참고 #include #include #include #include using namespace std; queue q; bool visited[100001] = { 0, }; void bfs(int n, int k) { q.push(make_pair(n, 0)); while (!q.empty()) { int value = q.front().first; int cnt = q.front().second; q.pop(); if (value == k) { cout > k; bfs(n, k); return 0; }

이 문제를 직관적으로 풀었을 때는 시간 초과가 발생한다. 구간이 예를 들어 1~100,000이고, 합을 구하는 횟수가 1~100,000이라면 어마한 양의 시간이 발생하기 때문에 다른 방법을 생각해내야 한다. DP (Dynamic Programming) 개념 DP란 큰 문제를 해결하기 위해 작은 문제들로 나누어 작은 문제들을 해결하여 큰 문제들 해결할 수 있도록 도와주는 알고리즘이다. 예를 들어 피보나치 수가 DP의 대표적인 문제라고 할 수 있다. 피보나치 4를 구한다고 생각해보자. 일반적으로 코드는 이렇게 짤 것이다. #include using namespace std; int fibo(int n) { if (n == 0) { return 0; } else if (n == 1) { return 1; } ..