good_da22

최소 신장 트리 (Minimum Spanning Tree) 신장 트리 - n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리 -무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 무향 그래프, 가중치를 가진 그래프에서 만들 수 있다. Krusakal 알고리즘 간선을 하나씩 선택해서 MST를 찾는 알고리즘 간전 중심 표현 그래프 간선 리스트 사용 최초, 모든 간선을 가중치에 따라 오름차순dmfh wjdfuf 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택 n-1개의 간선이 선택될 때까지 2를 반복 // G.V : 그래프의 정점 집합 // G.E : 그래프의 간선 집..

그래프 (Graph) 그래프는 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결 관계로 표현한다 정점(Vertex) : 그래프의 구성요소로 하나의 연결점 간선(Edge) : 두 정점을 연결하는 선 차수(Degree) : 정점에 연결된 간선의 수 그래프는 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조 V : 정점의 개수, E : 그래프에 포함된 간선의 개수 V 개의 정점을 가지는 그래프는 최대 V * (V-1) / 2 개의 간선이 가능(무향 그래프, 양방향) 선형 자료구조나 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하기 용이하다. 트리는 계층형 관계와 1:N 관계를 나타내는 특수한 그래프 형태 그래프 유형 무향 그래프(Undir..

서로소 집합(Disjoint Set) 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들 다시 말해 교집합이 없다. 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분, 이를 대표자(representative)라 한다. 서로소 집합을 표현하는 방법 - 집합 구성요소(원소) 표현 연결 리스트 트리 서로소 집합 연산 Make-set(x) : 집합 생성(x원소(대표자)를 가지는) Find-set(x) : x가 속한 집합 찾기 Union(x, y) : x와 y 원소를 하나의 집합으로 만들기 (대표자끼리 합친다) 서로소 집합 표현 - 연결 리스트 같은 집합의 원소들은 하나의 연결리스트로 관리한다. 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다. 각 원소는 집합의 대표원소를 가리키는 링..

백트래킹 (backtracking) 퇴각 검색 모든 조합을 시도해서 문제의 해를 찾는다. -> 완전 탐색 해를 얻을 때까지 모든 가능성을 시도한다. 모든 가능성은 하나의 트리(상태 공간 트리)6처럼 구성할 수 있으며, 가지(선택지) 중에 해결책이 있다. 여러 가지(선택지)들이 존재한는 상황에서 하나의 가지를 선택한다. 선택이 이루어지면 새로운 선택지들의 집합이 생성된다. 이런 선택을 반복하면서 최종 상태에 도달한다. 보통 재귀 함수로 구현된다. N - Queen 문제 완전 탐색할 경우 수 많은 후보 해 중에서 유망하지 않은 해는 방문하지 않는다. 당첨 리프 노드 찾기 루트에서 갈 수 있는 노드를 선택한다. 꽝 노드까지 도달하면 최그늬 선택으로 되돌아와서 다시 시작한다. 더 이상 선택지가 없다면 이전의 선..

백준 14889번 스타트와 링크(JAVA) 문제 난이도 실버 2 알고리즘 분류 브루트포스 알고리즘 백트래킹 풀이 N명 중 N/2 명을 선택하여 능력치 합을 구하고 선택되지 않은 N/2명 의 능력치 합을 구한다. N 명 중 N/2 명을 뽑는 조합 6명 중 1, 2, 3을 뽑는 것은 4, 5, 6을 뽑는 것과 같다. N/2를 뽑는 조합을 절반만 수행할 수 있다. 1 ~ N 까지의 수 중 N / 2개를 선택하는 과정에서 1을 포함하는 경우와 1을 포함하지 않는 경우로 나눌 수 있다. 1을 포함하는 N / 2개를 선택하고 선택되지 않는 경우와 비교 코드 public class Main { static int N; static int[][] arr; static int answer; static int[] num..

SWEA 1952. [모의 SW 역량테스트] 수영장 (JAVA) 문제 알고리즘 분류 메모이제이션 그리디 dfs 풀이 메모이제이션 dp를 활용하는 경우 각 과정에서 최소값을 저장하고 갱신 조건에 따라 최솟값을 갱신한다. dfs를 활용하는 경우 모든 경우를 탐색하며 조건을 만족하는 경우 최솟값 갱신 코드 // 메모이제이션 public class Solution { public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter out = new BufferedWriter(new OutputStreamWriter(..

Database Modelling (데이터베이스 모델링) 논리적 데이터베이스 모델링 개념적 데이터베이스 모델링 단계에서 정의된 E-R Diagram을 Mapping Rule을 적용 관계형 데이터베이스 이론에 입각한 스키마를 설계하는 단계와 이를 이용하여 필요하다면 정규화하는 단계로 구성 기본 키 (Primary Key) 후보 키 중에서 선택한 주 키 널(Null)의 값을 가질 수 없다. (NOT NULL) 동일한 값이 중복해서 저장될 수 없다. (UNIQUE) 참조 키, 이웃 키 (Foreign Key) 관계를 맺는 두 엔티티에서 서로 참조하는 릴레이션의 attribute로 지정되는 키 Mapping Rule 개념적 데이터베이스 모델링에서 도출된 개체 타입과 관계 타입의 테이블 정의 개념적 모델링 => ..

Database Modelling (데이터베이스 모델링) 정보화 시스템을 구축하기 위해 어떤 데이터가 존재하는지 또는 업무에 필요한 정보는 무엇인지 분석하는 방법 관계형 데이터베이스는 표(table) 개념을 사용해서 데이터를 구성하는 방법을 사용 자바관점에서 table 하나는 Dto 하나 Database Modeling 순서 업무 프로세스 분석 개념적 모델링 - 개념적 구조 성립 논리적 모델링 - 데이터 모델 정립 물리적 모델링 - 물리적 데이터베이스 생성 일치성 검토 개념적 데이터베이스 모델링 업무분석 단계에서 얻어진 내용을 토대로 우선 Entity를 추출하고 Entity내에 속성(Attribute)을 구성하며 Entity간의 관계를 정의해서 ER-Diagram을 정의하는 단계 사용자 부문의 처리현상을..

백준 21578번 꿀 따기 (JAVA) 문제 난이도 골드 5 알고리즘 분류 그리디 알고리즘 누적 합 많은 조건 분기 풀이 누적 합을 이용하기 위해 입력 시 누적된 합을 계산한다. 이후 중간에 벌통이 위치한 경우에서 사용하기 위해 입력 값 중 최댓값을 찾는다. (양쪽 끝 위치 제외) 벌통의 위치 왼쪽 끝에 있는 경우 오른쪽 끝에 있는 경우 중간에 있는 경우 왼쪽 끝에 있는 경우 한 마리 벌은 오른쪽 끝에 위치 (누적 합을 최대로 만들기 위해) 나머지 한 마리는 오른쪽 벌과 왼쪽 끝에 위치한 벌통 사이에 위치 오른쪽 끝에 위치한 벌이 따는 꿀의 합 = (N - 2 ~ 0 까지의 합 - 나머지 벌의 위치에 있는 꿀의 값) 중간에 위치한 벌이 따는 꿀의 합 = (현재위치 - 1 ~ 0 까지의합) 오른쪽 끝에 있..

백준 13975번 파일 합치기3 (JAVA) 문제 난이도 골드 4 알고리즘 분류 자료구조 그리디 알고리즘 우선순위 큐 풀이 모든 파일이 합쳐지는 동안 최초 두 파일을 합치는 경우의 비용은 누적된다. 누적되는 비용의 최소화 필요 가장 작은 비용의 두 파일을 합치고 하나의 파일로 연산한다. 코드 public class Main { public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); Strin..