문제 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Stri..
문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 코드 bfs import java.io.*; import java.util.*; public class Main { static ArrayList arr []; static boolean check[]; static int result; public static void main(String[] args) throws Exception { BufferedReader br = new Buffered..
문제 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 스도쿠는 가로, 세로, 3*3 내 사각형에서 같은 숫자가 있으면 안된다. 따라서 세가지를 체크해야 된다. 1. 가로 for(int i=0;i
문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 문자들의 조합으로 단어를 만들면 된다. 따라서 백트레킹을 이용한다. 오름차순으로 단어를 만들어야 되기 때문에 백트레킹 전에 오름차순으로 정렬한다. 그리고 그 전의 문자와 현재 문자를 비교하여 오름차순이면 백트레킹을 시행하고 아니면 그 다음 문자로 넘어간다. 이때 단어안에 모음은 최소 1개, 자음은 최소 2개가 필요하다. 따라서, 전역변수 2개를 선언한 다음 모음일 경우 변수 1개의 값을 증가..
문제 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 간단하지만 간단하지 않은 백트레킹 문제였다. 문제 풀이는 간단하다. 1. 'a', 'n', 't', 'i', 'c' 먼저 방문 체크한다. 2. 백트레킹 하면서 'a', 'n', 't', 'i', 'c'를 제외한 문자에 대해 조합을 만든다. 3. 만들어진 문자열에 대해 단어의 문자가 있는지 체크한다. 이때, 백트레킹 할때 가지치기가 필요하다. 알파벳 순서대로 문자를 확인하기 때문에..
문제 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 누적합과 백트레킹을 이용한 문제이다. visit 배열의 size는 26으로 나타나게 하므로써 visit배열의 인덱스가 알파벳이 된다. visit 배열을 누적합으로 나타낸다. 이렇게 하므로써 각 문자마다 다른 값을 갖게된다. 예를들어, ACDEB라고 한다면 visit배열은 다음과 같게 될것이다. 1 2 3 4 5 A는 1, B는 2, C는 3, D는 4, E는 5를 갖게 될것이다. ..
문제 https://www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 풀이 문제에서 규칙은 다음과 같았다. 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다. 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다. 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 ..
문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 풀이 서로소 집합을 사용한다. 서로소 집합은 공집합인 집합(서로소) 들의 정보를 확인(find)하고 조작(union)할수 있는 자료구조다. union 연산은 두 원소 a, b에 대하여 두 원소가 속한 집합을 하나로 합치는 집합이다. find 연산은 a가 속한 집합의 대표번호를 반환한다. 따라서 union 연산을 할때에는 두 원소의 대표번호를 변경하면 된다..
문제 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 풀이 각 index 까지의 합을 가지고 있는 dp 배열을 구한다. 예를들어, 2 3 4 5 로 입력 받았다고 한다면 dp[1] = 2, dp[2] = 5, dp[3] = 9, dp[4] = 14가 된다. 1~3까지를 구하고 싶다면 dp[3] - dp[0] 을 하면 된다. 코드 import java.io.*; import java.util.*; public class M..
문제 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 풀이 주어진 시작점에서 다른 모든 정점으로의 최단경로인데 가중치가 양수이므로 다익스트라 알고리즘을 사용한다. 다익스트라 알고리즘을 사용할때에는 PrirorityQueue를 이용한다. 코드 import java.io.*; import java.util.*; public class Main { static class Info implements Compara..
