알고리즘31 [알고리즘] 프로그래머스 - 단어변환 (dfs/bfs) 1. 문제 2. 문제풀이 현재 주어진 단어를 한글자씩 수정해서 최종 목표 단어로 변환이 가능한지를 구하고, 만약 변환이 가능하다면 몇번만에 가능한지 최소 변환 횟수를 구하는 문제였다. 현재 단어에서 words 배열에 있는 단어로 변환이 가능하다면 visit 배열에 방문을했다고 표시를 한 후 dfs 탐색 방법을 이용해서 탐색을 진행한다. dfs의 base case로는 전부 방문했거나, 현재 단어와 찾는 단어가 같을 경우 탐색을 종료했다. 그리고 최소 횟수를 계속 갱신하여 최종적으로 minNum을 반환한다. 변환이 불가능할 경우 0을 반환한다. class Solution { int minNum = 999999999; public void dfs(boolean[] visit, String[] words, St.. 2020. 8. 8. [알고리즘] 프로그래머스 - 카펫 (완전탐색) 1. 문제 2. 풀이 중앙은 노란색으로 칠해져 있고, 나머지는 갈색으로 칠해져 있는 직사각형(정사각형) 모양의 카펫의 가로 세로 길이를 구하는 문제였다. 우선 사각형 형태이므로 갈색 격자 개수와 노란색 격자 개수를 더한 수는 무조건 짝수가 나올 것이다. 우선 2개를 더한 수의 약수들을 구한다. 그리고 가로의 길이가 더 크므로 i와 곱해서 sum이 나오는 숫자가 가로의 길이가 된다. 그리고 나서 주어진 모양을 만족하는지 검사를 한다. 가로는 2개 이므로 가로 길이에 2를 곱해서 구해주고, 세로도 마찬가지로 2개지만 가로 길이를 구할때 각 사각형의 맨끝을 가로길이에서 이미 포함하고 있기 때문에 4를 빼준다. 그러면 쉽게 답을 구할 수 있다. class Solution { public int[] calRect.. 2020. 7. 30. 백준 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. [Algorithm] 조합 코드 구현 (Java) 완전탐색 알고리즘에서 모든 경우의 수를 계산한 후 결과 값을 찾는 방식이 자주 나온다. 그래서 재귀를 통해 조합을 구현하는 방법에 대해서 정리하려고 한다. 이때 기본 형식은 아래와 같다. 1. 조합(Combination) 조합은 고등학교 수학에서 경우의 수를 계산할 때 순열과 조합 파트로 배웠었다. 프로그래밍에서도 수학에서의 순열과 조합과 같다고 생각하면 된다. 잠시 고등학교 수학에서 배운걸 생각해보면 아래와 같다. 순서를 고려하지 않고 선택하는 방법 nCr : n개 중 r개를 순서에 상관없이 선택하는 방법의 수 nCr = nPr/r! / (n-r)!r! 간단히 예시를 들면 {1,2,3} 에서 2개를 뽑는 경우의 수 는 3C2로 3X2/2! = 6. 즉, 3가지가 나온다. {1,2} {1,3} {2,3}.. 2020. 7. 12. 이전 1 2 3 4 5 6 다음
