yeongminb의 PS 블로그

Floyd Warshall 알고리즘은 다익스트라 알고리즘의 진화(?) 버전으로 가중치가 주어진 그래프에서 모든 정점으로부터 모든 정점으로까지의 최소 거리를 구하는 알고리즘이다. Floyd Warshall 알고리즘은 모든 거쳐가는 정점을 기준으로 DP처럼 동작해 구현이 매우 간단하다. 1) Floyd Warshall 알고리즘의 동작 floyd warshall 알고리즘은 다음과 같이 동작한다.let) $d[i][j] :=$ ($i$부터 $j$까지의 최소거리 배열)let) $graph[i][j] :=$ ($i$와 $j$를 연결한 간선의 가중치) -> 연결이 안될 경우 INF(∞)1) $d[i][j]$ 초기화 $$d[i][j] = \begin{cases}0 & i=j\\graph[i][j] & otherwise..

다익스트라 알고리즘은 양의 가중치만 있는 그래프에서 어떤 정점으로부터 모든 정점까지의 최소 거리를 구하는 알고리즘이다. 다익스트라 알고리즘은 최단거리를 구할 때 매우 유용해서 GPS등에서도 사용한다고 한다(정확히는 모르지만,,). 쉽게 설명되어있는 유튜브 영상 : https://www.youtube.com/watch?v=EFg3u_E6eHU  아주 예전에 다익스트라 알고리즘을 처음 알았을 때 아주 똑똑한 친구가 위의 영상을 추천해줘서 봤었다. 이해하기 쉽게 설명되어있어서 다익스트라 알고리즘을 배우려고 하거나 까먹었을 때 보면 좋은 영상이다.  1. 다익스트라 작동 과정다익스트라는 다음과 같이 작동한다.1) pair형태로 {0, 시작정점}을 priority queue에 넣는다.2) priority queu..

MST 는 Minimum Spanning Tree (최소신장트리)의 약자로 가중치가 있는 그래프에서 모든 가중치의 합이 최소가 되도록 하는 어떤 트리(정점이 $V$개일 때 간선이 $V-1$ 인 연결그래프)를 의미한다. 예를 들어서 아래의 그래프에서는 찐하게 칠해진 트리가 가능한 모든 트리 중에서 가중치의 합이 최소이므로 MST 가 된다. 주어진 그래프에서 MST 를 구하는 알고리즘은 대표적으로 $Prim's\space Algorithm$ 과 $Kruskal\space Algorithm$ 이 있다. $Kruskal\space Algorithm$ 에 대해 알아보자. 1) $Kruskal\space Algorithm$  의 동작 Kruskal 알고리즘은 다음과 같이 동작한다.1) 모든 간선을 가중치를 기준하여..

Union-Find 알고리즘은 서로소 집합(Disjoint-Set) 알고리즘 이라고도 한다. 어떤 노드들이 서로 같은 그래프에 속해 있는지(두 노드까지의 경로가 존재하는지) 판별하기 위해서 사용되며 그래프를 다룰 때 중요한 알고리즘 중 하나이다.  Union-Find 알고리즘은 자신의 부모 노드를 불러오는 알고리즘, 두 노드를 이어주는 알고리즘(Union), 두 노드가 같은 그래프에 있는지 확인하는 알고리즘(Find)으로 구성된다. 이 알고리즘들은 각 노드의 부모 노드를 기준으로 구현하고 보통 parent라는 일차원 배열에 부모 노드들을 저장한다. 예시)노드12345부모 노드12345  먼저 초기에 아무 간선도 없을 때에는 각 노드의 부모 노드를 자기 자신으로 지정해둔다. $O(N)$ 알고리즘1. Uni..

1. BFS와 DFS의 개념 1) BFS먼저 BFS는 영어로 풀어쓰면 Breath-First-Search로 너비 우선 탐색을 의미한다.  다음과 같은 그래프가 주어졌을 때 BFS의 방식으로 그래프 탐색을 어떻게 하는지 알아보자. 먼저 기준 노드를 잡아야한다. 기준 노드는 쉽게 말하면 탐색을 시작하는 노드을 의미한다. 편의상 1번 노드를 기준으로 탐색을 시작하자. BFS 로 탐색하면 아래와 같은 결과가 나온다.1 - 2 - 4 - 5 - 3 - 6 - 7 BFS는 기준노드와 거리가 가까운 노드들부터 탐색을 한다고 봐도 무방하다.   2) DFS다음으로 DFS는 Depth-First-Search로 깊이 우선 탐색을 의미한다.아까와 같은 그래프가 주어져있고 1번 정점부터 탐색을 시작한다고 할 때 탐색 결과는 ..

문제 링크 문제 풀이 이 문제는 $N\times M$ 칸에 숫자들이 적혀 있을 때, 테트로미노 타일을 이용해 타일이 포함하는 수들의 합의 최댓값을 구하는 문제이다.  여기서 테트로미노는 폴리노미노의 한 종류로 네 개의 정사각형이 변끼리 인접하여 만들어지는 도형을 의미한다.    $N,M ≤ 500$ 이라서 그냥 브루트포스로 모든 점들에 대해서 백트랙킹으로 탐색해줘도 충분하다. 이때 시간복잡도는 $O(MN)$인데, 정확히는 백트랙킹 할 때 최대 $4^4$ 개의 가짓수가 있어서 $256MN$만큼의 연산이 필요하다.  먼저 Back Tracking 함수를 먼저 구현해보자. 초기 좌표와 깊이, 그리고 현재까지 숫자의 합을 매개변수로 하였다.void BT(int x, int y, int depth, int k){..

파이썬에서 tkinter 모듈을 이용해서 암호화 복호화 프로그램을 만들어보았다. 그러려면 tkinter 창의 간단한 디자인과 암호화 복호화 방법을 정해야한다.디자인 먼저 디자인은 크게 중요하지 않으므로 간단하게 하였다. 암호화 시킬 텍스트를 집어넣는 엔트리와 암호화된 결과를 보여줄 엔트리, 또 암호화 시킬 버튼이 필요하고, 복호화도 마찬가지로 복호화 시킬 암호를 넣는 엔트리와 복호화된 결과를 보여주는 엔트리, 또 복호화 버튼이 필요하다. 추가적으로 무슨 엔트리인지를 보여주는 텍스트와 모든 내용을 지우는 지우기 버튼도 추가하였다.코드from tkinter import *win = Tk()win.title('Encryption & Decryption')win.geometry('400x400')entry1 =..

예전에 LIS알고리즘을 DP로 $O(N^2)$만에 구현하는 포스팅을 올린 적이 있다. 하지만 이 알고리즘을 쓰기엔 시간복잡도가 크다보니 시간초과가 나는 문제가 많다.LIS $O(N^2)$  이번 포스팅에서는 이분탐색을 활용한 $O(NlogN)$ LIS 알고리즘을 올려보려고 한다. 이분탐색을 써서 푸는 백준 문제는 아래 세 개가 있다.가장 긴 증가하는 부분 수열 2가장 긴 증가하는 부분 수열 3 가장 긴 증가하는 부분 수열 5  LIS 길이 구현 방법 외부 배열이나 벡터에서 각각의 숫자들의 lower bound를 구해 그 인덱스로 넣어주는 방식이다. 아래 그림은 LIS 이분탐색 과정이다. 이렇게 이분탐색으로 배열을 만들고 나면 크기 순서대로 숫자들이 정렬이 되어있다. 여기서 이 배열의 길이는 LIS의 길이..

내신 공부를 위해 과학 공부를 하고 있던 중 친한 친구가  떨어진 거리나 비열에 따라서 복사 평형에 도달하는 시간이 어떻게 되냐라고 물어봐서 탐구해보게 되었다. 복사 평형은 물체가 흡수하는 에너지의 양과 물체의 온도에 의한 복사에너지의 양이 같아질 때 온도가 일정하게 유지되는 상태를 말한다. 이를 그래프로 나타내어 보면 아래와 같이 표현된다.    물체는 (흡수하는 에너지량) - (방출하는 에너지량) 만큼의 에너지로 자신의 온도를 변화시킨다. 이 점을 이용해서 시간을 계산해볼 것이다. 먼저 사용할 공식을 먼저 써보자.여기서 위의 식은 대부분이 알 것이라 생각하고, 밑의 식은 슈테판-볼츠만 법칙으로 M은 단위 시간, 물체의 단위 면적 당 물체가 방출하는 복사에너지를 의미한다. 시그마는 슈테판-볼츠만 상수로..

문제 링크   "물리학" 카테고리에 있는 문제들을 풀어보다가 이 문제가 재미있게 생겨서 풀어보았다. 예전에 이런 충돌수에 관련된 문제를 3Blue1Brown 이라는 굉장히 좋은(?) 채널에서 본 적이 있다.유튜브 영상 이 영상에서는 두번째 물체의 질량이 100의 거듭제곱 꼴일 때 충돌횟수가 π의 앞의 자리수가 되는 이유를 설명해주고 있는데 예전에 흥미롭게 봤던 경험이 있어서 생각이 났다.  1. 문제 풀이 먼저 알아야할 것은 두 번째 물체의 초기속력이 0만 아니라면 충돌수에 영향을 주지 않는다는 것이다. 만약 첫 번째 물체의 초기속력이 있었다면 상관이 있겠지만 첫 번째 물체의 초기속력이 0이므로 두 번째 물체가 어떤 속력을 가지든 속력비율은 항상 일정하기 때문이다. 근데 소수점계산에서 오류가 발생할 수도..

이항게수와 관련된 PS를 하다가 범위가 큰 $n$과 범위가 큰 $r$에 대해서 ${n \choose r}$의 일의 자리 수를 구해야하는 일이 생겼다. 일반적인 콤비네이션 계산($O(n)$)을 하고 일의 자리수를 구하면 시간초과가 나서 다른 방법이 필요했다. 이 포스팅에서는 이와 관련된 내용을 적어보려고 한다.1. 조합을 계산하는 일반적인 방법 가장 쉬운 방법으로는 정의식대로 $n!$, $(n-r)!$, $r!$을 모두 계산해주고 연산해주는 것이다. 하지만 $n$과 $r$이 조금만 커져도 계산 시간이 오래걸리고 PS에서는 정수형 범위나 심지어는 long long 범위까지 넘어갈 수 있기 때문에 좋지 않은 방법이다.int factorial(int n){ int output = 1; for(int ..

높이가 $h$인 지점에 있는 질량 $m$의 물체를 벽에서부터 막대를 이용해 경사각이 $θ$인 경사까지 굴릴 때 걸리는 최소 시간은? 그리고 그때의 막대의 길이는?   문제만 놓고 보면 굉장히 쉬운 문제 같아보이지만 처음 접근할 땐 생각을 많이 해봐야한다. 이 문제를 풀어보기 전에 조금 더 쉬운 문제를 한 번 보자. 어떤 원에서 지표와 수직한 지름으로 공을 떨어뜨릴 때 걸리는 시간과 다른 호로 공을 떨어뜨릴 때 걸리는 시간이 같을까? 이건 자명하게 같다. 왜냐하면 둘 다 등가속도 운동을 하는데, 가속도의 비는 1 : sinθ이고, 거리비는 sinθ : 1이기 때문에 쉽게 알 수 있다.   그럼 이것을 이용해 이 문제를 풀어보자.$\overline{PA}$를 지름으로 하는 원을 그리고, 그 원과 경사의 교점..

아마 대부분의 사람들이 픽의 정리를 들어본 적이 없을 것이다. 우리나라 교과과정에도 없고 KMO에서도 전혀 나오지 않는 내용이기 때문이다. 최근에 학원에서 이 정리에 대해 짧게 배운 적이 있다. 학원에서 들었을 때 꽤 흥미롭고 재미있어 보여서 추가로 찾아보았다. 여기서는 그런 내용들을 정리할 것이다. 또 이와 관련된 문제를 만들었는데, 그것도 풀어볼 것이다.픽의 정리 꼭짓점이 격자점인 다각형에서 다각형의 내부에 있는 격자점의 수를 I 라고 하고, 다각형의 선분 위에 있는 격자점의 개수를 B라 할 때, 다각형의 넓이는                                                                        S = I + B/2 -1로 나타낼 수 있다.  이것이 무슨 의..

몬즈의 정리(Monge's Theorem)는 KMO 2차에 자주 나오는 정리로 근축에 대해 배울 때 꼭 배워야히는 정리 중 하나이다. 여기서는 몬즈의 정리와 이와 관련된 재미있는 문제 몇 개를 풀어볼 것이다.몬즈의 정리 : 세 원 A,B,C가 두 점에서 서로 교차할 때, 세 공통현은 한 점에서 만난다. ( 세 원의 근축들은 공점선이다.) 참고하면 좋은  사이트 : https://en.wikipedia.org/wiki/Power_center_(geometry) Power center (geometry) - WikipediaFrom Wikipedia, the free encyclopedia For 3 circles, the intersection of the radical axes of each pair D..