Algorithm PS/Baekjoon Online Judge

문제https://www.acmicpc.net/problem/24480풀이이 문제는 그래프의 정점을 입력받아서 해당 정점들만 탐색하면 되므로 인접 리스트를 사용하는게 적절하다고 판단했다. 이번에는 이중 ArrayList를 사용하여 풀어봤다. 그래프의 내용을 저장할 ArrayList> graph를 만들어서 간선 정보를 입력받는다. 그리고 DFS를 이용하여 시작 정점에서 탐색을 시작한다. 각 정점을 방문할 때, 방문한 순번을 배열에 저장하고, DFS 탐색이 끝나면 저장했던 순번을 출력한다. 매우 사소한 실수로 메모리 초과가 발생했다...Codeimport java.io.*;import java.util.*;/*- 정점과 간선의 정보를 이용해서 출발 정점에서 각 정점을 방문하는 순번을 결과로 출력한다.- 시작..

문제https://www.acmicpc.net/problem/1012풀이graph를 생성하여 값들을 모두 입력 받고, for문으로 graph를 탐색하면서 graph의 현재 위치가 1(배추)이며, visited(방문하지 않은 곳)의 값이 false이면, dfs 또는 bfs를 실행하여 해당 지점을 기준으로 연결된 부분들을 방문처리하고 애벌래 개수를 증가시킨다. Dfs와 Bfs 모두 풀이가 가능하여 두 가지 방법으로 풀어보았다.CodeDfs 적용 (주석 변경으로 Bfs로도 적용 가능)import java.io.*;import java.util.ArrayDeque;import java.util.StringTokenizer;public class Main { static int T, M, N, K; s..

문제https://www.acmicpc.net/problem/1620풀이오박사 : 그럼 다솜아 이제 진정한 포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라. 일단 네가 현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라. 나의 시험을 통과하면, 내가 새로 만든 도감을 주도록 하겠네. N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력을 받고, 입력받은 후에는 M개의 줄에 내가 맞춰야하는 문제가 입력으로 들어온다. 문제가 알파벳으로만 들어오면 포켓몬 번호를 말해야 하고, 숫자로만 들어오면 포켓몬 번호에 해당하는 문자를 출력해야 한다.  즉, HashMap 형태롤 ..

문제https://www.acmicpc.net/problem/1926풀이그림의 개수와 넓이가 가장 넓은 그림의 넓이를 출력해야 한다.graph를 순회하면서 1(색칠이 칠해진 곳, 그림의 시작점)을 만나면, 해당 위치의 visited[][](방문 여부)를 확인하고 방문한 적이 없으면 bfs()를 실행하여 동서남북으로 연결된 칸수를 방문처리하고, 연결된 1의 개수를 area 리스트에 추가한다. 추가로 bfs() 횟수를 ++하여 그림의 개수를 파악한다.graph의 모든 지금을 방문하였다면 area 리스트를 정렬하여 가장 큰 값을 출력한다.Codeimport java.io.*;import java.util.*;public class Main { static int n, m; static boolean..

문제https://www.acmicpc.net/problem/2667풀이graph를 탐색하면서 방문하지 않은 집(visited[i][j] == false)이면서, 집이 있는 곳(graph[i][j] == '1')이면 해당 집을 시작점으로 bfs()를 실행하면서 해당 집을 기준으로 동서남북을 탐색한다. 해당 집의 동서남북에 방문하지 않은 집이면서, 집이 있어야하고, graph 범위 내에 있다면 위치를 최신화하고 방문처리(visited[i][j] == true) 하는 방식으로 진행한다. bfs()를 실행한 결과인 단지 내 아파트 개수를 aptCnt 리스트에 저장하고, bfs()가 실행된 횟수를 cnt++을 하여 groupCnt에 저장하여 출력을 한다.Codeimport java.io.*;import java..

문제https://www.acmicpc.net/problem/6118풀이Codeimport java.io.*;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Arrays;import java.util.StringTokenizer;public class Main { static ArrayList[] adjList; // 인접 리스트를 저장할 배열 static int N, M; static int[] distance; // 1번 헛간부터 각 헛간까지의 거리를 저장할 배열 public static void main(String[] args) throws IOException { Buffered..

문제https://www.acmicpc.net/problem/2660풀이Codeimport java.io.*;import java.util.*;public class Java { static ArrayList[] graph; static int[] distance; static Map resultDis; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(Syste..

문제https://www.acmicpc.net/problem/5567풀이Codeimport java.io.*;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Arrays;import java.util.StringTokenizer;public class Main { static int N, M; static int[] distance; static ArrayList[] graph; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader..

문제https://www.acmicpc.net/problem/11726풀이규칙만 찾아면 피보나치 수열인 것을 알 수 있다.Codeimport java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(br.readLine()); bw.writ..

문제https://www.acmicpc.net/problem/1788풀이피보나치 수열을 변형한 문제로 규칙을 구하면 쉽게 풀 수 있다. n의 값이 짝수이며 음수인 경우, 결과값이 음수로 나온다. n의 값에 대한 F(n)의 결과의 절대값은 n이 음수일 때와 양수일 때가 동일하다.Codeimport java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputSt..