알고리즘48 백준 BOJ 1085번 코드 import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int x = in.nextInt(); int y = in.nextInt(); int w = in.nextInt(); int h = in.nextInt(); int minX = Math.min(x, w-x); int minY = Math.min(y, h-y); System.out.println(Math.min(minX, minY)); } } 2022. 8. 9. 백준 BOJ 1012번 접근 방법 인접한 배추들을 그래프 형태로 생각하면, DFS와 BFS를 사용하여 문제를 풀 수 있다. DFS, BFS 둘다 그래프를 탐색하는 방법이다. 그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조다. 그래프를 탐색한다는 것은 하나의 정점으로부터 차례대로 모든 정점들을 한번씩 방문하는 것을 말한다. 그 중에 먼저 DFS부터 알아보자 깊이 우선 탐색 ( DFS, Depth-First Search ) → 최대한 깊이 내려간 뒤에 더이상 깊은 곳이 없으면 옆으로 이동한다. 위의 사진처럼 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 브랜치로 넘어가기 전에 현재 탐색 중인 브랜치를 완벽하게 탐색하는 방식이다. 예를 들어, 미로찾기를 할 때 최대한 한 방향으로 갈 수 .. 2022. 8. 9. 백준 BOJ 1003번 접근 방법 겉보기에는 매우 단순해보인다. 그냥 피보나치 함수에서 0, 1이 출력될 때 카운트만 해주면 될 것 같지만, 시간 초과로 오답이다. 이 문제는 Dynamic Programming 줄여서 DP를 사용해야 한다. (다른 블로그를 보니 재귀함수로 푸는 방법도 있더라) 일단 이번에는 DP에 대해서 알아보자. Dynamic Programming (DP) DP는 기본적으로 주어진 큰 문제를 작은 문제로 나누어서 풀되, 반복되는 연산을 줄이는 방법이다. DP의 접근 방식은 기본적으로 분할 정복 알고리즘과 비슷하다. DP를 사용하는 알고리즘도 주어진 문제를 작게 나누어 각 작은 문제의 답을 계산하고, 이를 이용해 본 문제의 답을 계산하기 때문이다. 분할정복과 차이는 반복되는 문제를 한 번만 푼다는 점이다. D.. 2022. 8. 1. 백준 BOJ 1018번 접근 방법 체스판 크기에 상관없이 가장 적게 칠할 수 있는 8 x 8 크기를 찾아야 한다. 경우의 수는 (가로칸 개수 - 7) x (세로칸 개수 - 7) 첫번째 칸이 검은색일 경우, 하얀색일 경우가 있다. → 결과적으로 경우의 수는 2 X (가로칸 개수 -7) X (세로칸 개수 - 7) 모든 경우의 수를 탐색해서 최소를 찾아야 하므로 Brute force 방식을 사용해야 한다. Brute force 브루트 포스 완전탐색 알고리즘으로, 가능한 모든 경우의 수를 탐색하면서 조건에 맞는 결과를 가져온다. brute force 방식의 기본적인 접근 방법은 해가 존재할 가능성이 있는 모든 영역을 탐색하는 방법이다. 장점 알고리즘을 설계하고 구현하기 쉽다. 예외 없이 100% 정답을 찾아낼 수 있다. 단점 당연하게.. 2022. 8. 1. 이전 1 ··· 9 10 11 12 다음
