코딩/백준 (Python) 검색 결과
183 개의 검색 결과가 있습니다.
코딩/백준 (Python)

백준 20040번: 사이클 게임 (Python)

접근 이번 문제에서는 유니온파인드 알고리즘을 이용하여 풀 수 있다. 유니온파인드 알고리즘 설명: 2021.05.01 - [코딩/백준 (Python)] - 백준 1717번: 집합의 표현 (Python) 백준 1717번: 집합의 표현 (Python) 접근 파인드유니온 알고리즘을 모르지만 일단 구현되게 하여 풀기는 하였다. 하지만 파인드유니온 알고리즘을 처음 접했으니 제대로 공부하고 최적화 방법도 알아보고 코드를 다시 작성해보았 ca.ramel.be 유니온파인드 알고리즘을 수행하면서 i 번째 단계에서 주어진 두개의 수의 루트 노드가 같으면 싸이클이 이루어지므로 i를 출력해주고 연산을 마친다. 코드 import sys def find(x): if connect[x] < 0: return x p = find(co..

2021. 5. 2. 01:18
코딩/백준 (Python)

백준 4195번: 친구 네트워크 (Python)

접근 유니온파인드 알고리즘을 이용하여 풀 수 있다. 유니온파인드 알고리즘 설명: 2021.05.01 - [코딩/백준 (Python)] - 백준 1717번: 집합의 표현 (Python) 백준 1717번: 집합의 표현 (Python) 접근 파인드유니온 알고리즘을 모르지만 일단 구현되게 하여 풀기는 하였다. 하지만 파인드유니온 알고리즘을 처음 접했으니 제대로 공부하고 최적화 방법도 알아보고 코드를 다시 작성해보았 ca.ramel.be 여기서는 weighted union find를 사용하지 않고 대신 문자형을 받을 수 있는 dictionary를 두개 사용하여 문제를 해결하였다. 기존 리스트들의 역할을 하는 딕셔너리와 집합의 크기를 나타내는 딕셔너리를 각각 이용했다. 코드 import sys def find(x)..

2021. 5. 1. 22:47
코딩/백준 (Python)

백준 1976번: 여행 가자 (Python)

접근 유니언파인드 알고리즘을 이용하여 풀 수 있다. 알고리즘에 대해서는 이전 글에서 자세하게 설명하여 링크를 남기도록 한다. 유니언파인드 알고리즘 설명: 2021.05.01 - [코딩/백준 (Python)] - 백준 1717번: 집합의 표현 (Python) 백준 1717번: 집합의 표현 (Python) 접근 파인드유니온 알고리즘을 모르지만 일단 구현되게 하여 풀기는 하였다. 하지만 파인드유니온 알고리즘을 처음 접했으니 제대로 공부하고 최적화 방법도 알아보고 코드를 다시 작성해보았 ca.ramel.be 연결된 도시들끼리 유니언을 이용하여 집합을 만들어주고, 주어진 여행경로들이 같은 루트 노드를 가지고 있는지를 체크해주면 된다. 코드 import sys def find(x): if connect[x] < 0..

2021. 5. 1. 20:49
코딩/백준 (Python)

백준 1717번: 집합의 표현 (Python)

접근 파인드유니온 알고리즘을 모르지만 일단 구현되게 하여 풀기는 하였다. 하지만 파인드유니온 알고리즘을 처음 접했으니 제대로 공부하고 최적화 방법도 알아보고 코드를 다시 작성해보았다. 유니온 파인드 알고리즘이란? 그래프 알고리즘의 일종으로 상호배타적 집합, Disjoint-set이라고도 한다. 여러 노드가 존재할 때 어떤 두개의 노드를 묶어주고, 또 어떤 두 노드가 같은 집합에 속해있는지 확인하는 알고리즘이다. FIND: 노드 x가 어느 집합에 포함되어 있는지 찾는 연산 UNION: 노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산 유니온 파인드 구현 트리를 통해서 유니온파인드가 구현될 수 있다. parent[i] 리스트를 작성하여 i노드의 부모노드라고 정의하고 초기화해준다. parent[i..

2021. 5. 1. 11:46
코딩/백준 (Python)

백준 4803번: 트리 (Python, PyPy3)

접근 서로 연결된 '연결 요소'가 싸이클을 이루는지 아닌지 체크하여 싸이클이 아닌 연결 요소의 개수를 세어주면 된다. 주의할 점은 다른 정점에 연결되지 않은 외딴 정점 또한 트리의 조건에 부합한다는 것이다. 한개의 연결 요소가 싸이클을 이루는지 체크하는 방법으로 BFS 알고리즘을 사용하였다. 첫번째 정점부터 탐색하면서 현재 정점의 visited를 체크하고 False라면 True로 갱신해준다. 첫번째 정점에서 연결된 정점들을 탐색하면서 visited가 False라면 queue에 추가해준다. 탐색을 진행하면서 queue에서 꺼내온 현재 정점의 visited가 True라면 이미 지나온 다른 요소와 다른 방법으로 연결되어 있으므로 (싸이클을 이루므로) tree로 카운트하지 않는다. queue를 모두 탐색했는데 ..

2021. 4. 29. 23:17
코딩/백준 (Python)

백준 5639번: 이진 검색 트리 (Python)

접근 트리 순회 문제 중, 인오더와 포스트오더가 주어졌을 때 프리오더를 구하는 문제가 있었는데 그 문제와 유사하게 생각하면 좋다. 이번에는 프리오더만 주어지지만 추가적으로 '이진 검색 트리'라는 트리의 속성을 이용하여 문제를 해결할 수 있다. 유사 문제: 2021.04.29 - [코딩/백준 (Python)] - 백준 2263번: 트리의 순회 (Python) 백준 2263번: 트리의 순회 (Python) 접근 재귀를 이용하여 문제를 풀 수 있다. 포스트오더의 마지막 숫자는 전체 트리의 루트이다. 인오더의 특성을 이용, 루트를 기준으로 왼쪽트리, 오른쪽트리의 노드 수를 구할 수 있다. 왼쪽 트 ca.ramel.be 주어진 이진 검색 트리의 프리오더를 보면 다음과 같이 생각할 수 있다. 주어진 프리오더의 루트..

2021. 4. 29. 21:50
반응형