반응형 알고리즘 PS113 [백준] 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. [이코테][기출] 05. 볼링공 고르기 A, B 두 사람이 볼링을 치고 있습니다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 합니다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여됩니다. 또한 같은 무게의 공이 여러개 있을 수 있지만, 서로 다른 공으로 간주합니다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재합니다. 문제 N개의 공의 무게가 각각 주어질 때, 두 사람이 볼링공을 고르는 경우의 수를 구하는 프로그램을 작성하세요. 입력 조건 첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 각각 자연수 형태로 주어집니다. (1 2022. 10. 18. 이전 1 2 3 4 5 6 7 8 ··· 13 다음 반응형
