본문 바로가기
반응형

분류 전체보기123

백준 1697. 숨바꼭질 🅰 백준 1697. 숨바꼭질 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net ✏️ 문제 풀이 큐를 이용하여 너비우선탐색을 해주었다. check변수를 이용하여 방문체크를 해서 방문한 곳은 다시 방문하지 못하도록 하였고, depth변수를 이용하여 몇번만에 동생을 찾았는지를 알기위해 선언하였다. 탐색을 하다가 동생(K)를 만나게 되면 반복문을 종료하도록 하였다. ✏️ 소스코드 package bruteforce; import java.util.*; import java.io.*; publi.. 2021. 8. 26.
백준 1182. 부분수열의 합 🅰 백준 1182. 부분수열의 합 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net ✏️ 문제 풀이 부분수열의 합을 구하는 문제이다. 일단 부분집합을 구하기 위해 subset 함수를 구현하였고, 부분집합이 완성될 때 마다 부분집합의 합을 계산하여 S의 값과 같으면 cnt++를 해주었다. 부분집합을 구하면 공집합일때도 있기 때문에 공집합일 때에는 카운트 해주지 않기 위해 none을 카운트 해줘서 공집합일때를 예외처리 해주었다. ✏️ 소스코드 package bruteforce; .. 2021. 8. 26.
백준 6603. 로또 🅰 백준 6603. 로또 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net ✏️ 문제 풀이 재귀를 이용한 조합을 이용하여 풀었다. ✏️ 소스코드 package bruteforce; import java.util.*; import java.io.*; public class Main_실버2_6603_손은성 { static int R = 6; static int N, ans[] = new int[R]; static StringBuilder sb = new StringBuilder(); public stat.. 2021. 8. 26.
백준 10971. 외판원 순회 2 🅰 백준 10971. 외판원 순회 2 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net ✏️ 문제 풀이 순열을 이용하여 모든 출발점에서 돌 수 있는 경우의 수를 뽑아낸 다음 비용을 계산해주었다. 순열이 완성되면 비용행렬을 탐색하면서 가는 길이 없으면 비용들을 다 더했더라도 boolean변수를 이용하여 최소값으로 비교하지 못하게 하였다. ✏️ 소스코드 package bruteforce; import java.util.*; import java.io.*; /* * 외판원 .. 2021. 8. 26.
백준 10819. 차이를 최대로 🅰 백준 10819. 차이를 최대로 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net ✏️ 문제 풀이 백트래킹을 사용하지 않고 순열을 이용하여 모든 경우의 수에 따라 값을 구해준 다음에 Math.max 를 이용하여 차이가 최대값인 값을 지정해주었다. ✏️ 소스코드 package bruteforce; import java.util.*; import java.io.*; public class Main_실버2_10819_손은성 { public static void main(String[] args) throws Exception{ .. 2021. 8. 26.
백준 9095. 1, 2, 3 더하기 🅰 백준 9095. 1, 2, 3 더하기 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net ✏️ 문제 풀이 알고리즘 분류에 DP라고 되어있는데 재귀함수를 이용하여서 풀었다. 들어오는 n값에 -1,-2,-3을 한 값을 재귀로 돌려서 n이 0이되면 cnt++을 해줘서 케이스 수를 더해준 다음 재귀 종료 후 모든 케이스를 출력해주었다. ✏️ 소스코드 package bruteforce; import java.io.*; public class Main_실버3_9095_손은성 { static int cnt; public static void main(String[] args) throws Exception{ Buffer.. 2021. 8. 26.
백준 10974. 모든 순열 🅰 백준 10974. 모든 순열 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net ✏️ 문제 풀이 모든 순열은 다음순열이랑 똑같은 문제이다. 다만 들어오는 데이터를 1부터 N까지 따로 저장을 해줘서 np를 수행해 주면 된다. ✏️ 소스코드 package bruteforce; import java.io.*; public class Main_실버3_10974_손은성 { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); St.. 2021. 8. 26.
백준 10973. 이전순열 🅰 백준 10973. 이전순열 10973번: 이전 순열 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net ✏️ 문제 풀이 이전순열은 다음순열과 마찬가지로 np를 이용해서 풀었다. 하지만 내림차순으로 정렬되어야 하기 때문에 앞에서 부터 탐색을 하기 위해 np함수 내 데이터의 부등호만 변경해주었다. ✏️ 소스코드 package bruteforce; import java.io.*; import java.util.*; public class Main_실버3_10973_손은성 { public static void main(String[] args) throws Exception{ BufferedRead.. 2021. 8. 26.
백준 10972. 다음 순열 🅰 백준 10972. 다음 순열 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net ✏️ 문제 풀이 자바에는 없는 next-permutation을 구현하는 문제이다. 먼저 입력 배열을 오름차순으로 정렬하는 것이 중요하다. 정렬 후 np함수를 통해 데이터를 출력한다. np에 대한 내용은 따로 정리해서 올리겠다. ✏️ 소스코드 package bruteforce; import java.util.*; import java.io.*; public class Main_실버3_10972_손은성 { public static void main(String[] args) throws Exce.. 2021. 8. 26.

티스토리툴바