728x90 트리15 [Python] 백준 4195 친구 네트워크 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 문제 풀이 - union find 문제이다. => 이에 대한 함수식을 쓰지 못하면 풀기 힘들다. (union find 문제라는 것은 알았는데 한동안 안풀면 까먹기 일상이다.) - 리스트를 이용하기보다(부모, 자식 모두 string name이 있어서 리스트로 index를 찾기는 너무 시간복잡도가 클 것 같다.) 딕셔너리(dict)을 이용하여 dict['name']= parents['nam.. 2022. 12. 21. [Python] 백준 1717 집합의 표현 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 문제 해결 - 집합을 어떻게 합칠 것인가? ( union 사용해야겠지...?) - set.add() 사용 할 것인가? => 사용하면 좋은데 어떻게 일반적으로 표현을 할 것인가? ex) 1번집합 2번집합 합치면 뭐로 표현??? - 해결책 => 트리를 이용해 부모를 정하자 ! ex) 1번집합 2번집합 합치면 숫자 작은 1번집합이라고 하자! CODE import.. 2022. 12. 13. [Python] 백준 1991 트리 순회 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 해결 전위 순회(preorder) 중위 순회(inorder) 후위 순회(postorder) 스캔 순서 노드 방문→왼쪽 자식→오른쪽 자식 왼쪽 자식→노드방문→오른쪽 자식 왼쪽 자식→오른쪽 자식 →노드 방문 예시 A→B→D→C→E→F→G D→B→A→E→C→F→G D→B→E→G→F→C→A 위 내용을 잘 모르겠으면 자료구조(Data Structure)의 트리 부분을 공부하고 오는 것이 좋.. 2022. 12. 10. 이전 1 2 3 4 다음 728x90
