우대비의 블로그

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr A도둑괴 B도둑이 물건을 훔치려고 합니다. 물건을 훔칠 때 생기는 흔적의 양을 배열로 받고, A도둑이 경찰에 붙잡히는 최소 흔적 개수 N과 B 도둑이 경찰에 붙잡히는 최소 흔적 M을 입력 받을 때, A와 B 모두 경찰에 붙잡히지 않으면서 모든 물건을 훔치는 경우중 A의 최소 흔적 개수를 구해주세요. 풀이 방법info의 길이가 40이기 때문에 완전 탐색을 하면 2^40, 약 1조개의 탐색이 발생하게 됩니다.그렇기 때문에 완전탐색으로는 문제 해결을 못할것 같지만,예외처리를 잘해준다면 완전탐색 코드로도 충분히 해결이 가능합니다. 여기서는 DFS를 사용해서 문제를..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr숫자를 입력 배열로 입력 받을 때, 숫자들을 조합해서 만들 수 있는 가장 큰 수를 구해주세요.ex) [3, 30, 34, 5, 9] => "9534330" 풀이방법해당 문제는 정렬 알고리즘 문제입니다.일반적인 정렬과는 다르게 두 원소를 이어붙였을 때, 어떤게 더 큰지에 따라 우선순위를 결정합니다.public bool Comp(int a, int b){ int A = int.Parse(a.ToString() + b.ToString()); int B = int.Parse(b.ToString() + a.ToString()); re..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 수를 strinf으로 입력 받을 때, 해당 수들을 조합해서 만들 수 있는 수 중에 소수인 것들의 개수를 구해주세요. (중복 조합 x) 풀이 방법해당 문제는 2개로 구분하여 풀이합니다. 1. 중복 없이 조합하기2. 소수인지 체크하기 우선 중복 없이 조합하는 방법을 소개하겠습니다.중복 없이 조합하는 방법public void DFS(string str = ""){ for (int i = 0; i DFS와 반복문을 조합하여 수를 조합합니다. public void DFS(bool[] visited, string str = ""){ for (int i =..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다.Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요. ex) works = [4, 3, 3], k = 4works를 [2, 2, 2]로 만들어야 최소 야근 피로도가 나옵니다. 풀이 방법야근 피로도의 공식은 아래와 같습니다.works[0] ^ works + works[1..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr높이가 1 ~ n까지인 빌딩이 2개씩 존재할 때, 은비가 바라본 방향에서는 count개의 빌딩이 보인다고 합니다. 이 때, 빌딩들이 배치될 수 있는 방법의 수를 구해주세요. (같은 높이를 가진 빌딩 사이에는 그보다 높은 빌딩이 없습니다.)  풀이 방법점화식을 찾고 풀이하는 동적 프로그래밍을 통해 해결해야합니다. DP[i, j] - 높이가 1부터 i까지 각각 2개씩 있는 빌딩을 배치할 때, j개의 빌딩이 보이는 경우의 수. 점화식은 두 가지 경우로 나뉩니다.1. 기존에 보이는 빌딩의 개수를 유지하는 경우  (dp[i-1, j] * (i-1) * 2):높이가 ..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krN * N 크기의 정사각 격자 형태의 지형이 있습니다. 각 격자 칸의 높이를 배열로 입력 받고, 사다리 없이 이동할 수 있는 높이를 입력 받습니다. 우리는 모든 지형을 연결하기 위해 사다리를 사용해야 합니다. 이 때, 사다리를 사용하여 지형을 연결할 수 있는 최소 비용을 구해주세요.(사다리의 비용은 두 격자 칸의 높이 차이가 됩니다.)  이 문제는 Union - Find 알고리즘과 크루스칼 알고리즘을 제대로 활용할 수 있는지 테스트 하는 문제입니다.Union - Find에 대해 잘 모른다면 아래 링크를 참고해주세요. 크루스칼 알고리즘과 유니온 파인드크루스칼 ..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr효진이는 한번에 1칸, 2칸을 이동할 수 있을 때, N으로 이동하는 경우의 수를 구해주세요.  풀이 방법점화식을 구해줘야 합니다. 1칸을 이동할 때는 경우의 수가 1개2칸을 이동할 때는 경우의 수가 2개3칸을 이동할 때는 경우의 수가 3개4칸을 이동할 때는 경우의 수가 5개즉 i칸을 이동할 때는 dp[i-1] + dp[i-2]칸이 됩니다. 즉,count[i] = (count[i-1] + count[i-2]) % MOD;위의 코드가 점화식이 되겠습니다. 해당 점화식을 이용하여 i가 N이 될 때 까지 반복문을 돌면 됩니다.  정답 코드public class So..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krN명의 참가자, 참가자 A, B가 있을 때, 두 사람이 만날 수 있는 라운드를 구해주세요.  풀이 방법승부는 (1, 2) , (3, 4)  (5, 6) 즉, 낮은 홀수번과 짝수번이 붙게 되며 다음 라운드에 가게 될시(1, 2)는 1번으로 (3, 4)번은 2번으로 (5, 6)번은 3번으로 가게 됩니다. 즉, 두 사람이 만났다고 할 수 있는 부분은두 사람의 번호가 (낮은 홀수번 X, X+1)일 경우 입니다.코드로 치면 아래와 같습니다.if (a % 2 == 0 && b + 1 == a) break;if (b % 2 == 0 && a + 1 == b) ..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krN개의 점으로 이루어진 트리에서 3개의 임의의 점 A, B, C를 선택합니다. 이때, A와 B의 거리, A와 C의 거리, B와 C의 거리중 중간 값을 반환하는 함수를 F라고 부를 때, 힘수 F를 통해 반환 받을 수 있는 수들 중 가장 큰 값을 구해주세요.  풀이 방법중간 값을 평균값으로 오해하면 안됩니다. 중간값은 임의의 점 3개 사이의 거리 (A->B, A->C, B->C)를 정렬 했을 때, 2번 째에 오는 수를 의미합니다. 중간 값을 찾기 위해서는 트리의 가장 큰 지름을 찾아야 합니다.  가장 큰 지름을 찾자 특정 노드에서 시작한 지름들 중 가장 큰 지름..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr1*1*1크기의 정육면체 블록으로 만들어진 지형의 상태를 입력 받습니다. 정육면체 하나를 추가하는 비용 P, 제거하는 비용이 Q일 때, 지형을 평평하게 만드는 최소 비용이 얼마인지 구해주세요.  풀이 방법기준이 되는 높이를 찾고 해당 높이와 다른 곳에 공사를 하여 평평하게 맞춰주는 비용을 반환하면 됩니다.여기서 문제가 되는 부분은, 기준이 되는 높이를 찾는 것과 높이가 다른 곳의 비용을 모두 더하는 것 입니다.이 문제를 해결하지 않으면 시간초과가 발생합니다.  높이가 다른 곳의 비용 구하기 - 누적합이 부분을 빠르게 해결하기 위해서는 누적합을 이용해야 합니다..