본문 바로가기

분류 전체보기

 (115)
백준 1766 문제집 A, B가 들어오면A->B 의 edge를 만들고완성된 그래프에 대해 위상정렬을 수행하는 문제. 단 위상정렬을 할 때 위상정렬큐에 indegree(진입차수)가 0인 노드를 한번에 다 넣지 말고 한번에 하나씩만 넣어야 한다. 풀이하자면 다음과 같다 #indegree가 0인 노드를 하나만 찾아서 그것 하나만 큐에 넣는다(다른 것과 다르게 모두 넣지 않는다.).큐에서 하나를 빼고 그 노드의 진입차수를 1뺀다(-1로 만들어주어 다음 계산시에 영향을 끼치지 않게 한다.).그 노드와 연관된 vertex들의 indegree를 1 뺀다.다시 루프 처음으로 돌아간다.# 이런 식으로 하면 큐에 가장 적은 숫자부터 들어가니 낮은 번호부터 나오게 되어 문제의 조건3을 만족한다. 그런데 이 알고리즘대로 수행하면 큐가 필요 없다...
백준 1516 게임 개발 A를 짓고 B를 지어야 한다면A->B와 같이 모델링 한 뒤,위상정렬을 수행하면서 시간을 계산한다. 여기서 defaultTime은 기본 건설 시간,addTime은 건설을 위해 선행으로 지어야 하는 건물들을 건설하기 위해 기다리는 시간이다. 그래프가 다음과 같다고 하자 A->EF->CB->C->D->E 이럴 경우 E를 짓는 시간은E를 짓는 기본 시간(defaultTime[E])+E의 선행 건물들의 건설 시간중 최대값(addTime[E])이다. addTime[E]는 A의 총 건설 시간과 D의 총 건설시간의 최대값이고, A의 총 건설 시간은 defaultTime[A]이다.한편 D의 총 건설 시간은 C의 총 건설 시간 + D의 기본 건설시간이고,이때 C의 총 건설 시간은 위상정렬을 하면서 C에 접근했을때 (def..
백준 2252 줄세우기 M번 들어오는 학생의 쌍이 다음과 같이 들어온다고 가정하자. (3, 2)(4, 1) 그렇다면, 3은 2보다 앞에 , 4는 1보다 앞에 있어야 한다는 뜻이다.이를 다음과 같은 그래프로 모델링 하자 3->24->1 그 후 이 그래프에 대해 위상정렬을 수행하면 적절한 정답이 도출된다. 한편, 정답이 여러개인 경우 하나만 출력하라고 하였다.이것은 edge가 없는 vertex에 대해 고려를 하지 않아도 되는 장점을 부여한다. 이를테면, 위와 같은 예가 있는데, 사실 학생의 수가 4명이 아니고 10명쯤 된다고 하자. 그렇다면 5번부터 10번까지의 학생은 indegree를 0으로 두고,indegree순으로 위상정렬을 수행할때 5번부터 10번까지의 학생의 indegree는 0이기 때문에 먼저 출력된다.edge가 없는 ..
파이썬과 Tkinter로 게임을 만든 적이 있었다 턴제였는데 그때 상황이 상황이였던 지라 그렇게 만든 소스코드를 들고 나올수가 없었다. 만줄 좀 넘었었고 나름 디자인패턴도 적용하고 쓰래드도 엄청 힘써서 적용하고 그랬는데.. 아깝다
백준 3665 최종순위 풀이는 다음과 같다. 팀을 vertex, 팀의 우열관계를 edge로 하여 방향그래프를 만든다. 이때 주의할 점은 가능한 모든 edge를 다 넣는 것이다. 예를 들어, 4 3 2 1이 주어졌다고 하자(팀4가 1등, 팀1이 4등)그렇다면 방향그래프는 4 -> 34 -> 24 -> 1 3 -> 23 -> 1 2 -> 1 와 같이 6개의 edge로 구성되어 있어야 한다. 그 후 팀의 우선순위가 바뀌는 쌍을 입력받는다.이 쌍은 방향이 바뀌는 edge의 노드 쌍이다. 예를 들어, 위와 같은 그래프일때 (4, 1)(3, 2) 를 입력받았다면 4 -> 34 -> 24 1 와 같은 그래프로 바뀐다 그 후, 이 그래프를 위상정렬을 하여 팀의 등수를 나타내는 것이 이 문제의 풀이이다. From노드로부터 To노드로 연결되어 ..
백준 7469를 재채점했더니 틀렸다.. 전처리로 sort한번 하고 쿼리가 들어올때마다 O(n)을 수행했고 m개의 쿼리가 있었으니 O(nlogn) + O(nm)으로 풀었다. 수행시간 1016ms였는데 재채점되었고, 시간 제한이 1초로 줄어서 오답이 되어부렀다 요게 아니고 persistent segment tree로 푸는 문제인데 맞은거 틀렸다고 하니 힘이 안난다 담에 풀어야징
[openGL][python3] 미니멀 태양계 결과물은 위와 같다. 태양, 지구, 명왕성, 그리고 지구를 회전하는 인공위성이 있다. 인공위성은 공전축이 매 회전마다 조금씩 바뀌고 명왕성은 공전궤도가 타원이다. 왼쪽위부터 태양계 전체를 보는 화면, 태양에서 12시 방향의 우주, 명왕성에서 본 지구, 지구의 한국에서 본 하늘 을 표현하고 있다. constant.py는 전역변수들을 저장하고 있다. 물론 이것도 과제다. main.pyfrom OpenGL.GL import * from OpenGL.GLU import * from OpenGL.GLUT import * from constant import * import math def drawSatellite(): global satelliteRevolveAxisCount global satelliteNowX..
[openGL][python3] 미니멀 당구 파이썬과 openGL을 이용하여 조그마한 당구장을 만들었다 물론 학교 과제다 결과물은 위와 같다. 기본적으로 카메라가 회전을 하고(회전 여부를 키보드로 설정 가능) h를 눌리면 공이 랜덤한 방향으로 움직인다 그러다 당구장 벽면에 부딪치면 튕긴다. 벽면에 부딪치는건 간단하게 방향벡터를 x축 대칭이나 y축 대칭을 하는것으로 해결했다. 또한 마찰에 의해서 속도가 조금씩 느려진다. 이것은 간단하게 속도를 프레임마다 조금씩 늦추는 것으로 구현했다. 아래를 클릭하면 다운 가능하고, floor.jpg와 wall2.jpg는 간단한 텍스쳐이다. 저작권 문제가 있을 수 있기 때문에 업로드를 하지 않으니, 혹시 실행해보고 싶으신 분들은 구글링으로 아무거나 검색해서 다운받으시면 된다. from OpenGL.GL import ..

티스토리툴바