Union Find 서로소 집합 알고리즘
1. 서로소 집합이란 예를들어 집합 {1,2} 와 {2, 3}은 서로소 가 아니지만 {1, 2}, {3, 4}는 서로소 집합이다. 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 서로소 집합 자료구조는 union과 find 2개의 연산으로 조작할 수 있다. union연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다. find 연산은 특정한 원소가 속한 집합이 어떤 집한 인지 알려주는 연산이다. 예를 들어 {1, 2, 3 ,4, 5, 6} 에서 서로소 부분 집합이 다음과 같이 주어진다고 가정하자 {1, 4} , {2, 3}, {2, 4}, {5, 6} 이와 같이 주어진 서로소 부분집합들은 각각 동일한 서로소 집합에 포함되어 있는 원소들이..
2023. 1. 28.
정렬
파이썬으로 문제를 풀다보면, 여러 조건으로 소팅을 해야하는 경우가 있다. 일반적인 소팅은 다음과 같이 sorted() 혹은 .sort() 를 사용한다. a = [4,1,2,5,7,3,6] b = sorted(a) # b = [1,2,3,4,5,6,7] sorted() 를 찬찬히 살펴보면 다음과 같다. a = [(1, 2), (0, 1), (5, 1), (5, 2), (3, 0)] # 인자없이 그냥 sorted()만 쓰면, 리스트 아이템의 각 요소 순서대로 정렬을 한다. b = sorted(a) # b = [(0, 1), (1, 2), (3, 0), (5, 1), (5, 2)] # key 인자에 함수를 넘겨주면 해당 함수의 반환값을 비교하여 순서대로 정렬한다. c = sorted(a, key = lambd..
2023. 1. 20.
코딩테스트 파이썬 문법 (기초편)
자료형 #소수부가 0일 때 0을 생략 a = 5. # 5.0 # 10억의 지수 표현 방식 (최단 경로문제에서 자주 사용) a = 2e+9+1 # 컴퓨터는 2진수 체계이기 때문에 실수 덧셈을 정확히 하지 못한다. 보통 5째 자리에서 반올림 하면된다. a = 0.3 + 0.6 print(rount(a,4)) 수 자료형의 연산 a = 7 b = 3 # 나누기 a / b # 나머지 a % b # 몫 a // b # 거듭 연산자 a ** b # a의 b승 자료형 변환 # 문자열을 한 글자씩 분리하여 리스트에 저장 str = 'Hello world!' list = list(str) ['H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', '!'] # Java에서 다음과 같..
2023. 1. 12.
