알고리즘/백준48 [백준 1463] 1로 만들기 - 자바 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1. 풀이 이 문제는 DP 점화식을 사용하여 풀이하면 된다. DP는 모든 경우의 수를 순회해야 할 때, 중복되는 순회를 빠르게 처리하기 위해 생긴 것이다. 그만큼 메모리가 차지하는 단점이 있긴하다. D[n을 1로 만드는 횟수] = (1) D[n/3을 1로 만드는 횟수] + 1 (2) D[n/2을 1로 만드는 횟수] + 1 (3) D[n-1을 1로 만드는 횟수] + 1 이 중에서 제일 작은 값을 골라서 D[n]에 저장하면 되는 것입니다. 즉 아래와 같은 코드가 됩니다. memo[n] = memo[n-1] + 1;.. 2020. 4. 1. [백준 14502]연구소 - 자바 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 1. 풀이 처음엔 dfs와 bfs로만 사용하면 풀릴 줄 알고, 조금 헤맸습니다.. 완전 탐색을 사용하여 벽을 세우면서 바이러스를 반복적으로.. 2020. 3. 31. [백준 11724]연결 요소의 개수 - 자바 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. www.acmicpc.net 1. 풀이 연결요소의 개수를 찾는 문제로, 정점의 개수만큼 루프를 돌며 방문한 적이 없는 정점이면 dfs나 bfs를 해주면서 count해주면 되는 문제입니다. 저는 dfs를 통해 풀이를 하였습니다. 2. 코드 import java.util.*; public class Main { static int[][] graph = new .. 2020. 3. 31. [백준 11403] 경로 찾기 - 자바 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 풀이 모든 정점에 대해서 i에서 j로 가는 경로를 찾는 것이 힌트라고 생각합니다. 그러므로 모든 정점에 대해서 dfs나 bfs중 하나를 선택하여 i에서 j로 가는 간선이 존재하는 곳에 1로 표시하면 됩니다. 즉, 각 정점에서 dfs나 bfs로 탐색을 진행합니다. 2. 코드 2.1 dfs import java.util.*; public class Main { public static void main(String[] args) { Sc.. 2020. 3. 31. [백준 1012] 유기농 배추 - 자바 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. ( www.acmicpc.net 1. 풀이 이 문제 역시 DFS를 통해서 문제를 풀이합니다. 주의할 점은 2차원 배열의 가로와 세로의 위치를 잘 지정해줘야하는 것입니.. 2020. 3. 30. [백준 2667]단지번호붙이기 - 자바 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net 1. 풀이 깊이 우선 탐색 ( DFS )를 통해서 그래프 상의 몇개의 갈라진 경로가 있는지 파악하는 문제라고 생각하고 풀었습니다. 2차원 배열을 사용해서 그래프의 .. 2020. 3. 30. 이전 1 ··· 5 6 7 8 다음
