반응형 +A14 [BaekJoon/백준] 1167번 C++ 어려웠다. bfs로 풀어나가긴 했는데 그게 전부가 아니였다. 일단 bfs의 depth 개념을 이용하는 문제이긴 한데, depth 그 자체는 아니고, 간선마다 길이가 다르므로 그 값을 이용해줘야한다. 처음에는 모든 노드에서 bfs를 구하여 코드를 만들었다. 당연히 상식적인 선에서 이렇게 구현하면 문제가 풀렸다. 예제들도 다 들어맞길래 정답인 줄 알았는데.. 시간초과가 떴다. 문제는 모든 노드에서 bfs를 해줬던 것이였다. 알아보니, 트리의 지름을 구할 때엔 각각의 노드마다 bfs를 전부 시도할 필요는 없고 단 두번으로 해결된다고 한다. 왜 두번인지 더 알아봤는데도, 왜 두번인지 모르겠다. 설명에서는, 임의의 노드에서 가장 큰 가중치를 가진 노드를 찾은 뒤에 (간선의 길이를 포함하여 가장 멀리 떨어진 노드).. 2021. 5. 16. [BaekJoon/백준] 18870번 C++ 문제 이해하는데만 30분 쓴 것 같다. 어려웠다. 문제가 무슨 말인지 도저히 알 수가 없어서 검색을 통해 사람들의 설명을 보고 해결했다. 대충 설명에 대한 메모는 이렇다. 일단 좌표압축이라는 건 조금 생소한 애기였다. 좌표를 압축한다 : 해당 좌표의 값을 그 값보다 작은 좌표값들의 개수로 대체한다의 의미 예제에 2 4 -10 4 -9가 주어졌는데 리스트의 각 숫자가 자신보다 작은 값들의 갯수로 나타내보면 예제의 정답과 같다. 따라서 이를 표현하기 위해 1. 값들을 오름차순으로 정렬 2. 중복을 제거 (메모의 unique와 erase부분. unique는 리턴값으로 '중복처리로 뒤로 미룬 첫번째 위치'를 반환한다. ex 3의 위치) 3. 이 때 값들의 index값이 문제에서 요구하는 정답. 하지만 이미 입력.. 2021. 5. 15. [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. 이전 1 2 3 4 다음 반응형
