본문 바로가기

Tech/Problem Solving

[프로그래머스 - DFS] 네트워크 (Java) https://programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원..
[프로그래머스 - DFS] 타겟 넘버 (Java) https://programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이..
[백준 2805] 나무 자르기 (Java) https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따 www.acmicpc.net 접근 방식 이분 탐색을 이용해 접근해야 시간초과가 나지 않는다. 아무리 길게 절단한다고 해도, 최대 입력 받은 나무 길이 중 가장 긴..
[백준 2217] 로프 (Java) https://www.acmicpc.net/problem/2217 2217번: 로프 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 www.acmicpc.net 접근 방법 그리디 알고리즘으로 접근해야하는 문제이다. N개만큼 각 로프가 들 수 있는 중량을 입력 받는데 해당 로프만 사용하는 경우는 그 중량..
[백준 11057] 오르막 수 (Java) https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net 접근 방법 전형적인 DP문제라고 하는데 역시나 아직 많이 부족함을 느낀다. 2차원배열을 사용한다. dp[N][0~9]로 수의 길이가 N번일 때, 마지막 자리수가 0 ~ 9 경우의 개수를 각각 담는다. 우선 dp[1][0~9]는 모두 1로 따로 설정을 해둔다..
[백준 11052] 카드 구매하기 (Java) https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 접근 방식 이전에 풀어봤던 문제(아마도 백준 2293 동전 문제인 듯하다)와 유사한 부분이 있어서 크게 어렵지 않게 풀 수 있었던 DP문제였다. 문제에서 주어진 예시를 가지고 설명을 하고자 한다. 민규가 구매하려고 하는 카드의 개수 N = 4 P1 = 1, P2 = 5, P3 = 6, P4 = 7 n개의 카드를 갖기 위해 지불하는 금액의 최댓값을 dp[n]이라고 하자. 만약 민규가 카드 1개를 갖는다고 ..
[백준 2156] 포도주 시식 (Java) https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 접근 방법 다이나믹 프로그래밍 문제로 이전에 풀었던 백준2579 계단 오르기와 유사해서 비슷하게 접근하였다. DP[n]이 n번째 포도..
[백준 2293] 동전 1 (Java) https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 접근 방법 DP문제로 우선 점화식을 도출해야했다. 동전의 가치가 a, b, c라고 할 때 합이 k가 되도록 하는 동전의 경우의 수는 (k-a)원이 되는 경우에 a를 더한 경우, (k-b)원이 되는 경우에 b를 더한 경우, (k-c)원이 되는 경우에 c를 더한 경우로 총 3가지 경우가 있을 수 있다. 이를 점화식으로 도출하면 DP[k] = DP[k - a] + DP[k -b] + DP[k -c]가 된..

티스토리툴바