공데셍

https://www.acmicpc.net/problem/11726 DP(Dynamic Programming) 의 가장 기초적인 문제이다. dp[i] 를 $2 \times i$ 칸까지 고려했을 때 타일을 깔 수 있는 모든 경우의 수라고 정의하자. $2 \times i$ 의 타일링을 만드는 경우의 수는 다음 그림과 같이 세가지 경로에서 올 수 있는데, 첫 번째 그림은 dp[i-1] 에 타일 하나를 이어붙이는 경우이고 두 번째 그림은 dp[i-2] 에 타일 두개를 눕혀 한 묶음으로 $2\times2$ 타일을 이어붙이는 경우이다. 이 중 마지막 경우는 사실 dp[i-1]에 포함이 되어있던 경우이므로 무시할 수 있다. 따라서 dp[i-1]에 한 타일을 이어붙인 한 가지 경우 + dp[i-2]에 두 타일을 눕혀 ..

이 두 개는 프로그래밍할 때 자주 보던 폰트일 것이다. 다음 사진의 우측을 보면 글자 길이가 일정하지 않아 정렬되어보이지 않는다. 하지만 폰트를 Consolas로 바꾸고 나의 인생 달라졌다. PyQt의 widget들에 대해 사용했는데 사용 예를 들자면 다음과 같다. openButton = QPushButton("Open Video") openButton.setToolTip("Open Video File") openButton.setStatusTip("Open Video File") openButton.setStyleSheet("QPushButton {background-color : mintcream ; color : deepskyblue;}") openButton.setFixedHeight(24) op..

코드는 현재 공개하지 않습니다. 다만 다양한 사이트를 참고하였는데 https://pythonprogramminglanguage.com/pyqt5-video-widget/ https://towardsdatascience.com/speech-recognition-with-timestamps-934ede4234b2 이 두 곳에서 도움을 많이 받았습니다. 참고로 PyQt5 등을 이용하여 동영상 재생 시 컴퓨터에 코덱(CODEC)이 설치되어있어야 합니다. https://www.codecguide.com/download_kl.htm 이 사이트에서 Basic을 다운로드한 후 기본값으로 다 ok하고 설치하면 됩니다. 설치 후 윈도우에서 찾기해보면 Codec Tweak Tool 이라는 프로그램이 생성되는데, 그 프로그램..

그래프 탐색 문제에서 종종 출발점에서 거리가 얼마나 되는지 측정해야 하는 때가 있다. https://www.acmicpc.net/problem/5014 이런 문제가 그렇다. 기본적인 BFS 코드는 다음과 같다. void BFS(int begin_node) { queue que; que.push(begin_node); visit[begin_node] = 1; while(que.empty() == false) { int cur = que.front(); cout g >> u >> d; BFS(f, s, g, u, d); return 0; }

다익스트라 알고리즘(Dijkstra's Algorithm)은 간선(edge)의 가중치가 있는 그래프에서 시작점이 고정되어 있을 때 모든 정점(vertex, 복수형은 vertices)으로 가는 최단 경로의 거리 합을 모두 구하는 알고리즘으로 에드거 다익스트라(Edsger Dijkstra) 가 1959년에 발표했다. 알고리즘을 설명하기 앞서 몇가지 기호들을 정의하고 시작한다. $PL$ : Permanent Label 라는 의미로, 확실하게 최단거리 계산이 끝난 정점들이 들어가는 집합이다. $TL$ : Temporary Label 라는 의미로, 집합 PL에 포함된 정점을 거쳐 갈 수 있는 최단거리가 계산된 정점의 집합이다. $L_j$ : 시작점에서 정점 $j$ 까지 도달하기 위한 확실한 최소 거리로써 $PL$..

이 포스트를 이해하기 위해 필요한 사전지식 : C++(혹은 C), 그래프 이론, 큐(자료구조) 그래프의 노드(Node)를 모두 탐색하는 방법으로 크게 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 두 가지가 있다. 다음과 같은 그래프가 있다고 하자. 8개의 노드와 7개의 간선으로 이루어진 양방향 그래프이다. 어디에서 시작하든 상관은 없지만 시각적 편리함을 위해 예시에서는 데이터 2가 저장된 노드에서 시작하기로 한다. DFS (깊이 우선 탐색) Depth First Search의 약자이며 말 그대로 깊이 갈 수 있는 곳까지 탐색하는 알고리즘. 각 노드에 연결된 노드들 중 아직 탐색하지 않은 노드들 중 아무거나 골라서 그 노드로 넘어가는 알고리즘이다. 위의 예시에서는 2에서 시작했으므로 2에 연결된 7..