본문 바로가기
반응형

실버314

[백준] 1874번 - 스택 수열 (Java)(△) https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 1. 1~n 까지의 자연수를 스택에 집어 넣는다. 2. 그 n까지의 자연수들을 스택에 넣었다 뺐다 하면서 입력값으로 주어진 수열을 만들 수 있는지 확인한다. 3. 오름차순으로 증가시키면서 집어 넣는데 push 때는 '+', pop은 '-'을 출력한다. 불가능하면 'NO'을 출력한다. import java.io.Buf.. 2023. 1. 2.
[백준] 11659번 - 구간 합 구하기 4(Java)(○) https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 1. 구간합 구하는 공식을 사용하면 된다. 2. 입력합수에서 수를 입력 받을 때마다 누적합을 구해서 구간합 배열을 미리 만들자. * 합 배열 공식 S[i] = S[i-1] + A[i] * 구간 합 공식 A[i] ~ A[j] 사이의 합을 구하려면 S[j] - S[i-1] import java.io.BufferedReader; import java.io.InputStreamRe.. 2022. 12. 26.
[백준] 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.
[백준] 15651번 - N과 M(3) (Java) https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 중복숫자와 순열 모두 허용이다. N과 M (1)과 (2)에서 중복을 막기 위해 사용했던 visited[]을 사용 안하면 된다. 다만, 출력을 System.out.print()를 하게 되면 시간초과가 난다. 대신 StringBuilder로 문자열을 계속 머지한다음 마지막 한번 출력했더니 통과했다. import java.util.Scanner; //[백준] 15651번 - N과 M(3) (Java).. 2022. 10. 13.
[백준] 15650번 - N과 M(2) (Java) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N과 M(1)과 비슷한데 중복 순열을 허용하지 않는 점이 차이가 닌다. 이전 문제는 중복 숫자만 방문배열을 통해서 처리를 했는데 이 문제에서는 순서가 달라도 중복이면 표시하면 안된다. 예제를 보면, 4 2 ---- 1 2 1 3 1 4 2 3 2 4 3 4 이런 식으로 1로 시작하는 값이 2로 시작하는 순열을 시작할 때 중복체크 락이 걸려있어야 한다. (1)에서는 재귀 호출에서 돌아오면 중복체크.. 2022. 10. 13.
반응형

티스토리툴바