https://www.acmicpc.net/problem/2404 2404번: 단위 분수로 분할 첫째 줄에 양의 정수 p, q, a, n이 입력된다. (1 ≤ p, q ≤ 800, 1 ≤ a ≤ 12000, 1 ≤ n ≤ 7) www.acmicpc.net 풀이 좀 많이 어려웠다. 시간 제한이나 범위로 봐서는 완탐으로 돌리는게 맞는데 어딜 어떻게 잡고 돌려야 할지 감이 오지 않았다. 이것만 떠올리면 문제에 접근하는데 감이 확 온다. a/b=c/d ac=bd 즉 a/b를 주어진 p/q라고 생각하고, c/d를 만들어진 단위 분수라고 생각했을 때 p*d==q*c를 만족하는 경우를 세면 되는 것이다. 코드 package backtracking; import java.util.*; import java.io.*; ..
https://www.acmicpc.net/problem/25421 25421번: 조건에 맞는 정수의 개수 2개의 자릿수를 갖고 첫 번째 자리의 숫자와 두 번째 자리의 숫자의 차이가 2보다 작거나 같은 양의 정수 11, 12, 13, 21, 22, 23, 24, 31, 32, ... , 97, 98, 99가 A에 해당된다. 따라서 정답은 39이다. www.acmicpc.net 문제 분석 & 풀이 간단한 DP문제다. 많이 가볼 필요 없이 n=3까지만 손으로 세보면 규칙을 쉽게 파악할 수 있다. 점화식은 dp[n][i] = dp[n-1][i-2] + dp[n-1][i-1] + dp[n-1][i] + dp[n-1][i+1] + dp[n-1][i+2]. 1, 2, 8, 9일 때 예외처리만 신경쓰면 된다. 코드 ..
https://school.programmers.co.kr/learn/courses/30/lessons/131127?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 읽고 든 생각은 그냥 문제가 제시한대로 따라가면 풀면 될 것 같은데? 라는 생각이 들었다. 첫 번째 풀이 단순하게 discount 배열의 0번째부터 discount.length - 10까지 반복문을 돌면서 10개씩 자르며 원하는 수량을 다 채웠는지 체크한다. import java.util.*; class Solution { private boolean canReg..
[여러 가지 정렬 1]에 나오는 정렬들 보다는 조금 복잡하지만 더 빠른, 배열을 정렬(오름차순)하는 방법을 알아보자. 1. Merge Sort 배열을 분할하여 각각 정렬하고, 정렬된 결과를 합치는 분할정복(Divide and Qunquer) 방식 주어진 배열을 둘로 나누어 각각 정렬하고, 이를 하나로 합친다. -> 둘로 나뉜 부분 배열은 어떻게 정렬할까? 둘로 나뉜 배열을 또 둘로 나누어 각각을 정렬하고, 이를 하나로 합친다. -> 또 나뉜 배열을 둘로 나누고, ... 길이가 N인 배열을 정렬하기 위해서는 길이가 N/2인 배열을 정렬해야 하고, 또 그 배열을 정렬하기 위해서는 길이가 N/4인 배열을 정렬해야 하고, ... , 결국 길이가 1인 배열을 정렬해야 하는데, 길이가 1인 배열을 정렬하는 것은 너..
배열을 정렬(오름차순)할 수 있는 여러 가지 방법에 대해서 알아보자. 1. Selection Sort 주어진 배열에서 가장 작은 데이터를 선택하여 앞으로 보내는 정렬 첫 번째 과정에서 가장 작은 데이터를 찾아 배열의 첫 번째 자리에 넣고, 두 번째 과정에서 그 다음 작은 데이터를 찾아 두 번째 자리에 넣고, ... n-1자리까지 반복한다. n개의 데이터에서 가장 작은 데이터를 찾고, n-1개의 데이터에서 가장 작은 데이터를 찾고, 그 다음은 n-2개, n-3개, ... 이렇게 이어지기 때문에 O(N^2)의 시간복잡도를 가진다. public void selectionSort(int[] arr) { for (int i = 0; i < arr.length; i++) { for (int j = i + 1; j ..
https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 문제 분석 수열 N이 주어졌을 때, 수열의 두 수를 묶어서 (순서는 상관없음) 묶은 수들의 합이 최대가 되도록 하는 문제. 묶은 두 수는 곱해지며, 수는 한 번만 묶을 수 있고, 묶지 않을 수도 있다. 예전에 풀었던 문제인데 뭔가 greedy 하지 못하다는 생각이 들어 백준에서 더 깔끔하게 푸신 분들이 없나 참고하였다. 내 코드 import java.io.BufferedReader; import..
