백준 알고리즘(BOJ)(46)
-
BOJ_14502_연구소
1 구분: 그래프 이론, 그래프 탐색, 부르트포스 알고리즘, 너비 우선 탐색 언어: Java 전략: 1. 벽을 세울 빈칸 3개를 조합을 이용해서 선택한다. - 벽은 3개만 세울 수 있으니까 3개만 만듬 - 빈칸들 중 3개를 선택한다. 2. 조합이 완성되면 그 곳에 벽을 세우고, 바이러스를 퍼트린다. - BFS를 이용하여 전체를 다 탐색하면서 바이러스를 퍼트린다. 3. 안전 영역의 넓이를 구한다. - 바이러스가 퍼지지 않은 부분(0)의 면적(개수)을 구한다. 2. 코드 import java.util.ArrayList; import java.util.Scanner; import java.util.Queue; import java.util.LinkedList; public class Main { static ..
2021.09.29 -
BOJ_10972_다음 순열
1 구분: 수학, 조합론 언어: Java 전략: next permutation을 이용하는 문제이다 NEXT PERMUTATION - 한 순열에서 사전 순으로 다음 순열 생성 1. 배열을 오름차순으로 정렬한 후 시작한다. 2. 맨 뒤부터 탐색하여 꼭대기(가장 큰 수, i번째)를 찾는다. 3. 꼭대기 바로 앞(i-1번째)보다 큰 수를 맨 뒤에서 부터 찾는다.(j) 4. i-1과 j를 교환한다. 5. 꼭대기 위치부터 맨 뒤까지 오름차순 정렬을 한다. 6. 2~5번 과정을 반복한다. 2. 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub S..
2021.09.28 -
BOJ_12865_평범한 배낭
1. 구분: 다이나믹 프로그래밍, 배낭 문제 언어: Java 전략 0-1 knapsack문제를 이용하여 문제를 해결한다. 물건을 차례대로 고려한다(포함하거나 포함하지 않거나) - 배낭 무게 내에서 물건을 포함할지 말지 고르고, 또한 그 가치를 포함/비포함 중 더 큰 것을 선택한다. 방법이 2가지가 있다 1, 2차원 배열을 활용하여 문제를 해결 - d[i][j]: i번째 물건을 고려할 때, 가방의 무게가 j일때 최대 가치 - i 번 물건을 고려(꼭 포함해야 하는게 아니다) - i-1번에서 현재 물건 포함한 상황과, i-1번째에서 포함하지 않은 상황 중 더 큰 것을 선택한다. 2. 1차원 배열을 활용하여 문제를 해결 - d[j]: 가방 무게가 j일때 최대 가치 - 가방의 무게가 가장 최대일 때 부터 현재 가..
2021.09.27 -
BOJ_17472_다리 만들기2
1 구분: 구현, 그래프 이론, 그래프 탐색, 브루트포스 알고리즘, 너비 우선 탐색, 깊이 우선 탐색, 최소 스패님 트리 언어: Java 전략 1. 각각 섬들을 구분하기 BFS를 통해 각 섬들을 구분한다. 섬들에 숫자를 부여한다. 2. 각 섬들 간의 최소 거리 구하기 각 섬들을 하나의 정점으로 여기기 위해 각 섬들의 최소 거리를 구한다. 각 섬들에 대해 거리를 구하는데, 한 섬에 해당하는 모든 좌표를 모두 확인한다. 그래서 최소 거리를 구한다 구한 거리는 인접 행렬에 넣어 그래프 처럼 만든다. 3. MST - 최소 스패닝 트리 구하기 prim 알고리즘과 kruskal 알고리즘이 있는데 나는 prim 알고리즘을 사용했다. 2. 코드 package com.ssafy.webex; import java.util..
2021.09.24 -
BOJ_17471_게리맨더링
1 구분: BFS, DFS, 그래프 이론, 그래프 탐색, 부트포스 알고리즘 언어: Java 전략 1. 지역구 입력 받기 연결 리스트의 형태로 지역구를 받는다. - 노드와 링크를 받을 클래스를 생성하였다. 2. 지역구로 나누기 부분 집합을 구하는 방법으로 지역구 2개로 나눈다 - 부분 집합 하나만 선택하면, 포함되지 않는 것들끼리 또 하나의 부분 집합이 완성 부분 집합의 개수가 0이거나 n개일 경우는 제외한다. 3. 각 부분 집합이 연결되었는지 확인 BFS를 이용하여 각 지역구가 연결 되었는지 확인한다 - 한 점에서 다른 점까지 도달 가능하면 지역구들은 연결되어 있는 것이다. 두 지역구 각각 연결 여부를 확인해야 한다. 4. 차이 구하기 각각의 구역의 인구 수들을 구해서 차이의 최소를 찾는다. 2. 코드 ..
2021.09.24 -
BOJ_1697_숨바꼭질
1. 구분: 그래프 이론, 그래프 탐색, BFS 언어: Java 전략 1. BFS에서 탐색을 하듯 한다 - 큐 사용 2. 주로 4방 탐색인데 위치 이동이 3가지 가능함을 생각 2. 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static class Node{ int pos, time; Node(int pos, int time){ this.pos = pos; this.time = time; } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner..
2021.09.22