https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 난이도 : 실버 2 태그 : 다이나믹 프로그래밍 문제 접근 이 문제는 처음 값부터 특정 값까지 가장 큰 부분을 찾는 문제가 아니라, 값이 최대가 되는 특정 구간을 찾는 문제입니다. 10 -4 3 1 5 6 -35 12 21 -1 예제에서는 12~21 부분이 되겠네요. 1 ~ 1 구간 : 10 1 ~ 2 구간 : 6 1 ~ 3 구간 : 9 1 ~ 4 구간 : 10 1 ~ 5 구간 : 15 1 ~ 6 구간 : ..
https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 난이도 : 실버 2 태그 : 수학, 조합론, 백트래킹, 재귀 설명 주어진 숫자 중 6개를 만드는 모든 조합을 찾는 문제입니다. 숫자 자체가 오름차순으로 주어지니, 입력 배열을 정렬할 필요는 없습니다. 저는 백트래킹(재귀)으로 주워진 숫자들의 모든 경우의 수를 체크하였습니다. 소스코드 import java.util.* var n = 0 lateinit var arr: Array latei..
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 이분 그래프 설명 https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84 이분 그래프 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 2색변 이분 그래프의 예 그래프 이론에서 이분 그래프(二分graph,..
https://www.acmicpc.net/problem/11931 11931번: 수 정렬하기 4 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 난이도 : 실버 5 태그 : 정렬 설명 그동안의 수 정렬하기가 오름차순 이였다면, 이번엔 내림차순 정렬입니다. 이번엔 조금 특이하게 정렬을 해봤는데요. PrioryQueue(우선순위 큐)를 사용해 정렬을 해보았습니다. 우선순위 큐는 말 그대로 원소값에 따라 우선순위를 갖는 큐로써, 꽤 자주 사용되는 자료구조 입니다. 우선순위 큐는 원소가 삽입될때 마다 정렬이 되며, 우선순위 큐를 ..
https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 난이도 : 실버 5 태그 : 정렬 설명 수 정렬하기 두 번째 문제입니다. 1편에서는 직접 삽입정렬을 구현해 풀이해봤다면, 이번엔 자바에서 기본적으로 제공하는 정렬 기능을 사용해 풀어보겠습니다. 소스코드 import java.io.BufferedReader import java.io.InputStreamReader import java.util.Collections fun main() {..
https://www.acmicpc.net/problem/24568 24568번: Cupcake Party A regular box of cupcakes holds 8 cupcakes, while a small box holds 3 cupcakes. There are 28 students in a class and a total of at least 28 cupcakes. Your job is to determine how many cupcakes will be left over if each student gets one cupcake. www.acmicpc.net 난이도 : 브론즈 5 태그 : 수학, 사칙연산 설명 8개 짜리 박스와, 3개 짜리 박스가 있고, 최소 28개의 컵케이크 중, 28명의 학생..
https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 난이도 : 실버 1 태그 : 그래프 이론, 깊이 우선 탐색, 너비 우선 탐색, 브루트포스, 그래프 탐색 설명 비가 오는 양에 따라 잠기는 지역이 있을 수도 있고, 없을 수도 있습니다. 높이는 1이상 100 이하 이므로, 1~100 높이 모두를 대상으로 DFS 혹은 BFS를 진행해 안전구역의 최대 개수를 구하면 됩니다 DFS, BFS 중 어느 것을 사용해도 무방하나, 저는 BFS를 사용하여 풀이하였습니다...
https://www.acmicpc.net/problem/11179 11179번: 2진수 뒤집기 희연이는 스웨덴으로 이사하여 현재 학교를 다니고 있다. 1학년 교육과정은 중국에서 배웠고, 스웨덴과 중국 두 나라의 교육과정은 완전히 다르다. 희연이는 수학을 좋아한다. 하지만 지금은. www.acmicpc.net 난이도 : 브론즈 1 태그 : 수학, 구현, 문자열 설명 숫자 n을 2진수로 만들고, 2진수를 뒤집고, 2진수를 다시 10진수로 만드는 문제입니다. 조금 귀찮고 번거로운 문제로 보일 수 있지만... 자바/코틀린에서 기본적으로 제공하는 메소드를 잘 이용하면 쉽게 풀 수 있습니다. 소스코드 fun main() { print((Integer.toBinaryString(readLine()!!.toInt()..
https://www.acmicpc.net/problem/1004 1004번: 어린 왕자 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주 www.acmicpc.net 난이도 : 실버 3 태그 : 수학, 기하학 설명 진입 / 이탈 횟수를 최소로 하는 경로를 찾아야 합니다. 각 행성계와 시작점, 도착점에 따라 나올 수 있는 경우의 수는 3가지 입니다. 1) 시작, 도착점 모두 행성계 외부에 있을 때 시작, 도착점 모두 행성계 외부에 있을 경우, 해당 행성계는 진입/ 이탈 할 필요가 없습니다. 2) 시작, 도착점 모두 행성계 안쪽에 있을 때 시작점, ..
https://www.acmicpc.net/problem/1212 1212번: 8진수 2진수 첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다. www.acmicpc.net 난이도 : 브론즈 2 태그 : 수학, 구현, 문자열 설명 8진수를 2진수로 바꾸는 문제입니다. 저는 처음에는 Java의 Integer클래스가 기본으로 제공하는 parseInt, toOctalString() 등을 사용해 풀이하려 했는데, 런타임 에러를 받고, 왜 그런지 봤더니 수의 길이가 최대 333,334 자리네요. Long의 자료형에 담기에는 좀 깁니다. 조금 다르게 접근해야 할 것 같습니다. 8진수, 16진수는 사실 컴퓨터공학 계열에서 꽤나 많이 쓰입니다. 2진수와의 변환이 쉽기 때문이죠. 보통 2진..