우당탕탕 개발 공부

페르마의 소정리 : a^p-2 = a^-1 ( p는 MOD, a는 r!(n-r)! ) 풀이 : 이항계수로 풀 수 없고, MOD연산은 나눗셈에는 적용 못함. 때문에 분모에 있는 a를 a^-1로 바꾼 뒤, 페르마 소정리 이용 Code public class Solution5607 { static long MOD = 1234567891; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int tc = 1; tc

제한된 칼로리 조건 하에서 가장 만족도 높은 조합을 선택하면 되는 문제 풀이 : 부분 집합 -> 재귀 함수 탐색을 하면서 만족도와 현재까지의 칼로리를 계속 기록하며 선택한 경우 --> 해당 항목의 만족도와 칼로리를 더해준 뒤 진행하고 선택하지 않은 경우 --> 기존의 상태에서 다음 번째 항목으로 넘겨주는 위 과정만 이해하신다면 유사한 문제들을 쉽게 풀이 Code public class Solution5215 { static int N, L; static int[] scores; static int[] cal; static int ans; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextI..

풀이 : dx, dy를 활용해서 8방향으로 움직이면서 if 문을 활용해 게임 판 내에 있는지 확인. 상대방 돌을 뒤집을 수 있으면 뒤집음 Code public class Solution4615 { static int N;// 보드 한변의 길이 (4, 6, 8 중 하나) static int M;// 플레이어가 돌을 놓는 횟수 // 상, 하, 좌, 우, 좌상, 우하, 우상, 좌하 static final int[] dx = { -1, 1, 0, 0, -1, 1, -1, 1 }; static final int[] dy = { 0, 0, -1, 1, -1, 1, 1, -1 }; static int[][] map; public static void main(String[] args) throws Exception ..

풀이 : N이 짝수,홀수일 때를 나누고 배열을 두개로 나눠서 입력값을 저장한다. 이를 번갈아가며 출력해줌 Code public class Solution3499 { public static void main(String args[]) throws Exception { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for(int tc = 1; tc

풀이 : DP로 해결해야 함 -> N (1 ≤ N ≤ 1,000) dp 배열을 만들고 그떄의 최대 길이를 저장하면서 max를 갱신해야함. ( dp를 쓰면, 이전에 했던 최대 길이 구하는 과정을 중복 안할 수 있음 ) Code public class Solution3307 { static int[] arr; static int[] dp; static int max, N; public static void main(String args[]) throws Exception { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for(int tc = 1; tc

풀이 : DP를 사용해서 푸는 대표적인 문제. bottom-up (table-filling) 방식 -> dp[N+1][K+1] 배열에 2중 for문을 통해 최대 가치 기입 백 트래킹으로 풀면 N 백 트래킹은 N

풀이 : 재귀 함수 활용, 가능한 모든 부분 수열의 합을 확인 -> 5215번 햄버거 문제랑 같음. 선택한 경우와 선택하지 않는 경우로 나눔 Code public class Solution2817 { static int N, K, result; static int[] arr; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int tc = 1; tc

최장 경로 = 방문한 정점의 수 풀이 : 무방향 그래프 -> dfs, visited[], ArrayList() 사용해서 방문했던 곳은 패스하고, 새로 방문하는 정점들을 타고 들어가면서 cnt++ Code public class Solution2814v { static int N, M, ans; static boolean[] visited; static ArrayList[] start; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int tc = 1; tc

풀이 : DFS로 풀어야 함. board[N]을 만들어 열을 내려가면서 해당 행에 어떤 위치에 퀸을 놓았는지 명시. 재귀 호출을 통해 위쪽 열(curr = 0)부터 퀸을 놓고 아래로(curr = N) 내려가는 방식 Code public class Solution2806V { static int board[]; // 퀸의 위치를 담는다. (board[0]=1 -> (0,1)에 하나의 퀸이 있다. board[1] = 3 -> (1,3)에 하나의 퀸이 있다.) static int answer; public static void main(String args[]) throws Exception { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for(i..

풀이 : N / 2 = mid 를 기준으로 위, 아래 나눠서 합치기. 배열의 시작점과 종료점을 바꿔가면서 각 행을 더해줌 Code public class Solution2805 { public static void main(String args[]) throws Exception { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for(int test_case = 1; test_case