반응형 +A14 [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. [BaekJoon/백준] 1927번 C++ 최대 힙, 최소힙 이러한 용어가 쓰이는 힙정렬 알고리즘에 대한 문제였다. 힙 부모의 값이 자식의 값보다 항상 크다 / 또는 작다. => 최대힙/최소힙 힙에서 부모와 자식 관계는 일정하지만, 형제 사이의 대소관계는 일정하지 않다. C언어로 힙정렬을 구현했을 때의 코드를 살펴봤는데 진짜 기억이 하나도 안나고...이해도 안되고... 하 ... 쉬고싶다... 어느정도 감은 잡았는데, 문제를 구현하는데 있어서 끙끙대다가.. 풀이를 찾아봤다. 찾아보니 최소힙 / 최대힙 구현을 C++의 STL인 priority_queue 를 사용하여 구현할 수 있다고 한다. 참고 : twpower.github.io/93-how-to-use-priority_queue-in-cpp 이를 이용해서 구현해봤다. #include #inclu.. 2021. 3. 31. [BaekJoon/백준] 1697번 C++ 처음에 동적할당으로 문제를 풀어보려 했으나, 어려웠다. 양방향에 대한 계산이 필요했기에 어려움을 많이 겪었고 알아보니 이러한 문제에서 DP 접근은 좋지 않다는 것을 알았다. ( 관련 참고 : www.acmicpc.net/board/view/41340 ) 풀이를 검색해보게 되었다. 이 문제는 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.googl.. 2021. 3. 28. [BaekJoon/백준] 11444번 분할정복 피보나치를 구하는 방법 중, 행렬의 제곱을 이용한 방법이 있다. 메모이제이션을 사용한 피보나치는 O(N)의 시간복잡도를 갖는 반면 10830번에서 볼 수 있었듯, 행렬의 제곱은 분할정복을 사용해 O(logN)으로 해결할 수 있다. 사실 10830번 코드를 거의 그대로 갖다가 썼다가, 계속 메모리 초과가 나와서 애를 먹었다.. 이유는.. 10830번에서는 제곱수가 1부터지만 11444번에는 제곱수가 0부터 가능해서 예외가 있었던 것 ㅜ #include #include long long arr[2][2]; long long original[2][2]; long long temp1[2][2]; int N = 2; long long B; int i, j, m; // 재귀 속에서 정적 변수인 arr을 공용으로 사.. 2021. 3. 19. 이전 1 2 3 4 다음 반응형
