프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 유형에는 완전탐색이라고 되어 있기하던데 난 다른 방식으로 풀었다.n개의 송전탑이 하나의 트리 형태로 연결되어 있고, 그 중 하나의 전선을 끊어 두 개의 트리로 만든다.그리고 각 트리에서의 원소 개수 차이가 최소가 되는 그 최소값을 구하면 된다. union-find를 통해서 풀었다.반복문을 통해 각 전선을 하나씩 제거하면서 union-find연산을 통해 각 송전탑들이 속하고 있는 트리를 저장한다.그리고 각 경우에 대해, 트리에 속한 송전탑의 개수 차이가 최솟값인 경우를 갱신해서 리턴한다. 풀이 코드from coll..
union
이 문제는 도저히 어떻게 풀어야할지 감이 잡히지 않아서 풀지 못했다. 아이디어 부분에서 막힌 문제. 문제 자체는 쉽지만, 문제 조건을 보면 탑승구의 개수가 최대 10만개, 그리고 비행기의 개수가 최대 10만개라서 단순히 반복문을 통해 구현하면 무조건 시간초과가 뜨는 문제이다. 그래서 어떻게 해결해야할지 감을 잡지 못해 풀지 못했다. 풀이 이 문제는 서로소 집합 알고리즘을 사용해서 푸는 문제다. 각 탑승구를 서로 다른 집합으로 나타낸다고 해보자. 전체 탑승구가 4개일 때, 루트 0 1 2 3 4 탑승구 0 1 2 3 4 초기 상태에는 모두 루트 노드로 자기 자신을 가리키고 있다고 가정한다. 0번 탑승구는 존재하지 않지만, 문제 해결을 위해 0번 탑승구도 그려준다. 이 때, 비행기가 순서대로 들어오면 차례대..
문제에서 등장하는 여행지의 관계를 그래프로 그린다. 이 문제에서는 서로소 집합 알고리즘을 사용해서, 그래프 간의 연결성을 파악해 해결한다. "여행 계획"에 해당하는 모든 노드가 같은 집합에 속해 있다면, 가능한 여행 경로가 될 수 있다. 따라서 두 노드 사이에 도로가 존재하는 경우에는 union 연산을 통해 서로 연결된 두 노드를 같은 집합에 속하도록 만든다. 결과적으로는 여행 계획에 포함되는 모든 노드가 모두 같은 집합에 속하는지를 체크하여 출력하면 된다. 내 풀이 코드 # 여행 계획 # 특정 원소가 속한 집합을 찾기 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[..
