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..

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제 이해 최소 신장 트리 (MST) 2. 제출 이 문제는 모든 노드가 서로 연결될 수 있는 완전 그래프다. 따라서 많은 간선이 생길 수 있다. (E의 최대 개수 = (V(V-1))/2)) Kruskal으로 풀기 : 시간 복잡도 O(ElogE + V) : 간선이 많은 밀집 그래프에서 불리. Prim으로 풀기 PQ로 구현한 Prim : 시간 복잡도 O(ElogE) : 간선이 많은 밀집 그래프에서 불리. 반복문으로 구현한 Prim : 시간 복잡도 O(V^2) : 밀집 그래프에 유리! 밀집 그래프에서 유리한 반복문으로 구현한 Prim 알고리즘으로 문제를..

0. 문제 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 1. 문제 이해 부분집합 완전탐색 (DFS, BFS) 2. 제출 가. 통과 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class BOJ17471 { static int N, ret; static int[] person, parent; sta..

0. 문제 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 1. 문제 이해 조합 2. 제출 2가지 방식으로 조합을 구현해 보았다. 가. 재귀 함수 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.StringTokenizer; public class BOJ1759_2 { sta..