본문 바로가기

Algorithm

 (252)
[백준] 2579 : 계단 오르기 JAVA 풀이 정말 어렵다............ 어렵다는 말만 오백번째 하고 있는 것 같은데 아직 DP문제에 익숙하지 않으니 어쩔 수 없다. 그래도 각 계단의 점수와 최댓값을 저장하는 배열을 따로 만들어야 하는 것이나 초기화하는 부분이라도 생각해냈으니 걸음마는 뗀 수준이라 자축해보겠다 흑흑 이 문제에서 중요한 조건은 연속된 계단 세 개를 모두 밟을 수 없다는 것이다. V V V ? V V 그럼 계단을 밟을 수 있는 건 이렇게 두 경우가 된다. 한 칸 전 계단을 밟았으면 두 칸 전 계단은 반드시 밟지 말아야 한다. 한 칸 전 계단을 밟지 않았다면 두 칸 전 계단은 반드시 밟아야 한다. 이 두 경우 중에 최댓값을 저장하면 되는데, 이를 코드로 쓰면 다음과 같다. // dp는 그 계단까지의 최댓값을 저장하는 배열 // ar..
[백준] 9095 : 1, 2, 3 더하기 JAVA 풀이 1, 2, 3 만으로 n을 만든다는 것 자체가 힌트였다. 우선 1, 2, 3을 사용해 1, 2, 3을 만들 수 있는 경우의 수가 필요하다. 왜냐하면 1,2,3 이후의 수, 예를 들어 4를 만들려면 이전의 수인 1, 2, 3에 3, 2, 1을 더해서 만들어야 하는데 1을 만들 수 있는 경우의 수 -> (1) : 1개 2를 만들 수 있는 경우의 수 -> (1,1), (2) : 2개 3을 만들 수 있는 경우의 수 -> (1,1,1), (1,2), (2,1), (3) : 4개 여기에 각각 3, 2, 1을 더하기만 하면 4가 되니 1, 2, 3을 이용해 4를 만들 수 있는 경우의 수는 이전의 수인 1, 2, 3를 만드는 경우의 수 그 각각의 합이 되는 것이다. 마찬가지로 5도 이전의 수인 4, 3, 2에 +1, ..
[백준] 2748 : 피보나치 수 2 JAVA 풀이 동적 계획법은 크게 재귀(Top-Down)방식과 반복문(Bottom-Up)방식으로 나뉜다. 재귀 방식은 큰 문제를 작게 쪼개서 가장 하위 문제부터 풀어나가는 것인데, 동적 계획법은 이미 풀린 하위 문제를 다시 반복하지 않고 그 값을 재활용하고, 이를 메모이제이션(Memoization)이라고 한다. 동적 계획법 연습을 위해 Top-Down과 Bottom-Up 두 방식으로 문제를 풀어봤다. 먼저 재귀를 활용하는 Top-Down 방식이다. 이전에도 재귀를 이용해 피보나치 수를 구한 적이 있는데, 그때는 그냥 단순히 재귀를 해서 값을 구할 뿐이었다. 하지만 이 문제의 카테고리는동적 계획법이고 그런 방식으로 풀면 시간초과라는 결과가 나온다. 따라서 한 번 해결한 하위 문제의 값을 재활용하는 방식으로 문제를 풀었다..
[백준] 2193 : 이친수 JAVA 풀이 이번 문제도 상당히 어려웠다.. 문제의 난이도 자체가 높다기보단 내 경험치가 부족한 탓인 것 같다. 이친수는 0으로 시작하지 않고 1이 두번 연속으로 나타나지 않아야 한다. 이는 N번째 자리 수가 0일 경우에는 그 이전에 1이 나오든 0이 나오든 상관이 없지만 1일 경우에는 반드시 0이어야 한다는 걸 의미한다. 그래서 N번째 자리수가 0인 이친수의 개수와 1인 이친수의 개수를 나눠서 세기 위해 2차원 배열을 사용했다. 이때 입력될 수 있는 N의 범위가 1부터 90까지인데 이는 int에 저장할 수 있는 크기를 넘어서기 때문에 long형으로 선언해줘야 한다. long dp[][] = new long[N+1][2]; 이제 dp[?][0]에는 끝자리가 0인 이친수의 개수를, dp[?][1]에는 1인 이친수의 개..
[백준] 1463 : 1로 만들기 JAVA 풀이 N을 입력받고 N이 3으로 나눠떨어진다면 나누기 3을, 2로 나눠떨어진다면 나누기 2를, 두 경우에 해당되지 않으면 1을 빼는 것을 반복해 1을 만드는 문제다. while문을 사용해서 N이 1이 될 때까지 if문을 이용해 연산을 하고, 카운트를 셌으나 시간초과가 나왔다. 그리고 이 블로그를 참고해서 문제를 해결했다. https://st-lab.tistory.com/133 1. N을 입력받는다. 2. 메모이제이션을 하기 위해 N+1 크기의 Integer 배열 dp를 생성한다. (Integer는 기본값이 null이고 int형으로 바꾸지 않으면 연산을 할 수 없는 Wrapper class이다. int형은 기본값이 0이기 때문에 아직 방문하지 않은 값인지 판단하려면 배열 전체를 -1같은 값으로 초기화를 하는 과..
[백준] 1924 : 2007년 JAVA 풀이 1. 일수와 요일을 배열에 저장한다. 2. StringTokenizer로 입력받은 월과 일을 분리해서 변수에 저장한다. 3. 총 일수를 저장할 total이라는 변수를 생성한다. 4. 입력된 월이 4월이라면 1~3월의 일수를 total에 더한다. 5. total에 입력받은 일수를 더한다. 6. total을 7로 나눈 나머지를 인덱스로 갖는 Day 배열의 값을 출력한다. import java.io.*; import java.util.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); S..
[백준] 10992 : 별 찍기 - 17 JAVA 풀이 첫줄 - 중간 - 마지막줄로 나눠서 코드를 작성했다. 하나의 반복문 안에서 첫번째줄일 때와 마지막줄일 때를 if문으로 검사할까했지만 반복문을 돌면서 계속 검사를 하니 실행시간이 더 오래걸리지 않을까 해서 따로 분리를 해버렸다. 음.....실행시간이 크게 다르지는 않을 텐데 아직 무엇을 우선시해야 하는지를 잘 모르겠다. import java.io.*; public class ArrayEx1{ public static void main(String[] args)throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); Strin..
[백준] 10991 : 별 찍기 - 16 JAVA 풀이 괄호 안에 있는 것이 공백의 개수라고 하면 N = 3일 때 출력해야 할 내용은 다음과 같다. (n-1)* (n-2)*(n-2)* (n-3)*(n-2)*(n-2)* 행마다 한 행에서 첫 번째 별이 나오기까지의 공백의 개수가 달라지는 것과, 별과 공백이 번갈아서 나오는 것에서 규칙을 찾아 코드를 작성했다. import java.io.*; public class Main{ public static void main(String[] args)throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); StringBuilder sb =..

티스토리툴바