반응형 백준알고리즘68 [백준] 15663번 - N과 M(9) (Java) https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 입력받은 정수배열만 사용해야 함. 2. 중복수열 허용안함 (방문배열 사용함) 3. 순서 바뀌면 다른 조합으로 인정(i = 0 부터 시작) 4. 입력 배열 중 같은 숫자가 있으면 중복 방문은 아니지만 같은 조합이므로 한번만 출력해야 함. - HashSet을 사용해서 중복 문자열이 있으면 머지하지 않고 스킵하도록 구현함. import java.util.Scanner; import java.ut.. 2022. 12. 10. [백준] 15657번 - N과 M(8) (Java) https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 입력받은 정수 배열을 사용해야 한다. 2. 중복방문 허용함. (방문배열 사용X) 2. 순서 바뀌어도 다른 조합인정 안함(i=start로 시작함) import java.util.Scanner; import java.util.Arrays; import java.lang.StringBuilder; public class Main { static int N, M; static int A[].. 2022. 12. 10. [백준] 15656번 - N과 M(7) (Java) https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 입력받은 배열은 DFS 탐색을 하기전에 오름차순으로 먼저 정렬을 한다. 2. 중복방문을 허용하기 때문에 방문배열은 사용하지 않는다. 3. 순서가 바뀌면 다른 조합으로 인식한다. - for (i = 0 to N)으로 해서 새로운 탐색을 할 때 처음부터 다시 시작한다. import java.util.Scanner; import java.util.Arrays; import java.lan.. 2022. 12. 9. [백준] 15655번 - N과 M(6) (Java) https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 입력받은 숫자를 수열로 출력한다. 2. 중복을 허용하지 않는다. - 방문배열을 사용해서 방문하지 않은 수라면 조합에 사용하고 방문처리한다. - level을 하나 높여서 재귀함수 호출한다. - 재귀 호출에서 돌아오면 방문처리를 리셋한다. 3. 순서가 바뀌어도 동일조합으로 인식한다. - for (i = start to N)으로 사용한다. - DFS(i, level+1)을 한다. impo.. 2022. 12. 9. [백준] 15654번 - N과 M(5) (Java) https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 오름차순으로 출력해야 하기 때문에 입력값을 먼저 정렬해야 한다. 2. 숫자 대신 배열 인덱스를 넘겨주고, 배열 A[i]를 저장한다. 3. 중복 조합을 허용하지 않기 때문에 방문배열을 사용한다. - 방문한 숫자가 아니면 값을 조합한다. - 재귀에서 돌아오면 다음 탐색을 위해 방문처리를 초기화한다. import java.util.Scanner; import java.util.Arrays.. 2022. 12. 9. [백준] 15652번 - N과 M(4) (Java) https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 중복 숫자를 허용한다. - 방문배열 사용X 2. 순서가 바뀌어도 동일 조합으로 본다. - for(i=start to N)으로 하고 재귀호출 때 DFS(i, level+1)을 한다. import java.util.Scanner; import java.lang.StringBuilder; public class Main { static int N, M; static int A[]; static .. 2022. 12. 9. [백준] 2343번 - 기타 레슨 (Java) https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 1. 강의 순서가 바뀌면 안된다는 것은 입력 받은 순서대로 디스크에 배치되어야 한다는 것이다. 2. 최소 디스크의 갯수는 M개로 정해져있다. 한 디스크의 최소 용량을 구해야 한다. 1) 완전탐색(DFS) 완전탐색으로 각 디스크에 곡들을 저장해서 그 중 최소값을 구하자. 각 디스크에 저장하는 곡의 수는 for문으로 정해야 하나? DFS로 구현을 하면 어떻게 할 수 있을까? 각 디스크에 저장하는 곡의 수가 .. 2022. 11. 7. [백준] 2665번 - 미로만들기 (Java) https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 검은 방을 변경하는 로직을 어떻게 가져 가야할 지 고민이 되었다. 처음엔 백준 14502 연구소 문제와 비슷한 유형으로 생각하고 아이디어를 생각해보았다. 랜덤하게 검은방 하나씩 변경하고 BFS탐색을 하는 식으로 진행해 봤는데 14502와는 차이점이 그 문제는 문 3개가 되면 탐색을 시작한다는 명확한 재귀탈출 조건이 있었고, 이 문제는 조건 세우기가 애매했다. 검은방의 위치, 갯수... 랜덤하게 진.. 2022. 10. 27. [백준] 2293번 - 동전 1 (Java) https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 동전의 종류가 n개 있다. k원이 되도록 하는 경우의 수를 구해야 한다. 동전의 수는 제한이 없다. 시간제한이 0.5초 이므로 이분탐색 혹은 DP일 가능성이 높다. 배열을 사용해서 동전의 가치를 저장한다. dp[i]는 i원까지 동전의 경우의 수이다. 10원을 표현하기 위해 동전 1, 2, 5를 갖고 있을 때 경우의 수는 점화식 dp[n] = dp[n-1] + dp[n-2] + dp[n-5] impo.. 2022. 10. 14. 이전 1 2 3 4 5 6 7 8 다음 반응형
