백준3 백준 10974번 모든 순열 (java) 1. 문제 2. 코드 N이 주어졌을 때 구할 수 있는 모든 순열을 사전순으로 출력하는 문제이다. DFS 알고리즘을 순열을 구했다. 1. 필요한 배열 : 데이터를 담을 배열과 방문했는지 안했는지를 기록할 visited 배열 2개를 만든다. 2. 첫자리에 올 수를 반복문을 통해 하나씩 넣는다. 사전순이으로 출력해야하니까 1부터 쭉 넣어준다. 3. 배열에 넣은 수는 visited[] 배열을 통해 방문 했음을 표시한다. 그리고 방문한 곳을 제외하고 다시 반복문을 돌린다. 4. 모든곳을 방문하면 현재 값을 출력해주고 return으로 종료해준다. depth는 현재가 몇번째 반복문을 돌고있는지를 표시해주고, start는 이번에 넣을 데이터이다. base case로 depth가 n과 같아지면 종료를 해준다. impor.. 2020. 7. 20. [BAEKJOON] 2407번: 조합 (Java) 완전탐색 문제를 풀다가 순열과 조합 유형이 자주 나와서 계속 풀어보고 있다. nCm을 구하는 것이 문제이다. 1. 문제 2. 풀이 과정 2.1 재귀를 통한 접근 첫번째 접근 방법은 고등학교 때 배운 파스칼의 삼각형을 떠올려, 재귀를 이용한 방법으로 풀어보았다. 코드는 아래와 같다. import java.util.Scanner; public class Main { public static long paskal(int n, int m){ if(m == 0 || n == m){ return 1; } return paskal(n-1,m-1) + paskal(n-1,m); } public static void main(String[] args) { Scanner sc = new Scanner(System.in);.. 2020. 7. 16. [BAEKJOON] 2004번: 조합 0의 개수 (Java) 1. 문제 nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 n, m(0≤m≤n≤2,000,000,000, n!=0)이 들어온다. 출력 첫째 줄에 0의 개수를 출력한다. 예제 입력 25 12 예제 출력 2 2. 풀이 처음 이 문제를 접근할 때 nCr = n!/(n-r)!r! 공식을 통해서 접근하려고 했다. 하지만 입력 범위가 m,n이 최대 20억인걸 보고 당연히 이 방식은 아닐꺼라고 생각했다. 그리고 끝이 0이 되려면 2x5 쌍이 1개 일 경우 뒤에 0이 한개 생기므로 2와5가 곱해진 개수를 세서 2와5의 지수 중 작은거를 선택하면 되겠다고 접근했다. 여기서 하나 더 생각해야할 것은 2와 5의 지수의 총합을 어떻게 구할지 였다. 100!을 생각해 봤을 때, 5가 곱해진 개.. 2020. 7. 12. 이전 1 다음
