mei 기술 블로그

1. 조합서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서 X, 중복 X)nCr = n! / (n - r)!r! = nPr / r! (단, 0 2. 중복 조합서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서 X, 중복 O)nHr = (n+r-1)Cr3. 코드private static int getComb(int n, int r) { int pResult = 1; int rResult = 1; // nPr for (int i = n; i >= n-r+1; i--) { pResult *= i; } // r! for (int i = 1; i // 조합 구현private static void combination(int[] arr, boolean[..

1. 팩토리얼1에서 n까지 모든 자연수의 곱 (n!)n! = n(n - 1)(n - 2) ... 12. 순열순서를 정해서 나열서로 다른 n개 중에 r개를 선택하는 경우의 수 (순서 O, 중복 X)nPr = n! / (n-r)! = n(n - 1)(n - 2) ... (n - r + 1) (단, 0 3. 중복 순열서로 다른 n개 중에 r개를 선택하는 경우의 수 (순서 O, 중복 O)nΠr = n^r4. 원 순열원 모양의 테이블에 n개의 원소를 나열하는 경우의 수n! / n = (n - 1)!5. 코드// 1. 팩토리얼// 기본 풀이int n = 5;int result = 1;for (int i = 1; i (x * y)); // 120// 2. 순열/ 5명을 3줄로 세우는 경우의 수n = 5;int r ..

1. 경우의 수어떤 사건에서 일어날 수 있는 경우의 가짓수ex) 동전을 던지는 사건: 경우의 수 - 2ex) 주사위를 던지는 사건: 경우의 수 - 6사건 A가 일어날 경우의 수: n(A)2. 합의 법칙사건 A 또는 사건 B가 일어날 경우의 수사건 A와 사건 B의 합의 법칙: n(A ∪ B)n(A ∪ B) = n(A) + n(B) - n(A ∩ B)3. 곱의 법칙사건 A와 사건 B가 동시에 일어날 경우의 수사건 A와 사건 B의 곱의 법칙: n(A x B)n(A x B) = n(A) x n(B)4. 코드int[] dice1 = {1, 2, 3, 4, 5, 6};int[] dice2 = {1, 2, 3, 4, 5, 6};int nA = 0, nB = 0, nAandB = 0;// 1. 합의 법칙// 두 개의 ..

1. 집합(Set)특정 조건에 맞는 원소들의 모임2. 교집합두 집합이 공통으로 포함하는 원소로 이루어진 집합A ∩ B = {x | x ∈ A and x ∈ B}3. 합집합어느 하나에라도 속하는 원소들을 모두 모은 집합A∪B = {x | x ∈ A or x ∈ B}4. 차집합A or B에만 속하는 원소들의 집합A - B = {x | x ∈ A and x !∈ B}5. 여집합전체 집합(U) 중 A의 원소가 아닌 것들의 집합A^c = {x | x ∈ U and x !∈ A}6. 코드HashSet set = new HashSet();set.add(1);set.add(1); // set은 중복 허용하지 않기 때문에 1은 한번만 삽입set.add(2);set.add(3);set.remove(1); // 1이라는 데..

1. 주요 프로토콜 프로토콜명 포트 번호 SSH 22 HTTP 80 HTTPS 443 MySQL 3306 Tomcat 8080 Oracle DB 1521 DNS 53 2. Inbound/Outbound Rule Default 보안 그룹 Inbound Rule 동일 보안 그룹에서 접근하는 경우에만 Inbound 허용 Outbound Rule 새로 만드는 경우 특별히 수정하지 않는 한 해당 값이 기본값 All Traffic - All(0.0.0.0/0) Outbound 허용 상태 조금 더 보안 처리하려면 값 변경 필요 3. 각 리소스의 Inbound/Outbound 정보 Backup Server SG Inbound HTTP(80) - 0.0.0.0/0(All) SSH(22) - 0.0.0.0/0(All) 또..

1. Services - Compute - Server 선택 2. 서버 생성 및 이미지 선택 부팅 디스크 크기: 50GB 이미지타입: Application Application 이미지타입: Jenkins 서버 타입: Compact 가장 최근 버전의 Jenkins-CentOS-7.8 선택 3. 서버 설정 4. 인증키 설정 새로운 인증키 생성 및 저장 5. 네트워크 접근 설정 6. 최종 확인 상태가 생성중 - 부팅중 - 설정중 - 운영중으로 변경되는지 확인 7. 공인 IP 생성 Public IP 선택 8. 포트 포워딩 설정 비공인 IP NCP 같은 네트워크 그룹 권한 컴퓨터에서 접속할 때 사용 우리 환경에서는 사용 안함 공인 IP 서버 외부에서 Tomcat 등을 받을 때 사용 프로그램 설치 권한 없음 이미 ..

1. 서로소 집합 서로소 집합(Disjoint Sets)란 공통 원소가 없는 두 집합 2. 서로소 집합 자료구조 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조는 두 종료의 연산을 지원한다. 합집합(Union): 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 서로소 집합 자료구조는 합치기 찾기(Union Find) 자료구조라고 불리기도 한다. 여러 개의 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작 과정은 다음과 같다. 합집합(Union) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다. A와 B의 루트 노드 A’, B’를 찾는다. A’를 B’의 부모 노드..

비용이 음수인 간선이 있을 때 최단 경로를 구하는 알고리즘 1. 음수 간선이 포함된 상황에서의 최단 거리 문제 백준 ‘타임머신’ 문제 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 2. 벨만 포드 최단 경로 알고리즘 음수 간선에 관하여 최단 경로 문제는 다음과 같이 분류할 수 있다. 모든 간선이 양수인 경우 음수 간선이 있는 경우 음수 간선 순환이 없는 경우 음수 간선 순환이 있는 ..

모든 출발지에서 다른 모든 출발지까지 최단 경로 계산 1. 플로이드 워셜(Floyd-Warshall) 알고리즘 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다. 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다. 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다. 점화식에 맞게 3중 반복문을 이용하여 2차원 테이블을 갱신한다. 다익스트라 알고리즘과 비교했을 때 구현 난이도는 쉬운 편인데 시간 복잡도는 O(N^3)이다. 노드의 개수가 적은..

하나의 출발지에서 다른 모든 출발지까지 최단 경로 계산 1. 최단 경로 문제 가장 짧은 경로를 찾는 알고리즘 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 2. 다익스트라 최단 경로 알고리즘 개요 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다. 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않는다. 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다. 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 ..