본문 바로가기

Algorithm44

[알고리즘] 프로그래머스 - 카펫 (완전탐색) 1. 문제 2. 풀이 중앙은 노란색으로 칠해져 있고, 나머지는 갈색으로 칠해져 있는 직사각형(정사각형) 모양의 카펫의 가로 세로 길이를 구하는 문제였다. 우선 사각형 형태이므로 갈색 격자 개수와 노란색 격자 개수를 더한 수는 무조건 짝수가 나올 것이다. 우선 2개를 더한 수의 약수들을 구한다. 그리고 가로의 길이가 더 크므로 i와 곱해서 sum이 나오는 숫자가 가로의 길이가 된다. 그리고 나서 주어진 모양을 만족하는지 검사를 한다. 가로는 2개 이므로 가로 길이에 2를 곱해서 구해주고, 세로도 마찬가지로 2개지만 가로 길이를 구할때 각 사각형의 맨끝을 가로길이에서 이미 포함하고 있기 때문에 4를 빼준다. 그러면 쉽게 답을 구할 수 있다. class Solution { public int[] calRect.. 2020. 7. 30.
[알고리즘] 프로그래머스-숫자 야구 (완전탐색) 1. 문제 2. 나의 코드 순열과 해시맵, 완전 탐색을 이용해서 풀었다. 우선 1~9까지의 서로 다른 3자리 수를 구하는 permutation 메소드를 구현하였다. 그리고 구한 순열의 숫자와 현재 baseball에 들어온 수들과 전부 비교하여 스트라이크 수와 볼 수를 전부다 만족하는 수이면 해시맵에 그 키에 대해서 1씩 더해주었다. 결과적으로 baseball의 길이와 해시맵에 들어가 있는값이 같다면 케이스를 모두 만족하는 수이므로 answer를 1씩 증가 시켜주는 방식으로 답을 구했다. import java.util.*; class Solution { private static Map map; public void permutation(boolean[] visited, int depth, String a.. 2020. 7. 26.
[알고리즘] 프로그래머스-소수찾기 (완전탐색) 1. 문제 2. 코드 순열을 이용해서 모든 경우의 수를 완전탐색하는 문제였다. dfs알고리즘을 순열에 적용했다고 생각하면된다. 현재 입력받은 문자열을 배열에 int로 저장을하고, permutation 메소드를 재귀로 돌려주었다. 방문한 곳은 true로 표시를하고 다시 방문을 하지 않았다. base case에서는 전부다 선택을 안한 케이스와, 소수는 2이상부터 있으므로 0과 1은 넣어주지 않았다. 또한 맨앞이 0으로 시작하는 케이스도 세지 않았다. 그리고 중복되는 경우의 수들이 있어서 map을 이용해서 중복된 값을 제거해주었다. 마지막으로 map에 넣은 키값들을 다시 빼내서 정수로 바꾸고 소수판별 메소드로 검사를해주었다. import java.util.*; import java.lang.*; class S.. 2020. 7. 20.
백준 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.

티스토리툴바