본문 바로가기

분류 전체보기155

[백준] 2023 신기한 소수 : 백트레킹 [골드 5] ✔️ 문제 설명 (펼치기)더보기문제수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.입력첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.출력N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.예제 입력 1 복사4예제 출력 1 복사 23332339239323.. 2024. 10. 4.
[백준] 2294 동전 2 : DP [골드 5] ✔️ 문제 설명 (펼치기)더보기문제n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.입력첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.출력첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.예제 입력 1 복사3 151512예제 출력 1 복사3 ✔️ 문제 풀이배열 dp에 어떤 값을 넣을 것인지는 생각해냈지만, 점화식을 세우지 못 했다....... 2024. 10. 4.
[백준] 14888 연산자 끼워넣기 : 이진탐색 [실버1] ✔️ 문제 설명 (펼치기)더보기문제N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.1+2+3-4×5÷61÷2+3+4-5×61+2÷3×4-5+61÷2×3-4+5+6식의 계.. 2024. 10. 3.
[알고리즘] 이분탐색(Binary Search)이란? ✔️ 이분탐색(이진탐색) 이란?이분탐색이란 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.  처음과 마지막의 중간값을 선택하여, 찾고자 하는 값과 크고 작음을 비교하는 방식을 반복하여 탐색을 진행한다.따라서, 필수조건은 리스트가 오름차순으로 정렬되어야만 한다.  그림으로 이분탐색에 대해서 더 자세히 알아보자 ! 0.길이가 10인 오름차순으로 정렬된 배열이 있다고 하자. 31 이란 특정한 값의 위치를 찾고자한다. 1.먼저 low, high, mid 값 설정한다. low : 최소값의 인덱스 high : 최고값 인덱스mid : 중간값 인덱스2.설정된 중앙값(mid)가 31보다 작으므로, low의 인덱스를 mid+1로 설정하여 우측을 선택한다.(만약 중앙값(mid)이 31보다 큰 경우라면,.. 2024. 10. 2.
[백준] 6603 로또 자바 : 백트레킹 [실버2] ✔️ 문제 설명더보기문제독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.입력입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있.. 2024. 10. 1.
[백준] N과M (1), (2), (3), (4) : 자바 백트레킹 이번 포스팅에서는 백준 N과 M 시리즈에 대해서 얘기해보자 ! 문제 (2),(3),(4)는 (1)에 조건이 추가된 문제들이다. N과 M(1) 알고리즘을 풀어봤다면 (2),(3),(4) 는 비교적 쉽게 풀 수 있다.✔️ N과 M (1) : 15649번arr : 출력할 수열을 담을 배열visited : 중복되지 않은 수를 출력하기 위해 방문 여부를 담을 배열import java.io.BufferedReader;import java.io.IOException;import java.util.StringTokenizer;import java.io.InputStreamReader;public class Main{ static int[] arr; static boolean[] visited; priv.. 2024. 10. 1.

티스토리툴바