good_da22

백준 14502번 연구소 (JAVA) 문제 난이도 골드 4 알고리즘 분류 구현 그래프 탐색 브루트포스 알고리즘 너비 우선 탐색 풀이 주어진 빈 공간(상태가 0 인 공간) 중 3곳을 선택해서 벽을 설치한다. 벽을 설치한 후 바이러스를 인접한 상하좌우 공간으로 확산한다. 확산이 끝난 후 남은 빈 공간을 계산 코드 import java.io.*; import java.util.*; public class Main { static int[] dx = { -1, 1, 0, 0 }; static int[] dy = { 0, 0, -1, 1 }; static int N, M, answer; static int[][] map, test; static List space, virus; static boolean[][] ..

백준 14500번 테트로미노 (JAVA) 문제 난이도 골드 4 알고리즘 분류 구현 브루트포스 알고리즘 풀이 테트로미노의 크기는 4 각 위치에서 4방 탐색으로 갈 수 있는 모든 위치를 4번 탐색하는 것은 모든 테트로미노의 경우의 수(대칭, 회전)을 탐색하는 것과 같다. ㅗ, ㅏ, ㅜ, ㅓ 모양의 경우 한 방향으로 이어지지 않는다. 따라서 2번 때 탐색 시점에서 뻗어가는 경우를 계산한다. 코드 import java.io.*; import java.util.*; public class Main { static int N, M, answer; static int[][] arr; static boolean[][] visited; static int[] dx = { -1, 1, 0, 0 }; static int[]..

백준 2239번 스도쿠 (JAVA) 문제 난이도 골드 4 알고리즘 분류 구현 백트래킹 풀이 0인 경우, 숫자 1 ~ 9까지 대입 1 ~ 9 까지의 숫자중 스도쿠의 조건을 만족하는 경우(3*3, 행, 열) 해당 위치에 숫자를 대입하고 다음 단계 탐색(방문) 방문 여부를 초기화(0으로) 한 후 대입 가능한 숫자를 계속 탐색 81자리 까지 끝까지 탐색한 경우, 최초의 정답을 반환해야한다.(사전순) 처음 탐색 종료 조건(81자리 모두 탐색)을 만족하면 각 단계를 탐색하기 전에 최최 탐색 완료 여부를 확인 코드 import java.io.*; public class Main { static int arr[][]; static boolean check; public static void main(String[] a..

SWEA 4008번 [모의 SW 역량테스트] 숫자 만들기 (JAVA) 문제 풀이 각 연산자의 개수 만큼 빈 공간을 선택, 선택된 빈 공간에 연산자 대입 다음 연산자에서 앞 선 작업을 반복 동일한 연산자가 들어갈 위치를 선택하면 순서는 상관 없다. 이미 연산자가 위치한 경우 다음 연산자는 들어갈 수 없다. 코드 import java.io.*; import java.util.*; public class Solution { static char[] operator = { '+', '-', '*', '/' }; static int[] count = { 0, 0, 0, 0 }; static int[] numbers; static char[] selected..

SWEA 5656번 [모의 SW 역량테스트] 벽돌 깨기 (JAVA) 문제 풀이 구슬을 놓을 위치 결정, 중복 순열 구슬은 단위 연산에서 전후 선택과 상관없이 어느 위치에도 놓아질 수 있다. 선택된 구슬 위치에서 처음으로 만나는 벽돌 선택 처음으로 만나는 벽돌에서부터 주어진 조건에 따라 4방 탐색으로 벽돌 제거 단위 연산에서 제거 가능한 모든 벽돌을 제거한 후 빈 공간이 있을 경우 벽돌은 밑으로 떨어진다. 코드 import java.io.*; import java.util.*; public class Solution { static int[] dx = { -1, 1, 0, 0 }; static int[] dy = { 0, 0, -1, 1 }; static int N, W, H; static int[][] ..

백준 17471번 게리맨더링 (JAVA) 문제 난이도 골드 4 알고리즘 분류 브루트포스 알고리즘 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 조합론 풀이 N개의 구역 중, 1 ~ N / 2 개의 구역을 선택 N / 2 ~ N -1 개의 구역은 앞서 선택된 구역에서 선택되지 않는 경우로 따로 계산할 필요가 없다. 분리한 구역 내에서 각 그룹이 서로 연결되어 있는지 확인, 너비 우선 탐색 두 그룹 모두 각각 연결되어 있다면, 각 그룹의 인구 수를 계산 코드 import java.io.*; import java.util.*; public class Main { static int N, answer; static List adj; static int[] size; static int[] numbers; publ..

백준 16234번 인구 이동 (JAVA) 문제 난이도 골드 5 알고리즘 분류 구현 그래프 이론 그래프 탐색 너비 우선 탐색 시뮬레이션 풀이 너비 우선 탐색을 통해 전체 데이터내에서 연합의 여부를 확인 연합이 발생하는 경우, 다음 단계로 이동 연합이 발생하지 않는 경우, 종료 각 단계 내에서 너비 우선 탐색을 진행, 각 연합 내에서 새로운 인구 수 계산 단계가 끝나고 방문여부 초기화 코드 import java.io.*; import java.util.*; public class Main { static int N, L, R; static int[][] map; static int[] dx = { -1, 0, 1, 0 }; // 상, 우, 하, 좌 static int[] dy = { 0, 1, 0, -1 }..

위상 정렬 (Topology Sort) 유향 그래프의 정점들을 방향을 거스르지 않도록 나열하는 것을 의미 위상 정렬은 순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해주는 알고리즘 ex) 교육과정의 선수과목 구조 만약 특정 수강 과목에 선수 과목이 있다면 그 선수 과복부터 수강해야하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬 이용 가능 정렬 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하니 않아야 한다. 그래프가 비순환 유향 그래프(directed acyclic graph)..

최소 신장 트리 (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..