본문 바로가기

프로그래밍

 (85)
백준 2252 줄 세우기 - 파이썬 문제. 풀이. 위상 정렬은 사이클이 없고 방향만 존재하는 그래프에서 정점을 나열하는 방법이다. 정점간의 연결관계를 저장한 리스트와 정점으로 들어오는 그래프 개수를 저장하는 리스트를 만든다. 그리고나서 진입 루트가 0 즉 자기 자신으로 들어오는 그래프 개수가 0인 정점들을 큐에 저장하고 해당 정점과 연결되어 있는 노드에서 진입 루트 개수를 하나씩 빼준다. 이렇게 계속 반복하면 된다. 소스코드.
백준 20040 사이클 게임 - 파이썬 문제. 풀이. 유니온 파인드를 이용해서 풀면된다. 우선 생각해야 할게 유니온 연산을 하기전에 파인드 연산을 먼저해서 둘의 루트 노드가 같다면 사이클이 완성된것이다. 예를 들어 parent = [0, 1, 2, 3, 4, 5] 가 있고 이제부터 입력을 받는다고 한다면 0 1이 들어오면 둘의 파인드 연산을 했을때는 각각 루트 노드가 0 , 1이다 둘의 루트 노드가 다르니 유니온 연산을 시행한다 1, 2 입력이 들어오면 둘의 파인드 연산 결과는 0, 2 2, 3 입력이 들어오면 둘의 파인드 연산 결과는 0, 3 0, 3 입력이 들어오면 둘의 파인드 연산 결과는 0, 0 이므로 사이클이 완성됐다. 소스코드.
백준 4195 친구 네트워크 - 파이썬 문제. 풀이. 유니온 파인드를 이용해서 풀면 된다. 입력이 문자열이기때문에 딕셔너리를 통해서 풀었다. 2개의 딕셔너리를 선언하고 number 딕셔너리의 루트 노드에 친구 관계의 친구관계의 수를 저장하고 매 단계 루트노드를 출력하면된다. 소스코드.
백준 1976 여행 가자 - 파이썬 문제. 풀이. https://turret1234.tistory.com/176 백준 1717 집합의 표현 - 파이썬 문제. 풀이. 유니온 파인드의 이해가 필요하다. 유니온 파인드는 순수히 노드 간의 연결 관계를 파악할 때 유용하게 사용된다. 유니온 파인드에는 유니온 연산과 파인드 연산이 있다 1) Union -> 서 turret1234.tistory.com 위 링크랑 풀이가 거의 유사하다. 입력 조건이 조금 다르지 푸는 알고리즘은 거의 똑같다. 연결된 집합끼리 유니온 연산을 해 주고 여행 계획인 도시끼리 파인드 연산을 해서 모두 같은 집합이라면 yes 아니면 no를 출력하면 된다. 소스코드. import sys # 유니온 (집합 합치기) def union(a, b): a = find(a) b = find(..
백준 1717 집합의 표현 - 파이썬 문제. 풀이. 유니온 파인드의 이해가 필요하다. 유니온 파인드는 순수히 노드 간의 연결 관계를 파악할 때 유용하게 사용된다. 유니온 파인드에는 유니온 연산과 파인드 연산이 있다 1) Union -> 서로 다른 두 트리(집합)을 합치는 연산 2) Find -> 루트 노드를 찾는 연산 find 연산은 어떤 노드를 인자로 넘겼을 때, 해당 노드의 루트 노드를 반환하며 재귀 호출의 형태로 구현한다. 시간 복잡도 효율을 높이기 위하여 자식 노드들의 값을 모두 루트 노드를 변경하여 경로 압축 최적화를 진행한다. union 연산은 서로 다른 두 트리(집합)을 합친다. 각 트리의 루트 노드를 비교하여 둘 중 작은 루트 노드를 기준으로 합치게 된다. 소스코드.
백준 5639 이진 검색 트리 - 파이썬 문제. 풀이. 이진 트리는 루트 기준으로 왼쪽은 루트 값 보다 작은 수들, 오른쪽은 큰 수 이다. 즉 root값을 기준으로 왼쪽 인덱스, 오른쪽 인덱스를 찾아 값을 구하면 된다. 소스코드.
백준 2263 트리의 순회 - 파이썬 풀이. 다음과 같은 트리가 있다하면 순회의 결과는 다음과 같다. 전위 순회 : 0->1->3->7->8->4->9->10->2->5->11->6 중위 순회 : 7->3->8->1->9->4->10->0->11->5->2->6 후위 순회 : 7->8->3->9->10->4->1->11->5->6->2->0 중위와 후위를 살펴보면, 후위의 마지막 요소가 루트 노드인 것을 알 수 있다. 그러면 중위 순회에서 루트 노드를 기준으로 left, right를 나누면 (7, 3, 8, 1, 9, 4, 10), (11, 5, 2 6)으로 나뉘어진다. 이 left, right의 길이만큼 후위 순회에서 나눈다면 (7, 8, 3, 9, 10, 4 ,1), (11, 5, 6, 2) 로 나뉘어진다 다시 후위 순회와 중위 순회를 ..
백준 1991 트리의 순회 - 파이썬 문제. 풀이. 트리의 순회만 안다면 매우 쉽게 풀 수 있다. 전위 순회 = 루트, 왼쪽 , 오른쪽 중위 순회 = 왼쪽, 루트, 오른쪽 후위 순회 = 왼쪽, 오른쪽, 루트 이다. 딕셔너리를 이용하여 풀었다. import sys # 전위순회 def preorder(root): if root !='.': print(root, end='') preorder(tree[root][0]) preorder(tree[root][1]) # 중위순회 def inorder(root): if root !='.': inorder(tree[root][0]) print(root, end='') inorder(tree[root][1]) # 후위순회 def postorder(root): if root !='.': postorder(tr..

티스토리툴바