-
표준 입출력(Standart input/output)
프로그램은 대개 사용자의 입력을 받아 동작을 수행해 그 결과를 되돌려주는 형태를 띄기 때문에, 대부분의 프로그래밍 언어는 사용자와의 입출력을 수행하기 위해 표준 입출력 함수를 제공한다. 파이썬에서는 표준 입력 함수로 input을, 표준 출력 함수로 print를 제공한다. 표준 출력 함수 - print 표준 출력 함수 print는 데이터를 화면에 출력하고 싶을 때 사용한다. 가장 기본적인 형태는 print(x)의 형태로, 괄호 안에 자신이 출력하고 싶은 것을 넣으면 된다. print("Hello, world!") print(100) 출력 결과 Hello, world! 100 ,(쉼표)를 이용하여 출력하고 싶은 값을 구분해 여러 개를 한번에 출력해 줄 수 있으며, 이 경우에는 각각의 값이 공백 한 칸으로 구..
-
![파이썬 공부를 시작하면서]()
파이썬 공부를 시작하면서
2021년 11월 22일, 파이썬 공부를 시작하려고 한다. 파이썬은 네덜란드의 프로그래머 귀도 반 로섬(Guido van Rossum)이 1991년에 발표한 언어로, 1989년 크리스마스에 연구실이 닫혀 있어 심심해서 만든 언어라고 한다. 그 후 버전업을 계속하여 2008년에 Python 3을 릴리즈 했고, 이 글을 쓰고 있는 지금 현재 최신 버전은 3.10.0이다. 파이썬은 2 버전과 3 버전이 굉장한 차이를 보이며, 파이썬 2 코드가 3 버전에서는 호환이 안되는 경우가 많다. 나는 Python 3을 기준으로 공부하고 글을 작성할 것이다. 목차 Part I - 개요 파이썬 공부를 시작하면서 표준 입출력(Standard input/output) 파이썬 기본 문법 Part II - 변수와 자료형 변수(Va..
-
확장 유클리드 호제법(Extended Euclidean Algorithm)
확장 유클리드 호제법(Extended Euclidean Algorithm)은 유클리드 호제법의 확장으로 두 정수 $(a,b)$가 주어질 때 $\gcd(a,b)$를 구하고, 또한 정수해를 가지는 방정식 $ax + by = c$의 해 $(x, y)$를 구해주는 알고리즘이다. 베주 항등식의 세 번째 명제에 의해서 $ax + by$는 반드시 $\gcd(a,b)$의 배수이고, 따라서 $c$가 $\gcd(a, b)$의 배수가 아니라면 부정방정식 $ax + by = c$를 만족하는 정수해 $(x, y)$는 존재하지 않는다. $c = \gcd(a,b)$라고 가정할 때, 해 $(x,y)$는 유클리드 호제법의 과정을 따라가면서 구해낼 수 있다. $a,b$에 대해 유클리드 호제법을 돌리는 과정을 식으로 표현하면 다음과 같이..
-
![유니온 파인드(Union-Find)]()
유니온 파인드(Union-Find)
유니온 파인드(Union-Find), 또는 분리 집합(서로소 집합, Disjoint Set)은 여러 집합들을 표현하는 자료 구조다. Disjoint Set이라는 이름에서도 알 수 있듯이, 이 자료 구조가 표현하는 집합은 서로소이고, 모든 집합의 합집합은 전체집합이다. Union-Find라는 이름은 이 자료 구조가 기본적으로 두 가지 연산, 즉 union과 find만을 지원하기에 붙여진 이름이다. union 연산은 두 집합을 하나로 합치는 연산이고, find 연산은 어떤 원소가 어느 집합에 속하는지 알아내는 연산이다. 초기 상태의 유니온 파인드는 1~N까지의 원소(이건 0-index일 수도 있음)가 전부 크기 1인 집합에 담겨 있다. 여기에서 어떤 두 집합에 union 연산을 수행하면 두 집합이 하나로 합..
-
트리(Tree)
트리(Tree)는 그래프의 일종이다. 이름의 tree는 나무를 뜻하는 것으로, 꼭 나뭇가지가 위로 뻗어 나가는 형상을 닮았다고 해서 이런 이름이 붙여졌다. 다음 조건을 만족하는 그래프를 트리라고 한다. 연결 그래프이다. 간선의 방향을 무시했을 때 사이클이 존재하지 않는다. 다음 그림에서 1, 2번 그래프는 트리이고, 3번은 트리가 아니다. 3번은 간선의 방향을 무시하면 사이클이 생기기 때문에 트리라고 할 수 없다. 위 두 조건을 만족하는 트리에서는 $E = V-1$이라는 성질을 추가로 가진다. 또한, 트리에서 어떤 두 정점을 잇는 경로는 유일하다. 트리의 구조 트리에서 가장 위에 있는 노드를 루트 노드(Root node) 혹은 루트라고 한다. 루트와 다른 노드 사이의 거리를 그 노드의 깊이(Depth) ..
