백준 알고리즘(BOJ)(46)
-
BOJ_11725_트리의 부모 찾기
1 구분: 그래프 이론, 그래프 탐색, 트리, 너비우선탐색, 깊이 우선탐색 언어: Java 전략 루트 노드인 1부터 시작 노드들 간 연결 요소를 ArrayList배열을 이용 - 각 배열마다 ArrayList선언 필요 자신과 연결된 노드들 이 내 자식이다 부모의 번호를 담을 배열을 준비한다 나와 연결되어 있는데, 이미 부모가 설정된것(나의 부모이다). 그렇지 않은 것들의 부모를 저장 bfs: 한 노드에서 자신과 연결된 모든 노드를 바로 자식으로 여기기 때문에 2. 코드 import java.util.Scanner; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; public class Main { static ..
2021.11.19 -
BOJ_16938_캠프 준비
1 구분: 수학, 부르트포스 알고리즘, 조합론, 백트레킹 언어: Java 전략: 문제를 선택한다 - 개수는 2개 이상 -> 부분 집합을 이용해 문제를 선택하거나 선택하지 않는다 문제들의 난이도들의 합을 구한다 -> 선택된 것들을 더한다 문제들의 최상 난이도 - 최하 난이도 차를 구한다 -> 배열의 정렬을 이용하여 최대, 최소값을 구한다 조건에 맞다면 개수를 1 증가 2. 코드 import java.util.Arrays; import java.util.Scanner; public class Main { static int n, l, r, x, ans; static int[] level; static boolean[] subset; public static void main(String[] args) { S..
2021.11.12 -
BOJ_11279_최대 힙
1 구분: 자료구조, 우선순위 큐 언어: Java 전략: 우선순위 큐를 활용한다. 우선순위 큐는 작은 수부터 나오니 큰 수부터 나올 수 있도록 작업을 한다. 0의 개수만큼 숫자가 나와야 하므로, (빈 상태에서도) 일단 0을 넣고, 출력한다. 2. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.Scanner; public class Main { public static void main(String[] args) throws NumberFormatException, IOException { Buf..
2021.11.11 -
BOJ_16987_계란으로 계란치기
1 구분: 브루트포스, 백트레킹 언어: Java 전략 1. DFS를 이용하여 칠 순서대로 계란을 찾는다 2. 손에 든 계란이 깨져있다면 pass 3. 깨려는 계란이 손에 든 계란이라면 pass 4. 계란을 치고, 깨진 계란이 있다면 깨진 것들 개수를 더한다. 재귀를 부른다 5. 다시 원상 복구를 한다(DFS의 특징) 6. 맨 오른쪽 계란을 잡고 깬다면 이제 그만 7. 매번 최대값을 갱신 2. 코드 package algorithm.boj; import java.util.Scanner; public class BOJ_16987 { static class Egg{ int power; int weight; boolean state;//true는 아직 안깨진것, false는 꺠진것 Egg(int power, in..
2021.11.08 -
BOJ_20056_마법사 상어와 파이어볼
1 구분: 구현, 시뮬레이션 언어: Java 전략: 큐에 있는 것들은 이동을 할 공들 ArrayList[][]에 있을 것들 - 공이 이동하고, 여러 개의 공이 있을 수 있기 때문에 ArrayList 2차원 배열을 생성 이동 시키기 - 모듈러 연산을 이용해서 간단하게 구할 수 있다. 좌표, 질량, 속력, 방향을 가지는 자료구조를 만든다 1. 처음의 공들을 입력 받아 큐에 넣는다 - 이때 좌표 주의! 2. 큐에 있는 공들을 큐가 빌 때까지(한 번 비워지는게, 실행 1번 한것) 공을 꺼내서 이동시킨다 3. 이동: 이동한 위치 = 처음 위치 + dx[방향] * (속력%전체 칸의 수) 음수인 경우를 대비해: 이동한 위치 = (전체 칸 수 + 이동한 위치 ) % 전체 칸 수 4. 같은 자리에 여러 개가 있는 경우 ..
2021.10.23 -
BOJ_17144_미세먼지 안녕!
1 구분: 구현 언어: Java 전략 1. 먼지의 좌표와 먼지 양을 담을 클래스를 생성 2. 먼지를 큐에 담고, 4방을 탐색하며, 먼지를 확산시킨다. 단!! 먼지가 동시에 확산된다는 점을 잊지 말아야 한다 3. 공기 청정기 작동 - 하나하나 그림을 바탕으로 칸을 이동한다. 2. 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { //먼지의 좌표와 먼지를 담을 class static class Point{ int y, x, dust; Point(int y, int x, int dust){ this.y = y; this.x = x; this.dust = dust; } } stat..
2021.10.21