최소 신장 트리 •트리(Tree)는 싸이클이 없는 연결 그래프, n개의 정점(vertex)을 가지는 트리는 n-1개의 간선(edge)을 가짐 •신장 트리(Spanning Tree)는 그래프 G(V,E)에서 정점 집합 V를 그대로 두고 간선을 |V|-1개만 남겨 트리가 되도록 만든 것 (|V|=n) •너비 우선 트리와 깊이 우선 트리도 신장 트리 •간선 가중치의 합이 가장 작은 트리를 최소 신장 트리 (Minimum Spanning Tree, MST)라 함 -> 최소 신장 트리를 대표하는 알고리즘으로는 프림 알고리즘과 크루스칼 알고리즘이 존재한다. 프림 알고리즘(Prim’s Algorithm) 프림 알고리즘은 로버트 프림(Robert C. Prim)이 만든 최소 신장 트리 알고리즘이다. 프림 알고리즘은 최..
https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr bfs를 활용한 문제이다. 뿐만 아니라 각 거리의 최솟값도 알아야 하므로 dp의 개념도 필요하다. 핵심 일반 bfs와 다른 점은 이건 이전에 방향이 어디를 향하고 있는지가 중요하다. 직진을 하다가 좌회전이나 우회전을 할 경우 가중치가 달라지기 때문이다. 또한 기본적으로 방문한 곳은 다시 방문하지 않는 것이 일반적이지만, 더욱 작은 값으로 갈 수 있다면 그 값을 들고 다시 방문한다. 정답 코드 im..
https://school.programmers.co.kr/learn/courses/30/lessons/67257 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 각각의 연산자에 우선순위를 부여하여 각각의 우선순위대로 계산했을 때 절댓값이 가장 큰 경우를 찾는 것이다. 핵심 연산자가 +, -, * 3가지이기 때문에 연산자의 우선순위의 경우의 수는 6가지이다. 따라서 다소 빡구현을 통해 풀 수 도 있지만, 조합을 이용하면 더 간결하게 작성할 수 있다. 정답 코드 import java.util.ArrayList; import java.util.Lis..
https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 투 포인터를 사용하는 문제이다. 핵심 모든 종류의 보석을 갖는 경우를 알아야 하고 만약 모든 보석을 가지고 있다면 1칸씩 당기면서 보석을 버리고, 그때도 모든 종류의 보석을 가지고 있는지 체크하며 최소의 길이를 찾아야 한다. 정답 코드 import java.util.Arrays; import java.util.HashMap; import java.util.HashSet; import java.ut..
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net bfs를 사용하는 구현문제이다. 핵심 이 문제는 어떤 식으로 접근할지 충분히 생각하고 시작하면 쉽게 풀 수 있다. 우선 나는 각각 자리마다 bfs를 하여 이동한 곳을 모두 체크하고, 이후에 체크를 하지 않은 곳을 탐색하는 방법을 사용하였다. 또한 한 번에 bfs로 이동한 곳은 좌표를 담아서 changeMap을 통해 자리의 값을 바꿔주었다. 정답 코드 import java.util.A..
https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net bfs 문제이다. 핵심 S에서 D로 도달하는 것이 기본적인 목표이다. 하지만 물이 있는 곳은 건널 수 없고, 물 또한 퍼지기 때문에 이를 잘 고민해야 한다. 정답 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static char[][] map; static int r; st..
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 핵심 (0,0)에서 시작하여 (n-1, n-1)로 갈 때 가장 최소의 코인을 잃은 상태로 가야 한다. 즉 다익스트라를 사용해야 한다. 정답 코드 import java.util.ArrayList; import java.util.List; import java.util.PriorityQueue; import java.util.Scanner; class Main { static Lis..
https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 백트래킹 문제이다. 핵심 입력값 0 이 있는 곳에 1~9까지 가능한 숫자를 대입하면서 스도쿠를 완성시켜야 한다. 전형적인 백트래킹 문제이다. 정답 코드 import java.util.Scanner; class Main { static int[][] map = new int[9][9]; public static void main(String[] args) { Scanner sc = new Scann..
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net DFS + BFS문제이다. 핵심 3개의 벽을 반드시 세워야 한다. 처음에는 특정조건에 기둥을 세워야 한다고 생각하였지만, N의 값이 8 이하인 것을 보고 모든 경우의 수를 적용해도 된다. 이후 바이러스를 퍼트린다. 남은 0의 개수를 찾는다. 정답 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public cla..
https://www.acmicpc.net/problem/1132 1132번: 합 N개의 수가 주어진다. 이 숫자는 모두 자연수이고, 알파벳 A부터 J가 자리수를 대신해서 쓰여 있다. 이 알파벳은 모두 한 자리를 의미한다. 그리고, 각 자리수는 정확하게 알파벳 하나이다. 0으로 www.acmicpc.net 전에 풀었던 문제에서 조건이 하나 추가되었다. 핵심 위의 문제는 만약 ABC + DAB 라면 100A + 10B +C + 100D+ 10A+B로 둘 수 있다. 이를 110A + 100D +11B +C로 둘 수 있다. 따라서 A에 가장 큰 9, D에 8B에 7C에 6을 넣어주면 된다. 단 새로운 조건이 추가되었다. 맨 앞자리가 0이 되면 안 된다. 위의 경우에는 해당되지 않지만, 수가 많아지면 0의 조건..
