일단 시작해보는 블로그

문제 자연수 n(n>=2)을 입력받으면, 0도 회전, 시계방향 90도, 반시계방향 90도, 위아래 반전, 좌우 반전 출력하기. 코드 package arrayAlgorithm; import java.util.Scanner; public class Array_Rotate { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[][] A = new int[n][n]; // Filling data. int K = 1; for(int i=0; i

점화식을 구해서 적용했다. 생각 흐름 5 X 5 행렬이 있다고 보면, 데이터가 존재하는 인덱스대로 다음과 같이 처리할 수 있다. -> 점화식을 만들 때, 대칭인 것(예를 들어, 1 3 5 3 1)을 for문으로 처리하는 방식은 대칭의 중심이 되는 것을 0으로 만들고 실제로 for문안에서 출력할 때 절댓값(java에서는 Math.abs(...))로 사용하면 된다. 코드 package ArrayAlgorithm; import java.util.Scanner; public class Array_Diamond { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // 5x5배열 int[..

DP가 아닌 Greedy를 떠올려야 하는 이유 Ai는 Ai-1의 배수이므로, 모든 경우의 수를 전부 다 해보는 dp로 한다면, 비효율적이다. 따라서 그리디로 구현해야한다. 코드 package greedy; import java.util.Scanner; // 문제 : 동전 0 // 예제1 : 동전 10(N)종류로 4200(K)원을 만들 때, 동전개수의 최솟값구하기 public class backjoon_11047 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 1. 입력 int N = sc.nextInt(); // N : 동전종류의 수 int K = sc.nextInt(); // K : 동전의 합 //동전의..

** dp문제라고 판단했을 때, 가장 먼저 해야하는 것 : 메모이제이션을 위한 배열 d 정의하기. ** d[i] 정의 i계단까지 왔을 때 문제에 만족하는 조건에 만족하며, 얻을 수 있는 최대 점수. 문제에 만족하는 조건 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 한 계단 전에서 왔다면 그 이전에는 두 계단 이전에서 왔어야한다. 마지막 도착 계단은 반드시 밟아야 한다. -> d[N]을 구하면 된다. 경우의 수 생각해보기 i의 입장에서 생각해 봤을 때 다음과 같다. 1. i-1을 밟고 온 경우 d[i] = d[i-3] + ..

스티커는 2행 n열로 주어진다. 하나를 떼면 왼쪽, 오른쪽, 위, 아래를 연속으로 뗄 수 없다. 따라서 왼쪽부터 오른쪽으로 스티커를 뗄 수 있으면서 그 값이 최댓값인 것을 경우의 수 중에서 고를 것이다. 생각 각각 열마다 3가지 경우의 수를 둘 것이기 때문에 이렇게 할당했다. int[][] d = new int[n+1][3]; d[i][0] = i열에서 하나도 안뗐을 때, 그전부터 이 상황((k=1; k '그 전부터 이 상황까지'의 부분이 dp가 적용되어야할 부분. d[i][1] = i열에서 위에꺼만 뗐을 때, 그전부터 이 상황까지 더한 값. d[i][2] = i열에서 아래꺼만 뗐을 때, 그전부터 이 상황까지 더한 값. -> 결국 마지막 열에서 d[n][0], d[n][1], d[n][2]의 최댓값을 구..

전형적인 dp문제 중, 최댓값(Math.max) 구하는 것. bottom-up, 저장해놓은 것보다 큰 값이면 ok아니면 새로 계산한 값 넣기의 종류 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); // 상담 가능 일자 int[] T = new int[N+10]; // 상담을 완료하는데 걸리는 일자 int[] P = new int[N+10]; // 상담을 했을 때 받을 수 있는 돈 int[] dp = new int[N+10];// dp memoization을 위한 배열 //1부터 N까지 입력받는다..

처음에 그냥 리스트에 넣고 정렬을 해줘서인지,,,,,, 시간초과가 났었던 문제. 정렬 시, 아주 빠른 속도를 보이는 우선순위큐를 이용해야했다. 시간복잡도 : O(logN) import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); // 보석 개수 int K = sc.nextInt(); // 1개의 보석만을 담을 수 있는 가방 Node[] jewelry = new Node[N]; // 보석의 정보를 담고 있는 Node 배열 int[] max = new int[K]; // 보석관련 정보를 N만큼 입력받는다. for(int..

순열이란? 수학적으로는 완전순열이라고 하는데, 쉽게 말해서 모든 원소의 위치를 바꿔서 주어진 수 배열을 나열할 수 있는 경우의 수를 모두 표현한 것이다. 예를들어, {1, 2, 3} 이라면 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}가 해당된다. 순열의 구현 첫번째로 생각해봐야하는 것은 해당 순열의 다음순열 구하기이다. 그래야 loop문으로 모든 순열을 구현할 수 있기 때문! [순열의 다음순열 구하기] {1 2 3 4 5 6 7}로 이루어진 순열을 사전순으로 나열했을 때, 마지막에 올 수 있는 것은 {7 6 5 4 3 2 1}일 것이다. 앞의 자리가 3이면서 마지막에 올 수 있는 것은 ? {3 7 6 5 4 2 1} 앞의 자리가 4 ..