백준 문제 해설66 12880 그래프 차이 최소 (C++) 보다시피.. 계속해 놓치던 반례가 있어 많은 WA를 받게 되었다. 문제 접근 과정 처음 읽었을 때 고등학교 기숙사에서 지내는데 12시 이후 소등이 되고 나서 갑자기 아무 문제나 하나 읽고 잠들기 전까지 고민하고 싶어 겨우겨우 와이파이 신호를 잡고 문제를 로딩하고 읽어 고민을 시작하게 되었다. 임의의 간선 집합을 알고 있을 때 해당 간선 집합으로 모든 정점 중 A와 B를 아무거나 선택하고 A -> B, B -> A 두 가지 경로가 모두 존재하는지 판별하는 방법도 잘 모르고 있었다. N = 50 밖에 안되었지만 전체적인 문제에 대한 접근 방법이 도저히 감이 잡히지 않아 문제에 대한 가벼운 고민을 2시간 정도 한 이후 해답을 참고하게 되었다. Justice Hui님의 tistory를 참고하게 되었다. 간선들을.. 2022. 9. 30. 2473 세 용액 (C++) 세 용액 중 두 가지 용액만 특정해주면 나머지 한 가지는 logn만에 알아서 선택된다는 사실을 이용하였다. 문제 접근 과정 처음 읽었을 때(언제였는지 잘 기억 안 남) : 알 것 같은데 어떻게 푸는지 모르겠다. 갑자기 떠오른 풀이 : n^2이 가능하니 두 개를 정해주고 하나는 알아서 정해지게 하자(n = 5000) 구현 10분정도 걸림 이분 탐색 잘못 적어줘서 두 번 WA 코드 한번 쭉 다시 읽으며 오류 잡음 수정 후 기쁨의 AC 시간 복잡도 : O(n*n*log(n)) 소요 시간 : 측정 불가 아쉬운 점 이분 탐색을 짤 때 해당 조건문에서 m을 커지게 해야 할지 작아지게 해야 할지 일단 적고 틀리면 바꾸는 경향이 있다. 고치게 되면 좋겠다. 전체적인 감상 지난 주 쯤 이 문제를 읽고 넘어간 적이 있는데.. 2022. 9. 29. 16724 피리 부는 사나이 (C++) Floyd's Tortoise and Hare Algorithm을 사용하여 문제를 해결하였다. 문제 접근 과정 1분 문제의 이차원 배열이 Functional Graph의 형태를 띤다는 사실을 알게 되었다. 사이클 판별 알고리즘을 활용하여 발생하는 사이클의 개수를 세어주면 된다는 것을 알았다. 6분 이차원 배열에서 직접 하려던 사이클 판별을 하기 위해 rev 배열을 구현하는데 어려움을 겪었다. 7분 이차원 배열의 노드에 새 id를 각각 부여해서 일반적인 형태의 그래프로 치환하였다. 14분 코드 첫 실행 while문에서 문제가 생긴다는 것을 return 0;을 써보며 알게 되었다. 15분 수정 후 첫 제출 기쁨의 AC 소요 시간 : 15분 아쉬운 점 : 노드에 새 id를 부여하는 것을 처음부터 했으면 더 빨.. 2022. 9. 28. 3973 Time To Live (c++) 다른 문제들을 풀다 막힘이 생기면 쉽게 쉽게 알고리즘 분류를 켜고 정답 코드를 찾아봤던 것과는 다르게 이 문제는 처음부터 끝까지 혼자 고민하며 온전히 나 스스로 해결하게 될 것이다. 문제 링크 : https://www.acmicpc.net/problem/3973 -- 문제 풀기 전에 했던 고민 -- 실수 1 문제를 잘못 이해해 트리의 전체 TTL값을 최소로 하기 위한 방법을 고민하였다 관찰 1 최대 TTL값은 항상 Leaf node에서 발생한다 - Leaf node마다 bfs를 돌려서 마지막에 만나는 곳을 라우터로 하여 정답을 찾는다 (?) -- 첫 다짐을 깨버리게 되었다. 정답 풀이 어느 한 지점에서나 bfs를 돌리면 마지막에 방문하게 되는 노드(이 노드는 무조건 leaf일 수 밖에 없음)는 길게 늘어.. 2022. 8. 7. 백준 13913 메모리초과(c++) 부모배열을 통해 탐색 여부를 판단했다(parent[n] != 0) 하하... 하지만 parent[n]은 0으로 지정될 수도 있다는 것을.... 기억하자 2022. 8. 5. 이전 1 ··· 10 11 12 13 14 다음
