두부의 코딩일기

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 위 문제는 최소 스패닝 트리 문제로 해결 방법은 프림, 크루스칼 두 가지가 존재한다. 필자는 두 가지 방법에 대해서 잘 모르는 상태였고, 해당 알고리즘 해결법을 먼저 숙지한 다음에 다시 문제에 접근했다. 우선, 크루스칼을 이용해서 문제를 해결했으며 해당 내용을 모른다면 아래를 참고하는 걸 추천한다. 자바 최소 비용 신장 트리(MST), 크루스칼 ..

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 위 문제는 dfs와 bfs를 이용해서 풀 수 있는 것처럼 보이지만 dp를 이용하지않으면 시간초과가 발생한다. 메모제이션, 즉 dp를 이용해서 실행시간을 단축시켜야한다. 출발지가 정확하게 명시되어 있지 않은 문제이기 때문에 bfs를 이용해야하고, 메모제이션을 이용해서 해당 과정에서의 시간을 단축시키면 된다. 우선 2차원 배열을 생성하고 임의의 출발지에서 상하좌우로 움직이면서 최대한 ..

https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 풀이 단순한 정렬 문제로 여러 가지 방법으로 해결할 수 있다. 필자는 배열을 이용하지않고 클래스 객체를 만들어서 해결했다. public static class Person implements Comparable { int age; String name; public Person (int age, String name) { this.age = age; this.name = name; } public in..

안녕하세요. 두부입니다. 이번에 키크론 K8 pro 키보드를 선물받고 데스크탑 PC에서 블루투스 기능으로 사용해보려하는데 도저히 연결이 안되더라구요. 이유는 제 메인보드에서 블루투스 기능을 지원하지않기 때문인데요. 그렇다면 연결하는 방법이 없을까요? 아닙니다!! 집 앞에서 흔하게 볼 수 있는 다이소에서 쉽게 구매할 수 있는 '동글'이를 구매하시면 되는데요. 다이소에서 5,000원에 구매하실 수 있습니다. Bluetooth 연결 방법 동글이를 구매하셨다면 어떻게 사용하는지가 궁금하실텐데요. 방법은 매우 간단합니다. 1. '동글'이를 본체 usb 포트에 꽂는다. 2. [시작] - 톱니바퀴 아이콘을 클릭해서 설정으로 들어와서 장치를 클릭한다. 3. Bluetooth 또는 기타 장치 추가를 클릭한다. 동글이를 ..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 인접해있는 땅과의 인구수 차이가 L과 R 사이이면 국경선이 열리고 연합 내의 동일한 인구수를 가진다. 위 문제는 bfs, dfs 아무거나 사용해도 무관하기 때문에 본인이 원하는 걸 사용하면 된다. 필자는 bfs를 이용해서 문제를 풀었다. while (true) { visited = new boolean[N][N]; // 방문 유부 isMove = false; // 변경 유무 f..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 전형적인 다익스트라 알고리즘 문제이다. dp와 bfs를 이용해서 한 노드에서 모든 노드로 가는 최단거리를 구할 수 있다. 다익스트라에 대해서 잘 모르면 아래 링크를 먼저 보는 걸 추천한다. 자바 다익스트라(Dijkstra) 알고리즘 정의 및 작동 원리 다익스트라 알고리즘 (Dijkstra) 정의 음의 가중치가 없는 그래프의 한 노드에서 각 모든 노드까지의..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 이번 문제는 bfs와 dfs를 동시에 사용하는 문제로 3개의 벽을 세워서 바이러스로 부터 안전한 구역을 최대한 넓게 만들어야한다. 우선 임의로 중복되지 않은 3개의 벽을 계속 세워야하므로 dfs를 이용한다. 벽을 세우고, 다시 복구를 반복하면서 벽 3개가 완성되면 bfs를 돌리면 된다. public static void dfs(int wall) { if (wall == 3) { bfs(); // 벽이 3..

https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이 이번 문제는 최소 비용 신장 트리 (MST) 유형의 문제이다. 해결 방법으로는 크루스칼 알고리즘과 프림 알고리즘이 있다. 필자는 사실 크루스칼 알고리즘을 처음 들어본다. 그래서 한 번 정리해봤다. 자바 최소 비용 신장 트리(MST), 크루스칼 알고리즘(Kruskal Algorithm) 정의 크루스칼 알고리즘 (Kruskal Algorithm) 정의 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘으로 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘 중 하나이다...

크루스칼 알고리즘 (Kruskal Algorithm) 정의 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘으로 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘 중 하나이다. 최소 비용 신장 트리 (Minimum Spanning Tree) 는 무엇일까? 정점 N개를 가지는 그래프에서 (N-1)개의 간선을 연결해야한다. 연결한 간선의 가중치 합이 가장 최소가 되는 그래프 모든 정점이 연결되야하지만 싸이클이 되면 안된다. A : 간선이 5개로 N-1개를 가져야하는 신장 트리 법칙에 어긋나고, [1, 3, 4] 정점에서 순환 싸이클을 돌고 있으므로 연결 그래프이다. B : 간선이 4개로 N-1개를 가져야하는 신장 트리 법칙에 어긋나지않지만 가중치 값 (2 + 5+ 7 + 6) 으로 최소 비..

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 이번 문제는 랜선 자르기, 숫자 카드 등과 같은 이분 탐색 알고리즘 문제이다. 이분 탐색에 대해서 잘 모르거나 이해가 가지 않는다면 위 문제를 먼저 풀어보는 걸 추천한다. 이 문제의 목표는 N개의 집이 주어졌을 때 C개의 공유기를 집 간격을 최대한 띄워서 설치하는 것이다. 그렇다면 이분 탐색을 어떻게 적용시켜야할까? 이분 탐색에서 중요한 건..