전체 글

카카오프렌즈 컬러링북

풀이 방법 dfs를 이용해서 연결되어 있는 영역의 갯수를 세어주었다. way배열로 상하좌우 방향을 이동하도록 하고 check로 체크한 부분인지 확인해주었다. 그림 배열의 처음부터 돌면서 check 되지 않은 부분을 dfs 돌려서 영역 크기를 구하고 최댓값을 구해주었다. 내 코드 class Solution { static int[][] way = {{1,0}, {-1,0}, {0,1}, {0,-1}}; static boolean[][] check; public int[] solution(int m, int n, int[][] picture) { int numberOfArea = 0; int maxSizeOfOneArea = 0; check = new boolean[m][n]; for(int i = 0; i..

에너지 모으기 - 16198번

내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static boolean[] visited; static int N; static ArrayList W; static int max = 0; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; N = Integer.parseInt(br.readLine()); W = new ArrayList(); st = new String..

이진 탐색 알고리즘

순차 탐색 : 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 단계마다 탐색범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2N 에 비례한다. 시간 복잡도는 O(logN)을 보장 이진 탐색은 최적화 문제를 결정 문제(예 혹은 아니오)로 바꾸어 해결하는 문제에 사용가능 예) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제 재귀 함수를 이용한 이진 탐색 예제 import java.util.*; public class Main { // 이진 탐색 소스코드 구현(재귀 함수) public static int binary..

빙산 - 2573번

풀이 방법 dfs를 사용한 방법을 생각했다. 모두 다 이어져 있으면 다시 1년 지나게 하고 이어져 있지 않으면 종료하기 위해 먼저 빙산을 녹이는 함수를 작성했다. 주변을 비교해서 녹이면 되는 함수이다. dfs는 check 배열을 만들어서 위치를 갔었는지 체크하고 0이 아닌 아무 곳에서 시작했다. 동서남북으로 확인하면서 가능한 경로인지 확인하고 연결되어 있는 갯수를 반환하게 했다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { static int N; static int M; static int[][] array; static int x, y; static boolean[][] check; public ..

크게 만들기 - 2812번

풀이 방법 스택을 사용해서 앞에서부터 넣어주면서 지금 넣는 자릿수가 앞의 자릿수보다 크면 제거하는 방법을 사용했다. 출력할땐 N-K개 까지만 출력해서 자릿수를 맞춰서 출력해주었다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseI..

짐 챙기는 숌

풀이 방법 책이 무조건 차례대로 들어가기 때문에 if문을 사용해서 차례대로 비교해주면서 넣어주면 된다. N이 0일땐 StringTokenizer를 생성하면 nullpointer 오류가 나기 때문에 그 점만 주의하면 된다. 내 코드 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine());..

전력망을 둘로 나누기

풀이 방법 트리에서 모든 전선들을 한번씩 끊어봐야겠다고 생각했다. 하나씩 끊어 보면서 한쪽의 송전탑 갯수를 세어주었다. 송전탑 수를 세기 위해 dfs를 이용한 완전탐색을 사용했다. (n - 한쪽 송전탑 갯수) = 나머지 한쪽 송전탑 갯수 (나머지 한쪽 송전탑 갯수 - 한쪽 송전탑 갯수) 를 절댓값 처리해준 뒤 가장 작은 값을 찾아주었다. 내 코드 import java.util.*; class Solution { static ArrayList graph; static boolean[] check; public int solution(int n, int[][] wires) { int answer = 100; for(int j = 0; j< wires.length;j++){ graph = new ArrayLi..

최소직사각형

풀이 방법 위클리 챌린지 8주차 문제로 보니까 간단한 문제길래 빠르게 풀었다. 명함들을 차례대로 지갑에 넣어줄때마다 회전시키면서 작은 쪽으로 넣어주었다. 내 코드 import java.util.*; class Solution { public int solution(int[][] sizes) { int array[] = {0, 0}; for(int i = 0;i< sizes.length; i++){ int w1 = Math.max(array[0], sizes[i][0]); int h1 = Math.max(array[1], sizes[i][1]); int w2 = Math.max(array[0], sizes[i][1]); int h2 = Math.max(array[1], sizes[i][0]); if(w1 ..

돌다리 건너기 - 2602번

풀이 방법 먼저 재귀적으로 완전탐색을 이용해서 풀었다. 하지만 시간초과가 나오고 말았다. 그래서 DP를 추가해 주었다. DP는 [현재 밟은 곳][찾고 있는 문자 인덱스][돌다리 종류] 로 나타내었다. 예제 입력 3번을 예로 들자면 GGGGRRRR GGGGRRRR GGGGRRRR GGGGRRRR SSSSGGGG SSSSGGGG SSSSGGGG SSSSGGGG 이렇게 찾은 후 다음 G에서 GGGGRRRR GGGGRRRR GGGGRRRR GGGGRRRR SSSSGGGG SSSSGGGG SSSSGGGG SSSSGGGG 똑같이 반복 될것이다. 그래서 위쪽의 돌다리에서 3번째 G를 밟은 후 현재는 아래쪽의 처음 나오는 G를 밟고 있으면 현재 밟은 곳에서 찾고 있는 문자가 인덱스와 돌다리의 종류가 같은 케이스가 나온..

괄호 제거 - 2800번

풀이 방법 각 괄호의 경우의 수를 구하기 위해 조합을 뽑아냈다. 먼저 괄호의 인덱스를 map에 저장해주고 그 인덱스르 바탕으로 조합의 경우의 수를 계산했다. 경우의 수를 바탕으로 괄호를 제거하고 출력해 주었다. 재귀 함수로 조합을 계산할 수 있다. (((0)))