본문 바로가기

Python

(6)
K-means 시뮬레이터 간단한 시뮬레이터다. 좀 경험이 쌓여서인지, 그전 것들보다 구현하기 쉬웠다. 이번에도 Python과 pygame을 사용해서 구현했다. import pygame import random def drawNode(nodeN, color): pygame.draw.circle(screen, color, dotToScreenDot(nodes[nodeN]), NODE_RADIUS, 3) screen.blit(font.render(f'#{nodeN}', True, color), dotToScreenDot((nodes[nodeN][0] - 5, nodes[nodeN][1] + 5))) def dotToScreenDot(a): return int(round(a[0])), int(round(SCREEN_SIZE[1]-a[1..
Kruskal Algorithm 시뮬레이터 MST를 구하는 유명한 알고리즘인 Kruskal 알고리즘의 시뮬레이터를 만들어 봤다. 이론상 노드가 얼마가되든 상관 없지만, 보기가 힘들니 5개 정도만 쓰자. 점이 좀 잘 퍼졌으면 좋겠는데, 그렇지 않아서 아쉽다. 프로그램이 끝나면 MST를 출력하거나, 못만들었다는 얘기를 해준다. 이번에도 코드가 구데기니 사용만 하자. 간선의 중간쯤에 있는 것은 가중치다. 초록색은 다음에 볼 간선이다. 초록색이 떴고, 빨간색으로 변하면 MST의 간선이 된 것이고, 검은색으로 변하면 사이클이 발생해 MST에 넣지 못한 것이다. 간선 생길확률은, 확률 결정하는 값을 $a$라고 할때, $\frac{3}{a}$다. 그리고 간선 개수는 확률적으로 노드 개수를 $n$이라고 할때, 간선 만드는 루프를 $n-1 + n-2 + \dot..
Union-Find 시뮬레이터 Python과 pygame을 이용해 Union-Find자료구조의 시뮬레이터를 만들어 봤다. 경로압축할지 선택 할 수 있다. 노드의 연결상태를 그려주는 코드가 짜기 매우 힘들었다.ㅜㅜ 결국 DFS를 사용해 해결했다. 다만, 너무 노드 연결을 많이하면 연결상태 알려주는 그림이 이상해지니, 조금만 해보자. 이번에도 코드가 구데기니 사용만 하자. import pygame def find(n): if p[n] == n: return n return find(p[n]) def beautifulFind(n): return p[n] def optimizedFind(n): if p[n] == n: return n p[n] = optimizedFind(p[n]) return p[n] def union(n1,n2): glo..
최소크기 외접원-경사하강법 시뮬레이터 최소크기 외접원을 구하는 알고리즘 중에는 경사하강법이 있다. 이미 설명이 잘 되어있는 글이 많으므로, 시뮬레이터를 통해 이해에 도움을 주려고 한다. 아래에 설명이 잘 되어있는 글을 링크 걸어놨다. wethinknewrise.tistory.com/5 [백준 2389] 세상의 중심에서... https://www.acmicpc.net/problem/2389 2389번: 세상의 중심에서... 첫째 줄에 N(1≤N≤100)이 주어진다. 다음 N개의 줄에는 x, y 좌표가 주어진다. 각각의 좌표는 소수점 여섯째자리까지 주어지며, -600,000 ≤ x.. wethinknewrise.tistory.com www.secmem.org/blog/2019/04/08/Smallest-Enclosing-Circle/ 최소 외접..
Monotone Chain 시뮬레이터 볼록껍질 만드는 알고리즘이다. en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain 파이썬 코드 보고서 이해하는게 제일 쉬웠다. Graham Scan에 비해서 안유명한 것같은데, 개인적으로는 Graham Scan보다 매우 좋아함. 각도 정렬이 아닌, 좌표가지고 정렬을 하기 때문이다. 아래는 이해를 돕기 위해 pygame을 이용해 볼록껍질이 어떻게 만들어지는지 표현한 것이다. 코드는 진짜 구데기니까 이해하지말고 사용만 하자. FPS가 낮을 수록 천천히 볼 수 있다.(단, 정수여야함) 중간에 나가는게 안된다. 나갈려면 alt+tab누르고 거기서 끄면 된다. 아니면 볼록껍질 완성되고 10초뒤에 꺼진다. import ..
파이썬 예제[Python] wxpython , sqlite3이용해서 일기장 만들기 한 5일동안 만들었다.아직 완성은 아니지만, 뭐 완성품 올리는 블로그도 아니고, 꽤 잘 작동해서 올리게 되었다. DbManager.py이다.import sqlite3 import arrow import os class DbManager: def __init__(self): self.conn = sqlite3.connect(os.path.join(os.path.expanduser('~'), 'documents', 'Diary', 'Diary.db')) self.c = self.conn.cursor() def saveDiaryInfo(self, date, time, todayFeel, todayThoughtsCount, writer): sql = f'INSERT INTO Diary (date, time, t..