백준 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

백준 1011번 Fly me to the Alpha Centauri(Java)

규칙을 찾기가 어려웠던 문제. 중간에 계산을 잘못해서 푼 줄 알았는데 알고보니 틀렸었다. 뭔가 규칙이 보일듯 말듯 한데 잘 보이지 않아서 고생했다. 조건 시작할때와 목적지에 도달 전의 이동거리는 반드시 1이 되어야 한다. 이동 가능한 거리는 바로 전에 이동했던 거리(n)의 n-1, n, n+1만큼 이동할 수 있다. 이런 문제를 풀때는 반드시 어딘가에 경우의 수를 써가면서 풀자. 암산하려고 하면 더 어렵고 헷갈린다. 거리(y-x) 경로 가장 큰 이동거리 작동횟수 1 1 1 1 2 11 1 2 3 111 1 3 4 121 2 3 5 1211 2 4 6 1221 2 4 7 12211 2 5 8 12221 2 5 9 12321 3 6 위 표를보면 몇가지 규칙이 있다. 1. 거리가 제곱일때 그 가장 큰 이동거리가..

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

백준 2839번 설탕배달 (Java)

막상 보면 매우 쉬운 문제 같지만, 알고리즘을 짜려고 들어가면 생각보다 어렵다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int sugar=scanner.nextInt(); int count=0; if(sugar%5>3){ count=sugar/5; sugar=sugar-5*count; } else if(sugar%5

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

백준 2775번 부녀회장이 될테야(java)

간단하지만 구현을 어떻게 하느냐에 따라 시간차이가 많이 나는 문제 유형이다. 제한이 14로 되어있어서 배열에 각 호수마다의 인원수를 넣었지만, 만약 제한이 100이 되었다면, 구현을 달리 해야한다. 일단은 배열에 각 호수마다의 인원을 넣어서 풀었다. 내일 알고리즘을 손 봐서 제한이 100일때도 구현해 봐야겠다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int[][] apart = new int[15][15]; for(int i = 0; i < 15; i++) { apart[i][1] = 1; apart[0][i] = ..

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