0. 문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1. 문제 이해 Brute force DP 2. 제출 가. Brute force import java.util.Scanner; // brute force -> 144ms public class BOJ1463 { static int N, ret = Integer.MAX_VALUE; // 입력받은 수 public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); solve(N, 0); System.out.println(ret); sc.close(); } stat..

0. 문제 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 1. 문제 이해 그래프 최단 거리 Dijkstra 4방위 탐색 2. 제출 가. Dijkstra algorithm - FOR문으로 구현 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; // Dijkstra algorithm // FOR문으로 구현 -> 774ms p..

0. 문제 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. 문제 이해 최단 경로 Dijkstra algorithm 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.PriorityQueue; import java.util.Str..

1. 이항 계수 구하기 가. 이항 계수 이항 정리 : 이항식의 거듭제곱을 이항 계수를 계수로 하는 일련의 단항식들의 합으로 전개하는 정리. 이항 계수 : 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다. (x+y)^3 = x^3 + 3x^2y + 3xy^3 + y^3 조합으로 이항 계수를 구할 수 있다. 위와 같이 일반화할 수 있다. 나. 조합 공식 nCr = n! / (r!( n-r)!) 조합 공식 - 계산량이 많은 팩토리얼(n!, r!)을 계산하지 않고 아래의 수식을 이용한다. nCr = (n-1)C(r-1) + (n-1)Cr 이는 재귀 함수로 구현할 수 있다. comb(n, r) IF n==k or k==0 : RETURN 1 // 모두 뽑거나 하..

1. Memoization 가. 피보나치수열 F0 = 0; F1 = 1; Fn+2 = Fn+1 + Fn; 피보나치수열의 점화식이다. fib(n) IF m < 2 : RETURN n ELSE : RETURN fibo(n - 1) + fibo(n - 2) fib1, fib2 ... 등이 중복 호출이 발생한다. fib()는 순수 함수다. 💡 순수 함수 함수 반환 값은 동일한 인수에 대해 일정합니다. 이 함수에는 부작용이없습니다. (함수 밖에 위치한 어떠한 상태 값도 수정하지 않는다.) 그렇기 때문에 fib1, fib2, … 등을 계산 결과는 항상 일정하다. 한 번만 계산하고 결괏값을 재사용할 수 있다. 나. Memoization 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장하여 매번 다시 계산..

1. 최단 경로 알고리즘 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로. 2. Dijkstra 알고리즘 음의 가중치가 없는 그래프의 한 정점에서 다른 정점들까지의 최단 거리 비용을 구하는 알고리즘. 시간 복잡도 : 반복문으로 구현 시 O(V^2) : PQ로 구현 시 O(ElogE) 가. 반복문으로 구현 시간 복잡도 : 반복문으로 구현 시 O(V^2) import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class dijkstraTest { static class Node { in..

0. 문제 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 1. 문제 이해 순열 시뮬레이션 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.StringTokenizer; public class BOJ17281 { static int N, cur, ret; static int[..

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제 이해 최소 신장 트리 (MST) Kruskal Prim 2. 제출 MST를 구하는 문제다. 주어지는 가중치가 크기 때문에 overflow를 주의하면서 풀면 된다. 가. Kruskal import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class SWEA3124 { static int V, E; static long ret; // int overflow 발생 sta..