문제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/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..
문제https://www.acmicpc.net/problem/9251 풀이LCS(Longest Common Subsequence, 최장 공통 부분 수열)는 임의의 두 수열에서 각각의 부분 수열들 중, 서로 같은 부분 수열 중에서 가장 긴 수열을 의미한다. 문제의 예제를 보면 두 수열로 ACAYKP와 CAPCAK가 있다. 각 수열의 부분 수열은 아래와 같다.ACAYKP의 부분 수열 : {A}, {C}, {A}, {Y}, {K}, {P}, {A, C}, {A, A}, ... , {ACAYKP}CAPCAK의 부분 수열 : {C}, {A}, {P}, {C}, {A}, {K}, {C, A}, {C, P}, ... , {CAPCAK}이들 중 {A}, {C}, {K}, {P}, {A, A}, ... , {A, C,..
문제https://www.acmicpc.net/problem/11053풀이이 문제는 DP 문제, LIS를 이용해서 푸는 문제이다.LIS (Longest Increasing Subsequence) : 최장 증가 부분 수열: 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 알고리즘 문제에서 주어진 수열을 보면 arr = {10, 20, 10, 30, 20, 50}이므로 수열을 담는 배열인 arr[]과 dp 값을 설정하는 배열인 dp[]를 생성한다. 그리고 수열을 입력받으면서 dp 배열의 값들을 1로 초기화한다.dp 배열을 초기화하면 각 위치에서 최소 길이는 1이다. → dp = {1, 1, 1, 1, 1, 1}i = 2일 때, arr[2] = 20이다.j = 1에서 arr[2] > arr[1]..
문제https://www.acmicpc.net/problem/9657풀이돌이 N개가 있고 상근이가 먼저 게임을 시작하며 돌을 1개, 3개, 또는 4개를 가져갈 수 있을 때 마지막 돌을 가져가는 사람이 이기는 게임이다. 문제에 '완벽하게' 라는 조건이 붙었기 때문에 상근이가 이기는 쪽으로 게임을 해야 한다. 돌의 개수 별로 돌을 가져간 횟수?를 저장하는 배열 arr을 생성한다.돌을 한 번에 4개를 가져갈 수 있기 때문에 N=1 ~ N=4까지는 고정 값을 넣어주었다.N = 1 : 상근이가 돌 1개를 가져가면 게임이 끝난다. → 상근 Win : arr[1] = 1N = 2 : 상근이가 돌 1개를 가져가고 창영이가 돌 1개를 가져가면 게임이 끝난다. → 창영 Win : arr[2] = 2N = 3 : 상근이가..
