[프로그래머스] 하노이의 탑 - JAVA

문제https://school.programmers.co.kr/learn/courses/30/lessons/12946전략하노이의 탑은 유명한 재귀 문제기둥이 3개인 것 기준 3개의 원판을 3번째 기둥으로 옮기려면위의 2개의 원판이 가운데 기둥에 옮겨져야 한다.그 후에 1번째 기둥의 마지막 원판을 마지막 3번째로 옮기고2번째 기둥의 원판 2개를 3번째로 옮긴다. → 이때 1번 스텝에서 2개의 원판이 가운데 기둥으로 옮겨지는 것은 출발지,나머지,도착지 기둥의 관점에서 보면 전체 1~3의 과정이 몇번째 기둥이 나머지, 도착지 기둥인지 옮겨지는 위치만 달라지고 전체 양상은 똑같다. → 어차피 마지막 3번째 원판은 모든 다른 원판보다 크니 위의 2개의 원판을 움직이는 것에 아무 영향이 없다. → 그렇게 3개의 원..

• format_list_bulleted 카테고리 없음
• · 2024. 9. 6.

[백준] 계단 수 1562 - JAVA

문제https://www.acmicpc.net/problem/1562전략N = 100 → 완전탐색으로는 불가능dp로 고민하자처음에는 dp[i][j]로 i : i자리 수 중 , 마지막이 j로 끝나는 계단수로 설정단순히 dp[i-1][j-1] + dp[i-1][j+1]로 더하면 계단수가 나올것이라는 생각하지만 989898989와 같이 계단수로 이루어져있지만 모든 자리수가 나오지 않는 경우가 있어 각 자리 수의 방문체크가 필요하다는 판단dp[i][j][k| 1dp[i-1][j-1][k] + dp[i-1][j+1][k] 로 모든 j-1, j+1을 끝자리로 가지는 모든 방문 여부를 확인한 수들을 다 더해준다ex) 989898989의 경우와 789898989의 경우 모두 확인따라서 길이가 N이면서 0부터 9까지 숫..

• format_list_bulleted 공부하기!/알고리즘
• · 2024. 9. 3.

[백준] 암호코드 2011 - JAVA

문제https://www.acmicpc.net/problem/2011전략5000자리이기때문에 완전탐색은 불가능입력값이 크기 때문에 dp로 생각해보면 앞에서 부터 끊어서 확인해보ex) 25114의 경우 - B,Y,A,K,A,D,N 의 알파벳들이 끊었을 때 나올 수 있다.-> 2/5/1/1/4 , 25/1/1/4, 25/11/4, 25/1/14, 2/5/11/4, 2/5/1/14dp[i] = i자리 영어의 암호화 가짓수로 두기맨 마지막 숫자를 확인 했을 때, 아래와 같이 확인할 수 있다.새로 붙인 숫자가 1~9를 앞에 수와 별도로 칠때 d[i-1]의 가짓수를 가진다.,앞에 숫자와 포함해 10 ~ 26 ->이 경우 앞에 숫자와 포함하기 때문에 가짓수는 d[i-2]코드import java.io.BufferedR..

• format_list_bulleted 공부하기!/알고리즘
• · 2024. 8. 23.

[백준] 타일 채우기 2133 - JAVA

문제https://www.acmicpc.net/problem/2133전략N = 2 -> 3 N = 4 -> 11 N = 6 -> 41 N이 홀수일 때는 0 N+2가 될수록 dp[i-2]와는 별도로 양끝을 세로막대로 채우고 가운대를 가로로 다 채운 형태의 2가지 경우가 추가된다. 1001    00001001    10010000   1001즉, N+2가 될때마다 i-2와 앞선 가운대를 다 채운 별도의 경우 수 그리고 i자체가 가운대를 채운 수를 고려해야 한다.정리하면, dp[i] = dp[i-2] * 3 + dp[4부터(i-2)까지 경우의 수] * 2의 합 + 2;코드import java.io.BufferedReader;import java.io.IOException;import java.io.Input..

• format_list_bulleted 공부하기!/알고리즘
• · 2024. 8. 22.

[백준] 가장 큰 정사각형 1915 - JAVA

문제https://www.acmicpc.net/problem/1915 전략완전탐색 : 입력값이 1000 * 1000 으로 너무커서 안된다dp를 통해 접근해보자dp로 접근시 dp[i][j] = 해당좌표 i,j를 기준으로 가장 큰 정사각형의 길이이때 정사각형 4 꼭지점 중 어떤 점을 i,j 로 둘것인가오른쪽 아래 꼭지점을 기준으로 했을 때 좌표를 i = 0, j = 0으로 탐색시 작은 사각형부터 탐색할 수 있을것이라고 판단하였다.따라서 왼쪽 , 위 , 왼쪽 위의 꼭지점이 모두 1이 될 경우 정사각형으로 확장이 가능하다.아래와 같은 정사각형의 경우 결국 확인해야 하는 세 점 중 최솟값을 기준으로 확장이 가능하다는것을 확인할 수 있다.1 1 1 1 2 2 1 2 3 코드import java.io.Buffered..

• format_list_bulleted 카테고리 없음
• · 2024. 8. 15.

[백준] 동전 9084 - JAVA

문제https://www.acmicpc.net/problem/9084전략동전으로 가능한 금액의 가짓수를 구하기 때문에 처음에 떠올린것은 완전탐색, 그리디 , DP이 중 테스트 케이스가 10 , 동전의 가짓수가 20 , 금액은 10000이다.완전탐색 : 동전의 종류별로 조합을 통해 금액 확인 ⇒ 시간복잡도가 20! * 10으로 너무 크다그리디 : 값이 큰 동전을 먼저 사용하는 방식은 최적해를 보장하지 않는다.시간복잡도까지 고려해서 DP로 접근하는것이 맞다고 생각해 고민하였다.dp배열을 금액에 따른 가짓수로 두었을때 2중 for문으로 동전별로 가능한 금액의 가짓수를 세는것dp[j] += dp[j - coin] (단, j - coin >= 0일 때)하지만 dp배열이 1차원일 경우 5+7과 7+5처럼 중복으로 ..

• format_list_bulleted 공부하기!/알고리즘
• · 2024. 8. 13.