0. 문제 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 1. 문제 이해 조합 이차원 좌표의 조합 구하기 그래프 완전 탐색 - BFS 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Queue; import java.util.StringTokenizer; public class BOJ14502 { static in..

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제 이해 부분 집합 시뮬레이션 2. 제출 가. 오답 import java.io.*; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; import java.util.StringTokenizer; // 60 tc 중 58개 통과 public class SWEA1767 { static int N, ret; static int[][] map; static int[] dy = {-1, 0, 1, 0}; static ..

0. 문제 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 1. 문제 이해 조합 DP 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; // DP - 조합 public class BOJ1010 { static int N, M; public static void main(String[] args) throws Exception { BufferedReader br = new B..

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 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장하여 매번 다시 계산..