Algorithm/프로그래머스9 [연습문제] 최고의 집합 int 타입의 n과 s가 주어지는데, n개의 수로 집합을 구성하여 모든 원소의 합이 s이고 모든 원소의 곱이 가장 큰 집합을 찾아내는 문제이다. 찾을 수 없다면 -1을 반환한다. n개의 수를 모두 사용해야 하기 때문에 찾을 수 없는 경우는 n이 s보다 큰 경우를 말한다. 각 원소는 자연수이여야 하기 때문에 s가 3이고 n이 5면 제일 작은 수 1로 구성하더라도 3을 넘기 때문에 불가능하다. 그리고 3, 3처럼 s와 n이 같다면 가장 작은 수 1로 구성해야 하므로 1을 n개만큼 만들어 반환하면 된다. 만약 s가 n으로 나누어 떨어진다면 n개의 수를 s/n으로 구성하면 된다. 그밖의 경우 s가 n으로 나누어 떨어지지 않는다면, 우선 s를 n으로 나눈다. 만약 예제의 9를 2로 나눈다면 몫은 4가 되고 나머지.. 2021. 9. 24. [Level 3] 섬 연결하기 각 노드를 최소 비용으로 연결시키는 문제이다. 최소 신장 트리를 만드는 Kruskal 알고리즘을 사용하면 된다. 알고리즘은 간단하다. 우선 cost를 기준으로 오름차순 정렬시킨다. i번 째 cost를 골라 두 섬이 연결되어 있는지 확인한다. 만약 연결되어 있다면(같은 그룹이라면) 다시 연결할 필요없다. 만약 연결되어 있지 않다면 (같은 그룹이 아니라면) 두 노드를 연결시키고(같은 그룹으로 표시) 해당 비용을 누적시킨다. 이를 모든 costs 요소에 대해 확인하면 된다. 여기서 핵심은 두 섬이 서로 연결되어 있는지, 같은 그룹에 있는지 확인하는 방법이다. 방법은 생각보다 간단한다. 우선 섬의 개수인 n의 크기를 가지는 int 타입 원소를 저장하는 1차원 배열을 하나 생성한다. 초기값은 모두 -1로 설정한다.. 2021. 9. 21. [Level 3] 단속 카메라 겹치지 않는 범위는 어쩔 수 없이 카메라를 1대 주고, 겹치는 영역은 최대한 겹치도록 하면 된다. 비교를 위해 먼저 시작 지점을 기준으로 오름차순 정렬한다. 그다음 반복하면서 [i]와 [i+1]의 범위를 비교하여 [i+1]의 시작 지점이 [i]의 종료 지점보다 크면 겹치지 않는 것이므로 어쩔 수 없이 카메라 1대를 주고 넘어간다. 만약 [i+1]의 시작 지점이 [i]의 종료 지점보다 작거나 같다면 1칸이라도 겹치는 것이므로 새로운 영역의 시작 지점을 [i+1]의 시작 지점으로 업데이트한다. 종료 지점은 더 작은 지점으로 업데이트한다. 다음엔 이 새로운 영역과 비교해서 겹친다면 영역을 또 업데이트하던지, 겹치지 않는다면 현재까지의 영역에 카메라를 한 대주고, 다시 반복하면 된다. #include #incl.. 2021. 9. 21. [Level 2] 큰 수 만들기 숫자로 이루어진 문자열과 k가 주어진다. 해당 문자열에서 k개의 숫자를 제외하고 만들 수 있는 가장 큰 수를 반환하는 것이 문제이다. 숫자의 순서는 바뀌면 안된다. 예를 들어 4912에서 가장 작은 수 2개를 제외 후 9와 4로 94라는 수를 조합하는 게 아니라, 순서는 유지하되 가장 큰 수의 배열인 92를 만드는 것이다. 따라서 맨 앞자리부터 값을 채운다고 할 경우, 특정 범위에서 가장 큰 값을 골라 현재 채워야 할 자리에 넣어주면 된다. 채워야 할 문자열의 길이는 (number.size - k) 이다. 예제 2의 경우 1231234에서 3자리를 제외한 4자리를 채우면 된다. 그러면 다음과 같이 빈칸을 4개 두고 맨 앞자리부터 차례대로 채운다고 생각하면 이해하기 쉽다. _ _ _ _ 그런데 단순히 모든.. 2021. 9. 20. [Level 2] 점프와 순간이동 | C++ 문제 설명 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return.. 2020. 9. 23. [Level 2] 위장 - 해시 | C++ [문제] 문제는 우선 간단하다. 얼굴, 상의와 같은 종류의 의상들이 주어지는데 그들 중 최소 1개 이상의 조합의 가지수를 구하는 것이다. 물론 같은 종류의 의상은 중복으로 착용할 수 없다. 예제를 살펴보면 첫 번째 예제의 경우 headgear 종류의 의상이 2개 eyewear에 해당하는 의상이 1개이므로 총 2개의 종류와 의상의 개수는 3개이다. 따라서 1개의 조합, 2개의 조합으로 입을 수 있으며 총 5가지의 수가 나온다. [풀이] 우선 해시맵을 이용하여 key-value 쌍을 (종류-의상들)로 저장한다. 예를 들면 "face" - ["crow_mask, "blue_sunglasses, ...]와 같은 식이다. 이렇게 분류한 뒤 종류 별로 조합하여 가능한 경우의 수를 모두 구하면 된다. 이 부분이 핵심.. 2020. 5. 28. 이전 1 2 다음
