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. 문제 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[..