소프트웨어개발블로그 소프트웨어개발블로그

알고리즘 모든 경우를 전부 시도해 보아야 한다. 단, Queen을 놓을 수 없는 위치라고 판단되면 중지하고 다음 경우의 수를 시도해볼 수 있다. -> 백트래킹 접근방법 모든 경우의 수를 전부 확인해야 하는 문제이다 2차원 배열이 아닌 1차원 배열로 문제를 풀어내 구현의 난이도를 낮출 수 있다. 4x4 N-Queen 보드에 (0, 0), (1, 3), (2, 1), (3, 2) 위치에 Queen 을 놓는다고 할 때, 1차원 배열로 다음과 같이 표현 가능하다. 1차원 배열 : [0, 3, 1, 2] => 행은 index, 열은 값으로 표현 코드 import java.io.*; import java.util.*; public class Main { private static int N; private stat..

문제 설명 자료구조 큐를 구현하는 문제이다. 접근 방법 - int[] 로 데이터를 저장하도록 구현하였다. - lastIndex 변수를 이용하여 값이 저장된 마지막 index를 추척하도록 구현하였다. 코드 import java.io.*; import java.util.*; public class Main10845 { private static int size; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); size = Integer.parseInt(br.readLine()); Queue queue = new Queue(..

풀이 0 ~ 20 까지 3 개를 더한다고 생각해보자. 1. 0 + ( 0 ~ 20 까지 2개를 더하는 방법의 수 ) 2. 1 + ( 0 ~ 19 까지 2개를 더하는 방법의 수 ) 3. 2 + ( 0 ~ 18 까지 2개를 더하는 방법의 수 ) ... 위 방법을 고안해냈다. DP 배열을 어떻게 표현할지 고민했다. DP[N][K] = 0 ~ N 까지 K 개를 더하는 방법의 수 이제 for 문으로 값을 만들어나가야 하는데, 위 방식에서 분홍색을 선택할 경우 3 중 for 문이 필요할 것이고 연두색 방법을 선택할 경우 2 중 for 문이면 해결이 된다. 코드 @github 에서 확인하기 /** * @site: https://www.acmicpc.net/problem/2225 * @github: https://gi..

풀이 가장 큰 변의 길이를 추가한다고 했으므로 P[N - 1 ] 은 반드시 들어간다. 추가로 더해지는 값은 P[9] 부터 규칙이 형성된다. P[9] = P[4] + P[8] P[10] = P[5] + P[9] P[11] = P[6] + P[10] ... 따라서 점화식은 P[N] = P[N - 5] + P[N - 1] 코드 @github 에서 보기 /** * @site: https://www.acmicpc.net/problem/9461 * @github: https://github.com/7772 * @auth: Landon Park * @date: 2018. 08. 14 */#include using namespace std; int main() { long P[101]; int i, T, N; cin ..

풀이 # 무조건 큰 제곱수를 빼는것이 최소 횟수가 아니다. 67 = 64 + 1 + 1 + 1 --> 4개 67 = 36 + 25 + 4 --> 3개 즉, 67 보다 작은 제곱근들 (1, 4, 9, 16, 25, 36, 49, 64) 에 대하여 1. 67 - 1 로 시작하는 경우2. 67 - 4 로 시작하는 경우3. 67 - 9 로 시작하는 경우...8. 67 - 64 로 시작하는 경우 를 모두 알아보아야 한다. "DP[N] = N 의 최소 제곱수의 합의 개수" 라고 한다면 DP 배열이 1 ~ N 까지 채워져 나가는 반복문 안에서 ---> i1 ~ (i*i) 의 제곱수를 빼나가며 최소값을 찾는 과정이 들어가야 한다. ---> j 점화식은 for (i = 1; i > N; for (i = 1; i

풀이 3. 마지막 도착 계단은 반드시 밟아야 한다. 이 규칙이 가장 중요하다. ... 15 25 10 20 or ... 25 10 20 이 두가지 중 하나는 무조건 선택이 될 것이다. 즉, 다음과 같이 요약될 수 있다. 1. 마지막 직전을 선택한 경우2. 마지막 -2 번째를 선택한 경우 결과적으로 이 두값의 크기를 비교하여 큰 값에 마지막 숫자를 더해주면 된다. 점화식은 DP[N] = max( DP[N-3] + arr[N - 1] , DP[N - 2] ) + arr[N] 이 된다. 코드 @github 에서 보기 /** * @site: https://www.acmicpc.net/problem/2579 * @github: https://github.com/7772 * @auth: Landon Park * @..

풀이 연속합 문제는 3중 for 문을 구성해야 풀 수 있다. 기억할 연산값을 저장하는 DP 배열에 10 10 + -4 10 + -4 + 3 ... -4 -4 + 3 -4 + 3 + 1 ... 12 12 + 21 12 + 21 + -1 이렇게 모든 값을 비교해보려면 3중 for 문이 필요했다.. 그러나 1 개의 생각만 하면 하나의 for 문으로 문제를 해결할 수 있다. 값을 더해나가는 sum 값이 음수이면 초기화 시킨다. 이전 까지 아무리 큰 값이 나왔더라도 다음에 나올 값이 음수라면 지금까지 더한 값은 최대값이 될 수 없기 때문이다. 해답을 보고나니 너무나 당연한 이론인데 왜 생각해내지 못했을까 싶었다. 코드 @github 에서 보기 /** * @site: https://www.acmicpc.net/pr..

풀이 증가하는 부분수열 문제를 2 번 이용해서 해결할 수 있다. 첫번째는 왼쪽에서 오른쪽으로 진행하면서 증가하는 부분수열을 찾는다. 두번째는 오른쪽에서 왼쪽으로 진행하면서 증가하는 부분수열을 찾는다. 위와 같이 계산이 되는 것을 볼 수 있다. 여기서 최대값 8 이 정답이라고 생각할 수 있다. 그러나 잘 생각해보면 최대값 8 은 1 2 3 4 5 의 증가 부분과 5 2 1 의 감소부분의 합으로 이루어져있다. 여기서 5 가 중복되기 때문에 최대값에서 - 1 을 해주어야 올바른 값이 나온다. 코드 @github 에서 보기 /** * @site: https://www.acmicpc.net/problem/11054 * @github: https://github.com/7772 * @auth: Landon Park..