우대비의 블로그

프로그래머스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일 때, 지형을 평평하게 만드는 최소 비용이 얼마인지 구해주세요.  풀이 방법기준이 되는 높이를 찾고 해당 높이와 다른 곳에 공사를 하여 평평하게 맞춰주는 비용을 반환하면 됩니다.여기서 문제가 되는 부분은, 기준이 되는 높이를 찾는 것과 높이가 다른 곳의 비용을 모두 더하는 것 입니다.이 문제를 해결하지 않으면 시간초과가 발생합니다.  높이가 다른 곳의 비용 구하기 - 누적합이 부분을 빠르게 해결하기 위해서는 누적합을 이용해야 합니다..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr각 바위의 위치를 담은 배열과 목적지의 위치, 제거해야할 바위의 수를 입력받습니다. 이 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최소값 중에 가장 큰 값을 구해주세요. 풀이 방법이진탐색으로 풀이하는 문제입니다. 탐색의 기준은 [바위 사이의 거리]입니다. sort(rocks.begin(), rocks.end());int answer = 0;int left = 0;int right = distance;while (left 입력받은 배열은 정렬되어 있지 않기 때문에 sort 함수로 정렬을 해줍니다.이후 0 ~ 목적지 까지 이분탐색을 사용합니다.탐색의 기..