전체 글
표준 입출력(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), 또는 분리 집합(서로소 집합, 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) ..
소수 판정과 소인수분해(Primality Test/Factorization)
소수(Prime number)는 $1$과 자기 자신을 제외한 양의 정수로는 나누어 떨어지지 않는 $1$이 아닌 양의 정수를 의미한다. 소수가 아닌 수를 합성수라고 한다. $1$은 소수도 합성수도 아니다. 소수에는 여러 흥미로운 성질이 있다. 그 중에서 소수 판정과 소인수분해에 쓰이는 중요한 성질로 어떤 합성수 $n$에 대해 $1$이 아닌 $n$의 약수 중 적어도 하나는 $\sqrt{n}$보다 작다는 성질이 있다. 소수 판정 소수 판정(Primality Test)는 어떤 수 $n$이 소수인지 아닌지를 판단하는 문제로, 정수론에서 중요한 문제 중 하나다. 어떤 수 $n$이 소수이려면 $2 \leq k \leq n-1$인 정수 $k$로 나누어 떨어지지 않아야 하므로, $2$부터 $n-1$까지 나눠보면 소수인지..
플로이드 와샬 알고리즘(Floyd-Warshall)
플로이드 와샬 알고리즘(Floyd-Warshall Algorithm)은 가중치가 있는 그래프에서 최단 거리를 구하는 알고리즘 중 하나다. 다익스트라나 벨만 포드 알고리즘은 한 정점으로부터 다른 정점까지의 최단 거리를 구하지만, 플로이드 와샬 알고리즘은 모든 정점 쌍 $(i, j)$에 대해 최단 거리를 구해준다. 또한 벨만 포드 알고리즘처럼 음수 간선이 있는 그래프에서도 정상적으로 작동한다. 동작 원리 플로이드 와샬 알고리즘의 동작 원리는 매우 간단하다. 정점 $i$와 $j$의 최단 거리를 계산할 때, 모든 정점 $k$에 대해 $i\rightarrow k \rightarrow j$가 $i \rightarrow j$보다 짧다면 $k$를 경유하는 것으로 최단 거리를 바꾸어 주면 된다. $i$와 $j$가 처음에..
너비 우선 탐색(Breadth-First Search, BFS)
너비 우선 탐색(Breadth-First Search, BFS)는 깊이 우선 탐색과 마찬가지로 그래프의 정점들을 순회하는 알고리즘이다. 깊이 우선 탐색은 될 수 있는 한 끝까지 깊이 들어갔다가 되돌아 오는 반면, 너비 우선 탐색은 시작 정점에서 가까운 정점부터 방문하는 특성을 지닌다. 정확한 동작 방식은 다음과 같다. 시작 정점을 '방문함'으로 설정하고 큐에 삽입 큐에서 가장 앞에 있는 정점과 인접한 정점들을 방문 / 큐에서 가장 앞에 있는 정점 제거 그 정점들을 방문하고 큐에 삽입 모든 정점을 방문할 때까지 2~4를 반복 시각화하면 다음처럼 나타낼 수 있다. 1번 정점을 시작 정점이라고 할 때, 시작 정점과 연결되어 있는 2, 3, 4번 정점을 순서대로 방문한 다음 2번 정점에 연결된 정점, 3번 정점..
깊이 우선 탐색(Depth-First Search, DFS)
그래프에서 깊이 우선 탐색(Depth-First Search, DFS)는 그래프를 탐색하는 방법 중 하나다. 이름에서 알 수 있듯이 DFS는 최대한 깊게 들어갔다가 다시 나오는 탐색 방식이다. 정확한 동작 방식은 다음과 같다. 시작 정점을 방문하고 '방문함'으로 표시 시작 정점과 연결되어 있는 정점 중 아직 방문하지 않는 정점을 시작 정점으로 놓고 1을 반복 연결되어 있고 방문하지 않은 정점이 없다면 이전 정점으로 돌아가 다시 2를 반복 모든 정점을 방문했으면 탐색을 종료 이것을 시각화하면 다음과 같다. 1번 정점을 시작 정점이라고 할 때, 연결되어 있는 정점인 2를 방문하고, 2에서는 5를 방문하고, 다시 돌아와 6, 9... 이런 식으로 방문하기 때문에 총 탐색 순서는 1-2-5-6-9-7-10-3-..
그래프의 정의와 표현
이산수학에서 그래프(Graph)는 정점(Vertex)와 간선(Edge)로 이루어진 집합이다. 기본적으로 위와 같은 형태이며, 간선은 정점 사이를 연결하는 역할을 한다. 또한 정점은 노드(Node)라고도 부른다. 두 정점 $u,v$가 있을 때, $u$에서 $v$로 가는 간선이 있으면 $u$는 $v$와 연결되어 있다고 한다. 어떤 정점에서 시작해서 다시 자기 자신에게 돌아오는 경로가 있다면 그 경로를 사이클(Cycle)이라고 한다. 일반적으로 정점의 개수를 $\vert V \vert$ 혹은 $V$로 나타내고, 간선의 개수는 $\vert E \vert$ 혹은 $E$로 나타낸다. 간선 간선은 정점과 정점을 연결하는 역할이다. 다음과 같은 특성을 추가로 가질 수 있다. 방향(Direction): 특정 방향으로만 ..