짱아의 개발 기록장

이 문제는 처음에 딱 읽었을 때 bfs로 풀면 간단하겠다라고 생각했지만, 통신탑과 간선의 개수가 각각 최대 100,000 인것을 보고 bfs로 풀다가는 백퍼 시간초과가 나겠구나 싶었다. 그리고 다른 방법을 고민하다가 도저히 아이디어가 생각나지 않아, 문제 유형을 검색해보니 바로 "유니온파인드"를 이용하는 문제였다. 끊을 간선을 제외한 모든 간선을 먼저 연결해주고 끊을 간선들을 역순으로 하나씩 연결해주며 값을 계산해나가면 된다. 예를 들어, a->b a를 b와 연결해준다면 a의 부모 노드를 찾고 b의 부모노드를 찾아서 연결해주고 b의 부모노드의 값에 a의 부모노드의 값을 더해주면 된다. (cost[b] += cost[a] 이런식으로 구현했다.) 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 1..

투포인터를 활용해 푸는 문제이다. 2020카카오인턴 기출 문제 3번인 보석쇼핑과 매우 유사한 문제이다. 유사 문제 https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 위 문제에 대한 코드도 블로그에 정리해 두었다. https://jungahshin.tistory.com/10?category=830724 2020 카카오 인턴 코딩 테스트 - 3번. 보석쇼핑(c++) 이 문제는 투포인터를 이용하면 쉽게 풀 수 있는 문제이다. 문제에서 gems 배열의 크기가 100,..