본문 바로가기

코딩테스트48

[백준 9095]1, 2, 3 더하기 - 자바 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 www.acmicpc.net 1. 풀이 DP로 풀려고 노력했지만, 처음엔 규칙을 찾지못했는데, 5를 만드는 1,2,3을 더하는 경우의 수가 13임을 발견하.. 2020. 4. 1.
[백준 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.
[백준 2667]단지번호붙이기 - 자바 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net 1. 풀이 깊이 우선 탐색 ( DFS )를 통해서 그래프 상의 몇개의 갈라진 경로가 있는지 파악하는 문제라고 생각하고 풀었습니다. 2차원 배열을 사용해서 그래프의 .. 2020. 3. 30.

티스토리툴바