Study-Note

[Java] 2667 - 단지번호붙이기 [문제] 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. [풀이] 대표적인 DFS, BFS로 풀 수 있는 문제이다. DFS가 더 익숙해서 DFS로 풀었다. 주어진 2차원 배열을 DFS로 탐색하면서 1일 경우 단지수가 존재함(count)을 ..

스택 사용하기 10828. 스택 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Stack; import java.util.StringTokenizer; public class BOJ_10828 { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int N = Integer.parseInt(br.readLine()); Stack stack = new Stack(); for(int i=0; i

그리디(탐욕) 알고리즘 응용하기 11047. 동전 0 동전 개수의 최소값을 찾아야하므로 최선의 선택은 가장 큰 금액에서부터 빼는 것 import java.io.BufferedReader; import java.io.InputStreamReader; public class BOJ_11047 { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] input = br.readLine().split(" "); int N = Integer.parseInt(input[0]); int K = Integer.parseIn..

동적 계획법 기초, 응용 2748. 피보나치 수 2 시간 제한이 있으므로 동적계획법(DP) 활용해야한다. Top-Down 방식을 활용해서 풀었음. 배열을 미리 -1로 다 채워놓고, fibo 메서드를 실행시킨 다음 해당 배열에 값을 채운다. 이미 실행되어 배열에 값이 존재할 경우 그 값을 그대로 사용한다. => 메모이제이션 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) throws Exception { BufferedReader rd = new BufferedReader(new InputS..

정렬 알고리즘 기본, 응용 2750. 정렬 시간 복잡도 O(n²) (1) 선택 정렬: 배열의 앞이 줄어든다. import java.io.BufferedReader; import java.io.InputStreamReader; public class BOJ_2750 { public static void main(String[] args) throws Exception { BufferedReader rd = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(rd.readLine()); //수 입력 int number[] = new int[N]; for(int i=0; i

브루트 포스 알고리즘 응용 * 브루트 포스 알고리즘 가능한 모든 경우를 전부 만들어보는 알고리즘 2798. 블랙잭 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; public class BOJ_2798 { public static void main(String[] args) throws Exception { BufferedReader rd = new BufferedReader(new InputStreamReader(System.in)); String[] input = rd.readLine().split(" "); int N = Integer.parseInt(input[0]); int M = I..

소수, 기하 다루기 1978. 소수 찾기 * 소수: 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수 => 1과 자기 자신만을 약수로 갖는 자연수 ex) 2, 3, 5, 7, 11 ... import java.io.BufferedReader; import java.io.InputStreamReader; public class BOJ_1978 { public static void main(String[] args) throws Exception { BufferedReader rd = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(rd.readLine()); String[] input = rd..

BaekJoon Oline Judge - Step 8 1011. Fly me to the Alpha Centauri 규칙 찾기 너무 어려웠던 문제 🤦🏻‍♀️ import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int T = scan.nextInt(); for(int i=0; i 0) { while(distance != 0) { distance -= j; if(distance >= 0) { count++; } else { distance += j; j--; } } } System.out.println(count); } scan.clos..

BaekJoon Oline Judge - Step 8 2292. 벌집 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int N = scan.nextInt(); scan.close(); int count = 1, six = 6, index = 1; while(true) { if(N > index) { index += six; six += 6; count++; } else break; } System.out.println(count); } } 1193. 분수찾기 규칙을 찾아보자면, 홀수일 때는 분모--, 분자++이고 짝수일 때는 분..

BaekJoon Oline Judge - Step 7 11654. 아스키코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); String c = scan.next(); scan.close(); int res = c.charAt(0); System.out.println(res); } } 10809. 알파벳 찾기 배열을 -1로 모두 초기화해주고, 알파벳 소문자의 개수만큼 배열 생성 a부터 시작하므로, a의 아스키 값인 97을 뺀 곳에 문자가 처음 등장하는 index를 넣는다. 두번 등장할 때 배열을 덮어쓰면 안되기 때문에 -1일 때만..