출처 : https://www.acmicpc.net/problem/2933 "조건을 잘 읽어보자. 슈발" 이 문제때문에 하루를 다날렸다. 문제를 이해하는데만 해도 굉장히 오랜 시간이 걸렸다. 클러스터가 뭔데... 땅에 붙어 있는 미네랄에서 막대로 인해 부셔져 공중에 둥둥 떠 있는 미네랄 조각을 클러스터라 한다. 얼음 덩어리는 상,하,좌,우가 인접한 얼음의 집합이다. 그냥 막대를 던져 얼음 덩어리를 깼을 때, 생기는 각각의 얼음덩어리 중 상,하,좌,우가 지면과 맞닿아 있지 않는 얼음덩어리를 공중에 있다고 한다. 이렇게 공중에 있는 얼음덩어리는 중력에 의해 모양을 유지하며 아래로 떨어지게 되는데, 지면에 닿거나, 다른 얼음 덩어리를 만날 때 까지 떨어진다. (단, 떨어지는 얼음의 모양은 변하지 않는다. 즉,..
출처 : https://www.acmicpc.net/problem/1953 "연결 요소들을 탐색해! 아이디어가 필요한 BFS" 해당 문제와 같이 이분( 팀을 나누거나, 선택/비선택 등 ) 하는 문제는 주로 비트마스크를 사용했다. 하지만 비트마스크는 비트 연산이므로 N이 32자리를 넘어서는 수에 대해서는 사용하지 못한다. 해당 문제의 경우 n이 최대 100이므로 비트마스크를 사용하지 못한다. 그렇다면 탐색을 통해 팀을 나누어 주어야 한다. 팀이 될 수 있는 경우로 모든 경로를 탐색한다면 오래 걸릴 듯 했다. 따라서 1번 노드를 시작으로 같은 팀이 절대 될 수 없는 것들을 먼저 분류 했다. 풀다 보니, 연결 요소의 개수를 탐색하는 것과 비슷했다. 1번 노드 부터 서로 싫어하는 노드들의 연결 요소를 따라 탐색..
출처 : https://www.acmicpc.net/problem/1613 "플로이드와샬!" 사건의 전후 관계에 대해 묻고 있다. 플로이드와샬은 음수 가중치를 계산할 수 있다는 점이 다익스트라와 다르다. 문제에서 친절히 -1,0,1 과 같이 힌트를 주었다. 주어지는 사건 x,y 에 대해 1 과 -1 을 부여한다. x y 순으로 주어진다면 아래와 같다. map[x][y] = 1 ;map[y][x] = -1; 그렇 다면 x y 두 사건의 관계를 x < y 라고 하자. 이렇게 되면 이제 우리가 찾아야 할 것은 x < (...) < y 의 관계를 만족하는 다른 사건들과의 관계 이다.이를 아래와 같이 계산한다. 가장 바깥쪽 for문이 우리가 찾을 (...) 에 해당한다. for (int a = 1; a j 라면,..
- Total
- Today
- Yesterday