백준
-
BOJ) 바이러스 (2606, JAVA)알고리즘/백준 2020. 8. 24. 16:39
풀이 전형적인 find - union 문제라고 할 수 있겠다. n 대의 컴퓨터가 연결되어 있고, 연결 관계가 주어진다. (그래프) 연결된 컴퓨터들 중 하나만 바이러스 걸려도 연결된 컴퓨터 모두 바이러스가 걸린다. 1번 컴퓨터가 바이러스 걸렸을 때, 몇 대의 컴퓨터가 추가적으로 바이러스 걸리는지 구하는 문제다. 풀이는 간단했다. 우선 parents 배열, find, union 메소드를 만들어 줬다. 그리고 입력을 받으면서 따로 graph에 저장하지 않고, 바로 find -union을 해줬다. 이후, 2번 ~ n번까지 컴퓨터를 돌면서 parent를 찾아 1번의 parent와 같다면 답에 더해줬다. (union할 때, 더 큰수의 parent를 작은 수로 설정해서 아마 1번의 parents는 언제나 1일것이다...
-
BOJ) 이항 계수 2알고리즘/백준 2020. 8. 8. 15:49
이항 계수 2 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 풀이 nCr 을 구하는 문제다. nCr = n-1Cr-1 + n-1Cr 이라는 공식을 저번에 이어서, 다시 한번 머리에 남기기 위해 포스팅 한다. r이 0일 때와, n일 때 1로 설정하고, 나머지 r에 대해서 위의 공식을 적용하면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public sta..
-
BOJ) 이동하기알고리즘/백준 2020. 8. 2. 00:01
이동하기 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 �� www.acmicpc.net 풀이 미로에 같힌 준규가 각 방에 놓여있는 사탕을 주워먹으면서 갈 때, 먹을 수 있는 사탕의 최대 갯수를 구하는 문제다. 이 문제는 언젠가 풀었던 것 같다. 아마 프로그래머스 문제 중 하나이지 않을까 싶다. 아무튼, dp를 이용해서 문제를 풀었다. 맵의 처음부터 x축을 순회하면서 좌측과 상단 중 사탕이 더 많은 갯수를 더해가면서 마지막 위치에 도달하게 설정했다. 이후, n, m의 dp값을 출력해서 답을 쉽게 구할 수 있었다. 코드 im..
-
BOJ) 촌수 계산알고리즘/백준 2020. 8. 1. 23:55
촌수 계산 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진� www.acmicpc.net 풀이 문제 의미대로 촌수를 계산하는 코드를 짜야한다. 다른 질문게시판을 보면 여러 알고리즘을 언급하고, 2차원 배열을 통해 푸는 것 같았다. 2차원 배열까지 갈 필요가 없다고 느껴서 1차원 배열로 풀었다. 우선 주어지는 값을, 1차원 배열에 저장했다. 저장하는 배열의 index는 자식 노드의 번호가 되고, value는 부모 노드를 입력해줬다. 부모 노드의 경우 자식 노드가 1개 이상 존재할 수 있기 때문이다. 그리고, 해당 노드들이 p..
-
BOJ) 가장 긴 감소하는 부분 수열알고리즘/백준 2020. 8. 1. 23:47
가장 긴 감소하는 부분 수열 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} � www.acmicpc.net 풀이 가장 긴 감소하는 부분 수열을 구하는 문제다. Longest Increasing Subsequence와 조건만 다른 Longest Decreasing Subsequence 문제다. LIS 문제의 조건을 반대로만 해주면 쉽게 풀 수 있다. 우선, int[] 배열 dp를 선언했다.그리고, 순회하는 인덱스의 다음 인덱스부터 n까지 돌면서 순회하고있는 인덱스의..
-
BOJ) 동전 2알고리즘/백준 2020. 7. 27. 23:57
동전 2 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주�� www.acmicpc.net 풀이 방금 전 포스팅한 LIC 문제보다 푸는데 조금 더 많은 시간이 걸렸다. 먼저, 동전 1과 다르게 k원을 만드는 최소 값을 구해야 한다는 조건이 까다롭게 느껴졌다. 또한, 만들 수 없는 경우 -1을 리턴해야한다는 부분을 간과했다. 마지막으로 고민한 부분은 점화식을 어떻게 세우는가였다. 우선 coin의 값이 뒤죽박죽일 수 있기 때문에, Arrays.sort를 통해 오름차순 정렬을 해주었다. 이후, 답이 될 dp[k]는..
-
BOJ) 가장 긴 증가하는 부분 수열 (LIS, Longest Increasing Subsequence)알고리즘/백준 2020. 7. 27. 23:51
가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 어제 푼 가장 큰 증가하는 부분수열 (BIS)와 유사한 문제다. 다른 점이 있다면, 최대 값을 구하는 것이 아니라 최대 길이를 구하는 것이다. 그래서, Math.max를 통해 값을 증가 시켰던 것과 달리, Math.max를 통해 카운트를 증가시켜준다. 먼저, 자신만 존재하는 부분 수열에 대해서 dp[n]에 1을 저장한다. 이후, 탐색을 통해 자신보다 큰..
-
BOJ) 가장 큰 증가 부분 수열알고리즘/백준 2020. 7. 26. 17:33
가장 큰 증가 부분 수열 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net 풀이 다이나믹 프로그래밍 문제는 너무 어렵다.. ㅠㅠ 다른 문제 유형보다 생각을 조금 많이 요한다. 많은 실패를 겪고 답을 찾았다. 먼저, 각 index에서 취할 수 있는 가장 큰 증가 부분 수열의 합을 저장할 dp를 선언해준다. 이후 for문을 통해 index를 탐색하면서( i ) dp[i] 에 최대값을 저장한다. 최대값을 저장하는 과정은 0부터 해당 index 전 까지 for..