good_da22

서로소 집합(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(..

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

백준 17204번 죽음의 게임 (JAVA) 문제 난이도 실버 3 알고리즘 분류 구현 그래프 이론 그래프 탐색 시뮬레이션 풀이 출발번호(0) 부터 목표번호(K)로 가는 최솟값 구하기 어떤 방법으로도 K로 갈 수 없는 경우는 K에 도착하기 전에 사이클이 발생한다. 코드 public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); StringBuilder sb =..

백준 2922번 크면서 작은 수 (JAVA) 문제 난이도 실버 3 알고리즘 분류 문자열 브루트포스 알고리즘 백트래킹 풀이 주어진 수를 모두 이용하여 새로운 수를 만들기(자리 수를 유지해야한다.) 주어진 수를 모두 이용하기 때문에 순열을 생성한다. 주어진 수보다 크지만 그 중 가장 작은 수를 탐색해야하기 때문에 정렬 후 순열을 생성하여 작은 값부터 탐색한다. 코드 public class Main { private static char[] split; private static int value; private static int N; private static int[] numbers; private static boolean[] visited; private static int answer; public..