부분 집합 구하기(DFS)

부분 집합 구하기(DFS) 이번 시간에는 DFS 를 이용한 부분 집합을 구하는 방법에 대해서 배워보자. 문제 자연수 N 이 주어지면 1 ~ N 까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요. 단, 공집합은 출력 하지 않습니다. 입력 3 출력 1 2 3 1 2 1 3 1 2 3 2 3$$원소의 개수가 N 인 부분집합의 개수 : 2^n$$ $$공집합을 제외한 부분집합의 개수 : 2^n-1$$ 루트 노드부터 보면, 1을 포함하는 경우 하지 않는 경우로 나누고, 2 depth 에서는 원소 2를 포함하는 경우 하지 않는 경우로 나눌 수 있다. 따라서, N 만큼의 반복을 돌고 depth 가 N + 1 이 되는 경우 종료된다. 구현 public class Main { private stat..

깊이 우선 탐색(DFS)

깊이 우선 탐색(DFS) DFS(Depth-First Search) 는 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS 는 Stack 자료구조를 사용하며 Stack 을 이용하기 때문에 재귀 함수를 이용하면 쉽게 DFS 구현을 할 수 있다. 재귀와 Stack 에 대해서 잘 모르겠으면 해당 링크를 통해서 배우고 오자. 동작 과정 Step1 Step1. 시작 노드를 스택에 넣고 방문 처리한다. Step2 Step2. 방문하지 않은 인접 노드 중에서 번호가 가장 낮은 곳을 방문하고 해당 노드를 스택에 넣어 방문 처리 한다. Step3 Step3. 위 과정을 반복한다. 구현 public class Main { public static boolean[] visited ..

[BOJ 16234] 인구 이동

인구 이동 BOJ 16234 : 인구 이동 해설 이 문제는 2차원 배열의 탐색 문제이기 때문에 좌표 형태를 그래프로 바꿔야 한다는 생각을 먼저 하였다. 문제의 입력 예시 4번을 가지고 해설할 것이다. 입력 N : 3, L : 5, R : 10 3 5 10 10 15 20 20 30 25 40 22 10 L 인구 이동이 불가능 할 때 까지 반복 구현 class Country { private int x; private int y; public Country(int x, int y) { this.x = x; this.y = y; } public int getX() { return x; } public int getY() { return y; } } public class Main { private stati..

[BOJ 1715] 카드 정렬하기

카드 정렬하기 BOJ 1715 : 카드 정렬하기 해설 구현 public class Main { private static int N; private static PriorityQueue pQ = new PriorityQueue(); public static void main(String[] args) { input(); solution(); } private static void input() { Scanner sc = new Scanner(System.in); N = sc.nextInt(); for (int i = 0; i ..

[BOJ 18352] 특정 거리의 도시 찾기

특정 거리의 도시 찾기 BOJ 18352 : 특정 거리의 도시 찾기 해설 다익스트라 알고리즘 사용을 눈치 챘다면, 풀이는 쉽다. 구현 class Node implements Comparable { private int vertex; // 정점 private int cost; // 비용 public Node(int vertex, int cost) { this.vertex = vertex; this.cost = cost; } public int getVertex() { return vertex; } public int getCost() { return cost; } @Override public int compareTo(Node o) { return this.cost - o.cost; // 비용이 낮을 수록..

[BOJ 3190] 뱀

뱀 BOJ 3190 : 뱀 해설 처음에 이 문제를 풀 때, 제 시간에 풀지 못했다. 꼬리, 몸통, 머리 부분이 이해가 잘 안갔었는데 이 부분에 대한 해설은 다음과 같다. # 꼬리, 몸통, 머리 예를들어 뱀이 (0, 0)에서 시작해서 계속 사과를 먹으며 우측으로 이동해 (0, 3)까지 간 상태라면 queue = (앞=꼬리) { (0,0), (0,1), (0,2), (0,3) } (뒤=머리) 가 된다. 사과를 못 먹어서 꼬리부분을 당겨야 되는 상황이라면 꼬리 위치의 값을 빈 값으로 설정하면 된다. 이 문제의 핵심은 Queue 를 사용한다는 것을 빨리 눈치 채야하는 것 같다. 그리고 나머지는 구현 문제 답게, 문제에 나와있는 조건들에 따라 차근차근 구현하면 되는 것 같다. Strategy 전략(Strategy..

이것이 코딩 테스트다 : 모험가 길드

모험가 길드 책 이것이 코딩테스트다의 모험가 길드 문제풀이 해설 몇 가지 케이스를 만들어서 오름차순(Asc) 와 내림차순(Desc) 기준으로 구분을 해봤다. 마지막 Case4 를 보면 오름차순으로 정렬되었을 때 그룹 수의 최댓값을 구할 수 있는 것을 알 수 있다. 그리고 파란색으로 밑줄친 부분이 조건문이 필요하다는 핵심적인 부분이다. 저부분을 통해 어떤식으로 조건문을 짜면 되는지 힌트를 얻을 수 있다. 구현 public class Main { private static int N; private static int[] fear; private static int group; public static void main(String[] args) { input(); greedy(); System.out.pr..

[BOJ 18406] 럭키 스트레이트

럭키 스트레이트 BOJ 18406 : 럭키 스트레이트 구현 public class Main { private static String N; private static int left = 0; private static int right = 0; public static void main(String[] args) { input(); solution(); } private static void input() { Scanner sc = new Scanner(System.in); N = sc.nextLine(); } private static void solution() { String[] numbers = N.split(""); int middle = numbers.length / 2; for (int i ..