알고리즘56 [백준 1003]피보나치 함수 - 자바 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 1. 풀이 피보나치 수열을 재귀를 사용하여 풀때, 0과 1의 호출 횟수를 구하는 문제입니다. 피보나치의 재귀 동작 순서가 쓰여져있어서, 처음엔 피보나치 수열을 재귀적으로 풀어서 정답을 구하려다보니 시간 초과가 발생해서 DP를 사용하여 풀게 되었습니다. 우선, 피보나치의 0과 1의 호출 횟수는 아래와 같은 규칙을 가집니다. n memo[i][0] 0 호출 횟수 memo[i][1] 1 호출 횟수 0 1 0 1 0 1 2 1 1 3 1 2 4 2 3 memo[i][j] = memo[i-1][j] +.. 2020. 4. 1. [백준 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. 이전 1 ··· 6 7 8 9 10 다음
