부분집합 재귀함수 순열 구하기(JAVA) 순열(Permutation) n개의 원소 중 r개의 원소를 꺼내는 경우의 수 순서가 유효하기 때문에 원소의 중복을 허용함(조합은 순서가 유효하지 않아 중복 불허) 경우의 수 :n!/(n-r)!의 갯수를 가진다. 표기법 nPr 순서가 있도록 모든 경우의 수를 뽑아내는 것을 순열이라고 합니다. 부분집합 중{1,2,3}과 {3,2,1}은 엄연히 다른 것으로 인식합니다. 예를 들어 {1,2,3}중 2개를 조합해 만들 수 있는 모든 숫자를 구하라고 한다면 순열을 이용. 두 숫자를 붙이는 것은 순서에 따라 다르니깐요. 전체코드 import java.util.ArrayList; import java.util.List; import java.util.Scanner; class ..

백준 1932번 DP 문제 문제 사이트 해설 제일 위에서 부터 제일 아래까지 내려가면서 자기 자식을 더해서 가장 큰 값을 구하는 문제이다. i가 1->3으로 갈 떄까지 최고 합을 구하면 되는 것입니다. 경우의 수를 보게 되면 ABD / ABE / ACE / ACF 이렇게 4가지가 있다. ABF가 안되는 이유는 당연히 문제에 대각선 왼/오른쪽(자식) 중 선택하라고 했으므로 F는 C의 자식이지 B의 자식이 아니기 떄문에 안된다. 간략하게 배열에 맞게 숫자를 넣어봤다. 그럼 이제 하나씩 더해 보도록 하겠다. 빨강 테두리 부분과 파랑 테두리 부분을 먼저 보면 이 부분의 합을 구하는 방법은 딱 하나 밖에 없다. 예를 들어 (3,1) 까지 더한 값을 구하기 위해서 (3,1) + (1,1) +.(2,1) 이렇게 밖에..

백준 2579 동적 계획법 문제 문제는 위에 링크와 같다. 설명 문제를 간단하게 설명하면 각 계단이 있는데 그 계단에 값이 있고 연속해서 계단을 3번을 건널 수 없고 최대값을 구하는 문제이다. DP[N]을 N개의 계단을 오르기 규칙에 의해 얻은 최대 점수라고 가정하자. N번째 계단은 무조건 밟아야 하기 때문에 N번째 계단이 1번 연속인 경우! N번째 계단이 2번연속인 경우! 이 2가지 경우를 나누어서 생각해 보자. 이제 중요한 3번째 계단이다. (첫번째 경우) N번째 계단이 1번 연속인 경우 N-1번째 계단은 필요 없고, N-2번째 계단의 총점을 합쳐야 합니다. DP[N] = DP[N-2] + A[N] (두 번째 경우) N번째 계단이 2번 연속인 경우 N-1번째 계단은 밟아야 하고, N-2번째 계단은 무..

백준 9663 N-Queen 문제 백트랙킹으로 유명한 n-queen문제이다. 간략하게 문제는 이렇다. N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 위 그림은 체스를 놓을 수 있는 방법중 하나이다. 체스의 퀸은 양 옆, 아래 ,대각선을 공격할 수 있기 때문에 조건으로 양 옆,아래,대각선 이렇게 있으면 안된다. 처음에 과연 어떻게 체스의 위치를 알 수 있을까 생각을 하다가 좌표를 그려보았다. 그리고 각 행에 한 개의 체스만 놓을 수 있다는 것을 알게 되었다. 그러면 각 행에 체스 퀸을 놓고 DFS형식으로 문제를 풀면 되겠다고 생각을 하였고 체스 퀸을 하나 놓을 때 마다 위치의 조..

프로그래머스 더 맵게 문제 문제는 프로그래머스에서 출제된 더 맵게 문제이다. 문제상황 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요. 제한사항 scoville의 길이는 2 이상 1,000,000 이하입니다. K는 0 이상 1,000,000,000 이하입니다. scoville의 원소는 각각 0 이상 1,000,000 이하입니다...