본문 바로가기
백준 1753 : 최단경로 https://www.acmicpc.net/problem/1753 최단경로 기본문제. 한 정점을 기준으로 다른 정점까지 최단 경로를 구할때 만약 간선의 가중치가 없으면 BFS로 탐색하면 된다.만약 간선의 가중치가 존재하면 기본적으로 다익스트라(Dijkstra) 알고리즘을 사용할 수 있다. 다익스트라 알고리즘은 BFS와 형태가 유사한데while문에 queue 대신 priority_queue를 넣고 너비우선탐색처럼 정점을 순회하며각 정점의 최단경로를 갱신하는 방법이다. (priority_queue를 쓰는 것은 다익스트라 알고리즘을 ElogV 로 최적화 한 것이다.) 각 정점에 연결된 간선의 정보를 넣고 다음 정점을 탐색할때 만약 (다음 정점의 Distance > 현재정점의 Distance + 간선의 가중치).. 더보기
백준 2887 : 행성 터널 https://www.acmicpc.net/problem/2887 행성터널. 최소스패닝트리 문제이다. 간선의 정보를 주는 것이 아니라 정점의 정보(x, y, z 좌표) 를 준다. 따라서 주어진 정점의 정보를 토대로 후보 간선들을 정해야 하는데 정점 N이 100,000 이므로 N^2 연산으로 모든 행성들을 일일이 다 연결시키면 초과가 발생한다. 따라서 간선의 후보를 주어진 조건에 맞게 적절히 설정해야한다.우선 행성과 행성간의 3차원상에서의 거리가 가중치가 아닌x,y,z좌표 중에서 거리가 짧은것 하나만 가중치가 된다. 또한, 모든 행성을 후보로 연결할 필요 없이 x,y,z 좌표중 행성 가까이에 있는 행성들만 후보터널로 사용하면된다. 예시가 다음과 같이 주어졌다 행성번호 1 2 3 4 5 x , y, z 11.. 더보기
백준 1922 : 네트워크 연결 https://www.acmicpc.net/problem/1922 MST(최소스패닝트리)의 가장 기초 문제이다. kruskal 알고리즘 대신 prim 알고리즘을 이용해서 풀어보았다. kruskal 알고리즘은 작은 간선들 부터 차례로 확인해보면서그 간선을 연결하면 cycle이 도는지 확인하는 알고리즘이다.이 때 union-find를 사용하여 재귀적으로 각 정점의 뿌리정점을 정의해주어서로가 연결되어있는지의 여부를 확인한다. 반면, prim 알고리즘은 한 정점을 기준으로 최소 간선을 따라다음 정점를 탐색해나간다. 정점을 하나씩 탐색할때마다새로 탐색한 정점에 연결되어 있던 유효한 간선들을 priority_queue에 넣는다.이는 한정점을 탐색하고 다음 최소 간선은 priority_queue에 넣어놓은 top().. 더보기
백준 10423 : 전기가 부족해 https://www.acmicpc.net/problem/10423 Union-Find를 살짝 응용한 문제.최소 스패닝 트리이되 무조건 모든 노드가 연결이 되는 문제가 아니다. 모든 도시가 연결되어있을 필요는 없고 다만 모든 도시가 발전소와 연결되어 있기만 하면 된다.발전소를 보유하고 있는 도시 가 주어지므로 발전소를 -1로 두었다. 뿌리노드 배열을 -1로 두고 최종적으로 모든 노드의 뿌리노드가 -1이 되면 발전소와 연결이 된 것이다.예시를 참고하자면 1,2,9번 도시가 발전소를 보유하고 있으므로 다음과 같이 설정하고 시작해준다. * vRoot[][1,2,3,4,5,6,7,8,9]-> [-1,-1,3,4,5,6,7,8,-1] ... -> [-1,-1,-1,-1,-1,-1,-1,-1,-1] 이 되면 연결완.. 더보기
백준 1774 : 우주신과의 교감 https://www.acmicpc.net/problem/1774 기본적인 MST 문제이다. 간선이 주어지지 않고 정점의 x,y좌표가 주어졌는데 정점의 개수가 1000개라모든 정점을 연결하는 후보 간선을 뚫어도 N^2연산으로 충분히 가능하다. 단 조금의 차이점은 미리 다리를 놓은 것인데, 이 경우 연결된 간선의UnionFind 에서 merge작업만 수행해주면 된다. 즉 각 노드의 루트노드끼리 병합을 수행해주고 일반적인 Kruskal을 진행하기만하면 된다. 이후 Kruskal을 진행할때 이미 연결한 간선이 나오더라도 이미 root노드가 병합이 되었으므로그냥 무시하고 넘어가기 때문이다. ※ 단, 부동소수점에 관하여..보통 소수점 자리수를 맞출때 setprecision을 사용했다.그러나 이문제에서 setpre.. 더보기
백준 2463 : 비용 https://www.acmicpc.net/problem/2463 쉽지 않은 문제였다... 단 이 과정에서 해당 노드가 속해있는 최상단 뿌리노드 외에 배열을 하나 더 설정해주어야 하는데 그 뿌리노드에 속한 노드들의 개수를저장해주어야 한다. 만약 vRoot[] 가 1,2,3,4,5,6 이면 임의로 groupSize[] 의 변수를 만들고 각 노드그룹이 속한 개수 1,1,1,1,1,1 로 초기화 시켜준다.3과 6이 합병되면 3,6의 vRoot는 3으로 통일이 된다. 그럼 이때 3번노드는 3과 6 두개의 노드를 가지고 잇는 뿌리노드이므로 groupSize[3] = 2가 되어야한다 이는 본래 groupSize[3] 의 값인 1에다가 6의 뿌리노드(6 자신)의 개수 groupSize[6]의 값 1을 합친 2가 되는.. 더보기
cocos-2dx로 다시 도전 추후 cocos-2d로 bms파싱까지 다시 구현해볼 예정.소켓을 통한 1:1과 로그인, 점수산정까지. 더보기
DJ_Technician 자바 리듬게임 만들기 배속 구현 정확한 메트로놈을 구하고나니 마디구현이랑 박자에 맞게 노트를 떨어지게 하는 것이 어렵지 않았다.여기까지 진행하니 배속까지 구하는 것은 그리 어렵지 않았음. 애초에 노트를 떨구는 이동을노트 개개인의 y축을 y += noteSpeed 의 방식으로 계산을하고 프레임에 맞춰서 떨구려고했는데아예잘못된 것이었다. 현재 곡의 진행시각을 기준으로 y축을 계속 갱신하는 방법으로 코드를 짜야한다. 현재곡의 진행시각에 비례해서 noteSpeed 를 곱해주며 떨어지는 방식이때 noteSpeed의 변화에 따라 배속이 바뀌고그에 맞게 노트와 마디들의 y축이 재조정된다. 아직 구현하느라 이것저것 실험해보고 코드가 간결하지 않은데 조만간 정리한번 해야겠다. 더보기

티스토리툴바