본문 바로가기

교육 및 책/구름톤 챌린지4

[구름톤 챌린지] 통신망 분석 풀이 과정 먼저, 이 문제를 풀 때 컴포넌트에 포함된 컴퓨터의 번호를 오름차순으로 공백을 두고 출력하라는 것을 보고, TreeSet 자료구조를 이용하면 좋지 않을까 생각했다. 그래서 나는 컴포넌트들을 TreeSet에 담아두고 밀도들을 비교해서 조건에 맞는 TreeSet을 업데이트하는 방식으로 문제를 풀었다. Static 변수 static ArrayList[] A; // 노드와 연결된 노드들의 정보를 담기 위한 배열 static TreeSet treeSet; // 나중에 가장 조건에 적합한 컴포넌트 static boolean visited[]; // 방문한 적이 있는지 확인하는 배열 static int indegree[]; // 아래에서 설명 static int totalOrigin = 0; // 컴포넌트.. 2023. 9. 6.
[구름톤 챌린지] 연합 풀이 과정 처음에는 입력값도 크고 그래서 잠시 유니온파인드인가? 라는 착각을 했었다.. 근데 그러한 문제는 아닌거 같고 그냥 DFS로 풀어보기로 했다. 여기서 핵심은 임의의 두 섬 a와 b에 대해, a번 섬에서 b번 섬으로 직접 이동할 수 있는 다리와 b번 섬에서 a번 섬으로 직접 이동하 룻 있으면, 두 섬은 연합을 결성하는 것이다. 그리고 주의해야할 점으로 a와 b가 연합을 결성하고 b와 c가 여합을 결성했다면 a와 c 역시 위 조건을 만족하지 않더라도 같은 연합에 속해있다고 보는 것이다. 따라서 예제 2번에서 1이 출력되는 것이다. static int count = 0; static boolean visited[]; static ArrayList[] graph; 먼저, static 필드로는 count.. 2023. 9. 4.
[구름톤 챌린지] 작은 노드 풀이 과정 먼저 노드들의 연결 정보를 담기 위해서 ArrayList[] graph를 선언하였다. 그리고 노드 개수만큼 반복하여 해당 인덱스마다 해당 노드가 연결된 정보를 담을 수 있게 new ArrayList();를 통해 할당하였다. 그리고 visited를 통해서는 해당 노드를 방문했을 경우 다음 노드를 방문할 수 있는 용도로 정의하였다. 그 후에 간선의 개수만큼 순회하며 입력된 간선의 정보를 통해 양 노드가 서로 연결되어 있기 때문에 양 노드 모두 해당 인덱스에 대한 ArrayList에 추가하도록 작성했다. 문제 조건 중에 방문할 수 있으면서 번호가 가장 작은 노드로 이동하기 때문에 해당 노드에 연결된 노드들을 오름차순으로 정렬했다. DFS 방식을 사용하여 시작 노드로부터 연결된 노드들을 순회하면 위에.. 2023. 9. 1.
[구름톤 챌린지] 통증 (2) 풀이 과정 먼저, 이 문제는 Dynamic Programming으로 해결할 수 있다. 예를 들어, 3, 4, 5 힐 아이템이 있다고 가정하고, 9라는 통증을 0으로 만들어야하는 상황을 가정해보자. 그 때, 3원의 동전으로 통증 3을 해결하는 방법은 1가지이고, 통증 6을 해결하는 방법은 통증 (6 - 3)을 해결하는 경우의 수 + 1 즉, 2가 된다. 그리고 마지막 통증 9를 해결하기 위해서는 통증 (9 - 3)을 해결하는 방법 + 1이 된다. 다시 4원과 5원을 봤을때 통증 4를 해결하는 방법, 통증 5를 해결하는 방법은 각각 1가지가 되고, 통증 9를 해결하는 방법은 통증 (9 - 4)를 해결하는 방법 + 1(본인) 즉, 2가지가 필요하다. 따라서 정답은 2가 된다. 이를 순서대로 다시 작성해보자. .. 2023. 8. 31.

티스토리툴바