백준 1018번 체스판 다시 칠하기(Java)

정사각형으로 n*m으로 나눠지고 각 칸은 B,W중 하나로 칠해진 판을 체스판으로 만드려고 하는데, 이때 어느부분을 자르면 가장 적게 칠할수 있을지 푸는 문제. 구현은 쉬웠지만, 어떻게 구해야 할지 고민을 많이 했던 문제. 일단 8*8 체스판을 제작하려 했을때, 처음 시작하는 부분, 즉 배열로 따지면 (0,0)에 들어있는 색상에 따라 칠할수 있는 숫자가 달라진다. 색상에 따라 칠하는 수는 "64-색상에따른 칠하는 수"가 된다. 만약 B가 첫번째이면 W가 첫번째로 오는 체스판을 칠하는 수는 B의 수에다가 64를 빼면 된다. 그것만 알면 나머진 풀기 쉬운 문제. import java.util.Scanner; public class Main { public static void main(String[] args..

• format_list_bulleted Algorithm/백준
• · 2021. 3. 27.
• textsms

백준 2798번 블랙잭(Java)

구할수 있는 모든 경우의 수를 구해, 그 수중에서 목표인 수에 가장 가까운 수를 출력하는 문제. 반복문으로 n번째 카드를 기준으로 삼고 그 카드를 더할수 있는 모든 경우의 수를 더해 배열에 저장후, 목표값과 가장 가까운 수를 출력하도록 했다. import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int card_num=scanner.nextInt(); int[] card_list=new int[card_num]; List card_sum=new..

• format_list_bulleted Algorithm/백준
• · 2021. 3. 15.
• textsms

백준 11729번 하노이탑 이동순서(Java)

유명한 문제. 복잡하게 생각할 수록 어려운 문제다. 장대의 개수가 3개보다 많을시 난이도역시 오르는 문제. 하지만 3개여서 매우 쉽다. 분할정복을 사용해서 풀면 매우 간단하다. 가장 큰 원판을 3번째 장대로 옮기는걸 n번 반복하면 된다. 즉 n번째의 원판을 이동시키려면 n-1번째까지의 원판을 모두 2번째 장대로 옮겨야 된다. 그 후 2번째 장대로 옮겨놓은 판을 다시 3번째 장대로 옮기기만 하면 끝. import java.util.Scanner; public class Main { static void hanoi(int n,int start,int middle,int to){ if(n==1) { System.out.println(start + " " + to); return; } hanoi(n-1,star..

• format_list_bulleted Algorithm/백준
• · 2021. 3. 13.
• textsms

백준 2447번 별찍기-10(Java)

재귀를 이용한 별찍기다. 2시간정도 낑낑거리면서 풀었다. 누구나 규칙을 찾을수 있지만, 그것을 알고리즘으로 구현하는게 어려운 문제다. 일단 밑의 코드로 실행을 시키면 실행은 된다만, 시간초과가 뜬다. 3^6(729) 입력시 걸리는 시간이 1초가 넘어간다. 문제에서는 3^7 까지가 조건이니 시간초과. 풀이방법 * * * * * * * * 크기가 3인 패턴은 가운데 하나만 비어있는 패턴이다. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 크기가 9인 패턴을 보자. 규칙성이 보인다. 크기가 3인 패턴과 같은 규칙이다. 다른점은 *..

• format_list_bulleted Algorithm/백준
• · 2021. 3. 12.
• textsms

백준 10870번 피보나치 수 5(Java)

피보나치의 수를 구하는 문제. f(n)=f(n-1)+f(n-2)가 성립하기에 이를 기반으로 풀면되는 쉬운 문제이다. 이때 재귀의 특징상 메모리의 낭비가 심한데 낭비를 줄이는 방법은 위 사진에 나와있듯이 f(19)=f(17)+f(18)이다. 그런데 f(18)을 구하는데 f(17)의 값을 계산한 적이 있으므로 f(17)의 값을 어딘가로 빼놓고 f(19)를 계산할 때 f(18)과 f(17)을 더해 계산하면 메모리를 절반가량 아낄 수 있다. 다만 이 풀이법에서는 아직 구현하지 않았다. import java.util.Scanner; public class Main { int fibo(int count){ if(count==0) return 0; if(count==1) return 1; return fibo(cou..

• format_list_bulleted Algorithm/백준
• · 2021. 3. 12.
• textsms

백준 10872번 팩토리얼(Java)

재귀함수의 가장 기초적인 문제다. 자기 자신을 리턴시켜 답을 구하는 방식. 따로 설명이 필요 없을것 같다. 한가지 주의할 점은 0!의 값은 1이다. 이것만 주의해 주면 쉽게 풀 수 있다. import java.util.Scanner; public class Main { int multi(int num){ if(num

• format_list_bulleted Algorithm/백준
• · 2021. 3. 10.
• textsms