스파르타 알고리즘 트랙 문제(백준) (18) 썸네일형 리스트형 스파르타 알고리즘 트랙 문제 6일차 - 3 #11047 동전 0 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 해결 과정 DFS를 구현한 후 그리디 서치를 해야겠다는 생각을 했으나, 문제의 동전 조건이 1부터 시작하여 배수로 증가하는 배열이기에 금액이 큰 동전부터 고려한다면 큰 문제없이 해결할 수 있는 문제가 되었다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int .. 스파르타 알고리즘 트랙 문제 6일차 - 2 #1037 약수 문제 양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오. 해결 과정 1과 자기 자신을 제외한 모든 약수가 주어질 때, N을 구하는 것은 모든 약수 집합 중, 최댓값과 최솟값을 곱하면 간단히 값을 구할 수 있다. 인수분해 시 소수의 제곱 형태의 정수 N은 1과 자기 자신을 제외한 모든 약수의 갯수는 1개이기에 해당 수를 제곱하여야 하나, 최댓값과 최솟값이 동일한 약수 집합으로 생각하면 위 과정과 동일함을 알 수 있다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args).. 스파르타 알고리즘 트랙 문제 6일차 - 1 #1927 최소 힙 문제 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 해결 과정 최대 힙 문제에서 힙의 정렬 순서를 값이 가장 작을 때로 변경한 것과 동일하다. 최대 힙 문제와 동일하게 Priority Queue를 사용하되, reverseOrder 구문만 제거해 정순으로 정렬되게 하였다. 그 외에는 최대 힙 문제와 동일한 알고리즘을 구현하였다. import java.io.*; import java.util.*; public class Main { public static void main(String[] ar.. 스파르타 알고리즘 트랙 문제 5일차 - 3 #4949 균형잡힌 세상 문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 해결 과정 주어진 주제는 Stack이었으나, 동일하게 약간의 수학적 계산만 들어간다면 List를 사용하는 것이 더욱 빠를 것으로 생각하였다. 1부터 순서대로 N까지의 데이터가 들어있는 List 배열을 생성한다. .. 스파르타 알고리즘 트랙 문제 5일차 - 2 #11279 최대 힙 문제 널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 해결 과정 힙 자료구조를 구현하여 해결하는 문제이다. 힙은 이진 트리 구조로 형성되어 부모 노드의 값이 자식 노드의 값보다 무조건 큰, 혹은 작은 형태의 자료구조이다. 따라서 힙을 구현한 후, 그 자료구조에 1의 경우는 값을 집어넣는 메소드를, 2의 경우는 값을 빼는 메소드를 작성하면 될 것으로 보인다. Java에서는 PriorityQueue라는 이미 힙 형태로 만들어진 자료구조 클래스가 존재하여 이를 사용하여 문제를 해결해 보았다. impo.. 스파르타 알고리즘 트랙 문제 5일차 - 1 #4949 균형잡힌 세상 문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다. 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다. 짝을 이루는 두 괄호가 있을 때, 그 사이에 있.. 스파르타 알고리즘 트랙 문제 4일차 - 3 #9012 괄호 문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문자열.. 스파르타 알고리즘 트랙 문제 4일차 - 1 #1874 스택 수열 문제 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라. 해결 과정 수열과 Stack의 관계를 비교할 수 있다면,.. 이전 1 2 3 다음