import java.io.*; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static boolean[][] map; static boolean[] visited; static int N, M, V; static StringBuilder sb = new StringBuilder(); static Queue queue = new LinkedList(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamRea..
1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net import java.io.*; import java.util.StringTokenizer; public class Main { static boolean[][] field; //밭 static int X, Y; //밭의 가로, 세로 static int[] dirX = {-1, 1, 0, 0}; static int[] dirY = {0, 0, -1, 1}; public static void main(String[] args) throws IOException { Buffer..
1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net import java.io.*; import java.util.StringTokenizer; public class Main { static int[][] canvas; //그림 static int N, M; //노드 수, 간선 수 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in));..
2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net import java.io.*; import java.util.StringTokenizer; public class Main { static boolean[][] graph; //그래프의 = 연결 상태를 알려줌 static boolean[] visited; //DFS로 탐색 할 때 이미 방문한 노드를 건너뛰기 위해 기록 static int N, M; // 노드 개수 & 간선 개수 static int count; //바이러스에 걸리는 컴퓨터의 수 = DFS로 접근한 노..
Greedy Algorithm 현재 상태에서 최선의 선택지를 계속해서 고르다보면, 전체적으로도 최선의 선택지가 된다. 실제로는 최선의 결과가 나올 때가 있고, 안나올 때가 있다. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1번부터 다시 반복. 프로그래머스 큰 수 만들기 아래 코드는 앞에서부터 k 범위 내의 최대값을 순차적으로 골라서 새로운 배열에 추가하는 방법이다. 그 순간의 최선의 선택인 최대값을 골라 가장 큰 결과값을 도출하였다. class Solution { public String s..
DFS: 깊이 우선 탐색 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정해 최대 깊이까지 탐색을 마친 후 다른 분기로 이동하여 다시 탐색하는 알고리즘 실제 구현 시 재귀함수를 이용하므로 스택오버 플로우(깊이가 너무 깊어질 때)에 유의해야한다. 핵심: 한번 방문한 노드를 다시 방문하면 안된다 = 노드 방문 여부를 체크할 배열이 필요하다. 시간 복잡도: O(V+E) (노드 수: V, 간선 수: E) 왼쪽 분기로 계속 들어가면서 Visit Array에 방문한 노드를 표기한다. 왼쪽 분기가 존재하지 않는다면 이전 노드의 오른쪽 분기로 넘어간다. 1,2 과정을 반복 BFS: 너비 우선 탐색 그래프의 시작노드에서 가장 가까운 노드로 탐색한다. 큐를 이용한 FIFO 방식을 활용하며 O(V+E)의 시간복잡도를 ..