Problem Solving1214 [백준] 9095 1, 2, 3 더하기 - Dynamic Programming / Java • 문제 링크 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net • 풀이 과정 규칙성을 발견하기 위해 n이 1 ~ 4 일 때 1, 2, 3 의 합으로 나타내는 경우의 수을 표현하면 아래와 같다. n = 1 (1) n = 2 (1 + 1) (2) n = 3 (1 + 1 + 1) (1 + 2) (2 + 1) (3) n = 4 (1 + 1 + 1 + 1) (1 + 1 + 2) (1 + 2 + 1) (2 + 1 + 1) (2 + 2) (1 + 3) (3 + 1) 위와 같이 n = 4 일 때 모든 경우의 수는 1 ~ 3 의 모든 경우의 수를 포함한다. 이에 대한 점화식을 dp 배열을 활용한 코드에 적용하면 dp[i] .. 2022. 7. 18. [백준] 11726 2×n 타일링 - Dynamic Programming / Java • 문제 링크 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net • 풀이 과정 문제에서 제시된 직사각형의 세로의 길이는 2로 고정되어 있으므로 가로의 길이만 고려하여 점화식을 구한다. 즉 n 을 1 또는 2의 합으로 나타내는 방법의 수를 구하는 문제로써 예시를 나타내면 아래와 같다. 2 = (1 + 1) (2), 3 = (1 + 1 + 1) (1 + 2) (2 + 1), 4 = (1 + 1 + 1 + 1) (1 + 1 + 2) (1 + 2 + 1) (2 + 1 + 1) (2 + 2) 이때 4를 만드는 경우의 수는 2의 모든 경우의 수.. 2022. 7. 17. [백준] 1463 1로 만들기 - Dynamic Programming / Java • 문제 링크 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net • 풀이 과정 1 ~ n 까지의 각각의 수를 문제에 제시된 조건에 맞는 연산을 하여 최소 연산이 되는 횟수를 저장할 dp 배열을 n + 1 의 크기로 생성한다. i가 1 ~ 10 의 범위일 경우 i - 1, if (i % 2 == 0) i / 2, if (i % 3 == 0) i / 3 의 연산 중 최소 횟수의 연산을 각각의 dp 배열 인덱스에 저장하면 아래와 같다. 0 1 2 3 4 5 6 7 8 9 10 11 0 0 1 1 2 3 2 3 3 2 3 - 예를 들어 n = 6 일 경우 문제에 제시된 3가지 연산이 모두 가능하며, i - 1 = 6 - 1 = 5,.. 2022. 7. 16. [백준] 2644 촌수계산 - Graph Theory / Java • 문제 링크 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net • 풀이 과정 문제에 제시된 촌수는 연결 요소에서 특정 두 정점 간 도달하기 위한 간선의 개수를 의미한다. 정점의 개수, 거리를 계산할 두 정점, 그리고 무향 그래프 정보를 입력받아 인접 리스트로 구현한다. 시작 정점을 지정해 dfs 탐색을 수행할 함수에 매개변수로 전달하고, 간선을 따라 이동한 횟수를 나타낼 cnt 변수를 매개변수로 0으로 초기화하여 생성한다. 방문 여부를 확인하는 boolean 배열을 활용하여 연결된 모든 정.. 2022. 7. 15. [백준] 11403 경로 찾기 - Graph Theory / Java • 문제 링크 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net • 풀이 과정 모든 정점에서 모든 정점으로의 최단 거리를 구하고 정점의 개수가 1 ≤ N ≤ 100 수준이므로 플로이드 와샬 알고리즘을 활용하여 풀이한다. 기본적으로 거쳐가는 정점을 기준으로 최단 거리를 구하며 거쳐가는 정점이 k 일 경우 i 에서 j 로 도달하는 거리와 i 에서 k를 거쳐 k 에서 j 로 도달하는 거리는 같다는 전제를 둔다. 즉 k, i, j 의 3중 for문 내에서 arr[i][k] == 1 && arr[k][j] == 1 인 경우에만 arr[i][j] = 1 로 모든 정.. 2022. 7. 14. [백준] 2667 단지번호붙이기 - Graph Theory / Java • 문제 링크 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net • 풀이 과정 0 과 1을 입력받아 단지의 형태를 나타내는 2차원 배열을 생성하고 전체 노드를 탐색하여 0 이 아닌, 즉 방문 가능한 노드를 시작 노드로 하나의 연결 요소로써 탐색한다. 배열의 범위 내의 연결된 노드의 값이 1인 위치을 찾아가며, 방문한 위치마다 0 으로 변경하고 cnt 변수에 1을 더하여 해당 연결요소의 방문한 모든 노드의 개수를 반환한다. 반환한 값은 List 자료구조에 저장되며 최종적으로 연결 요소의 개수를 의미하는 list.s.. 2022. 7. 13. 이전 1 ··· 187 188 189 190 191 192 193 ··· 203 다음
