반응형 알고리즘 PS113 [이코테][기출] 04. 만들 수 없는 금액 N개의 동전이 주어질 때 조합으로 만들 수 없는 양의 정수금액 중 최솟값을 구해야 한다. 1. for (i=1 to 1,000,000)으로 정수를 하나씩 증가시킨다. 2. N개의 동전을 순서대로 빼본다. (미리 오름차순 정렬을 해놓고 큰수부터 빼자.) 3. 빼서 0이되면 만들 수 있는 정수이므로 i를 증가시킨다. 4. 빼서 0보다 크면 나머지를 계속 뺀다. 5. 빼서 음수면 다음 수를 뺀다. 6. 다 빼도 수가 남아 있으면 정답 import java.util.Scanner; import java.util.Arrays; // [이코테](그리디) 04. 만들 수 없는 금액 public class Main { static int N; static int A[]; public void InputData() { .. 2022. 10. 18. [이코테][기출] 03. 문자열 뒤집기 모든 숫자를 전부 같게 만드는 것이 목적이다. 따라서 전부 0으로 바꾸는 경우와 전부 1로 바꾸는 경우 중 더 적은 횟수를 가지는 경우를 구하면 된다. 모두 0으로 만드는 경우 모두 1로 만드는 경우 두번째 숫자부터 그 다음 숫자랑 비교를 해서 수가 달라지면 count를 증가시킨다. import java.util.Scanner; // [이코테](그리디) 03. 문자열 뒤집기 public class Main { static int A[]; static int count0 = 0; // 전부 0으로 바꾸는 경우 static int count1 = 0; // 전부 1로 바꾸는 경우 public void InputData() { Scanner sc = new Scanner(System.in); String s .. 2022. 10. 18. [이코테][기출] 02. 곱하기 혹은 더하기 숫자 문자열의 왼쪽부터 오른쪽까지 하나씩 숫자끼리 연산을 해서 가장 큰수를 구하라. 연산은 '+'와 'x' 두개만 사용할 수 있다. 모든 연산은 왼쪽부터 순서대로 이루어진다. 문자열을 정수형 배열에 변환해서 담는다. for문으로 숫자를 하나씩 확인하면서 만약 0이면 다음에 '+', 아니면 'x'를 오게해서 Queue에 저장한다. 다음 for문으로 큐에서 연산자를 하나씩 빼면서 숫자 연산을 해서 ans에 누적시킨다. ----------------------------------------------------------------------------------------------- 첫번째 수는 ans 변수에 저장한다. 그 뒤 숫자부터 for문을 돌리면서 두 수중 하나라도 1이나 0이면 두 수를 '+' .. 2022. 10. 18. [이코테][기출] 01. 모험가 길드 모험가가 N명 있다. 공포도가 X인 모험가는 반드시 X명 이상의 모험가 그룹이 필요하다. 최대 몇명의 모험가 그룹을 만들 수 있는가? 배열 A[N]을 정의해서 공포도를 저장한다. 오름차순으로 정렬한다. for (i = N to 0) A[N]의 공포도만큼 i를 전진하고, count++한다. (10분 걸림) 오름차순으로 정렬하는 것까지는 생각함. 하지만 공포도가 낮은 것부터 확인해서 일단 그룹에 모험가를 포함시키고 그 수와 현재 확인중인 공포도를 비교하는 로직은 생각하지 못함. --------------------------------------------------------------------------------------------- 공포도를 기준으로 오름차순으로 정렬을 한다. 공포도가 낮은 모험가.. 2022. 10. 18. [백준] 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. [백준] 9663번 - N-Queen (Java) https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹의 대표 문제이다. 퀸은 상하좌우 대각선으로 거리제한 없이 움직일 수 있다. 그 동선에 걸리지 않도록 다른 퀸을 N개 배치를 하는 경우의 수를 구하는 문제이다. 각 행별로 놓을 수 있는 위치가 발견되면 재귀호출을 해주고, N개 만큼 배치가 되었다면 count+1을 해준다. * 두가지 문제 1. 재귀호출을 어떤 방식으로 할 것인가 2. 퀸을 놓을 수 있는 위치인지 어떻게 판단할 것인가 * 체스판의 퀸을 일차.. 2022. 10. 13. [백준] 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. [백준] 15649번 - N과M(1) (Java) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 중복되는 수를 제외한 모든 경우의 수를 탐색해야 한다. dfs탐색을 사용한 백트레킹 알고리즘으로 풀자. 백트레킹은 탐색할 노드를 조건문으로 판단하여 유.. 2022. 10. 13. 이전 1 ··· 3 4 5 6 7 8 9 ··· 13 다음 반응형
