반응형 [백준]214 [BaekJoon/백준] 9095번 C++ 규칙이 없어서는 안될 문제라고 생각했는데, 규칙이 보이지가 않았다. 실버3에.. 정답률이 60인데 규칙이 없을리가 없다고 생각했다. 동적계획법으로 푸는 문제라고 확신했는데, 막상 규칙이 보이지 않았다. 이 문제가 이렇게 어렵게 푸는게 아닌 것 같은데.. 라고 생각하며 dfs 방식으로 풀어봤다. #include using namespace std; int N, T; int ct; void recur(int x) { if(x == 0) { ct++; return; } else if(x T; while(T--) { ct = 0; cin >> N; recur(N); cout 2021. 4. 6. [BaekJoon/백준] 7662번 C++ 처음에는 우선순위 큐(priority_queue) 두개를 사용해서 문제를 풀어보려 시도했다. 근데 단순히 두 개만 이용할 것도 아니고, 이미 삭제된 노드에 대해서도 서로 체크해줘야 하는 어려움이 있었다. 나는 결국 우선순위 큐 두개를 사용해서 풀진 못했지만 그런 방법도 있다! velog.io/@leehj8896/백준-7662번-이중-우선순위-큐 검색을 하다가, STL 에 있는 multiset 자료구조를 알게 되었다. 이 자료구조는 이름에 맞게, 중복도 허용해주지만 알아서 정렬을 시켜준다는 점이 크게 매력적이였다. 이 자료구조를 이용하면 이 문제를 엄청나게 간단하게 풀 수 있었다. #include #include using namespace std; int T, N, input; int main() { i.. 2021. 4. 5. [BaekJoon/백준] 7576번 C++ 1697번, 2606번 같은 BFS 유형의 문제였다. BFS 코드의 방향이 다 비슷비슷하다. 처음 queue에 push 하고, visit 처리. 그리고 while문 돌면서 팝 하면서 이 때도 push하고 visit 처리... 반복 다만 이전 문제들과 다르게 시작 노드가 두개이상 일 수 있어서, 큐를 두개 구현해야하나.. 이런저런 생각을 했지만 옳지 않은 방향으로 갈 뿐이였다 ㅜㅜ.. 풀이를 검색했고, 어떤 분의 풀이를 보고 느낌이 왔다.. 생각해보니 시작 노드가 두개라고 해서 큐를 두개 구현할 필요가 없었다. 예를 들면, 1을 큐에 넣고 pop을 한 뒤 child node 2, 3을 넣었을 때와 처음부터 2 3이 각각 시작노드라고 생각해도 구현이 똑같기 때문이였다. 이런식으로 문제를 풀게 되었다! // .. 2021. 4. 2. [BaekJoon/백준] 2606번 C++ BFS로 해결할 수 있는 문제였다. BFS의 기본유형을 아주 잘 나타낸 문제였던 것 같다!! BFS 문제는 이 문제가 두 번째였는데, 느낌은 오는데 구현이 힘들었다. 아직 BFS에 대해 많이 익히지 못했으니까!! 앞으로 점점 익혀나갈 것이다. 어렵더라도 꼭 머릿속으로 그려가며 풀어보셨으면 좋겠다. 특히 블로그 두 군데를 추천해드릴테니, 설명을 보고 그림을 따라가면서 문제를 한번 꼭 직접 구현해봤으면 좋겠다. 참고 : 1. gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html 2. m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221230944971&proxyReferer=https:%2F%2Fwww.google.com%2F .. 2021. 4. 1. 이전 1 ··· 20 21 22 23 24 25 26 ··· 54 다음 반응형
