프렌즈4블록 입풀력 예제 m=4 n=5board : ["CCBDE","AAADE","AAABF","CCBBF"]answer : 14 풀이과정mXn 길이를 처음에 4블록인 것을 확인하기 위해서 높이는 m-1까지 , 폭은 n-1까지 확인해서 해당 위치에 오른쪽 아래쪽, 대각선 위치랑 같은 지 확인을 해서 전부 같으면 블록을 내리면 된다. 4블록이 완성이 되면 visit[n][m] 확인 배열을 이용해서 체크해둔다.그리고 제거할때마다 visit가 true이면 answer를 증가시키고 위에서 한칸씩 내리는 방법을 이용했다.내릴 때 1칸씩 내리기 때문에 효율은 굉장히 나쁘지만 구현할 때 매우 편하다. 그리고 내리면서 빈 공간은 0으로 저장시키면서 board가 0일때는 그냥 무시하게 만들어야 했다. 소스코드 #inc..
다트 게임 입출력 예제 dartResult : 1S2D*3Tanswer : 37 풀이 과정저는 이 문제를 문제 과정 그대로 따라가듯이 했습니다 숫자를 읽어 들이고 그다음 문자를 읽고 스타상일 때 과정, 아차상일 때 과정 둘다 존재하지 않을 때 과정을 따로 if문을 이용해서 문제를 해결해나갔습니다.c++에서 string에서 int로 바꾸는 방법은 stoi()함수를 이용해서 정수형으로 사용할 수 있습니다.그리고 flag를 이용해서 첫번째 스타상일 때 처리를 하려고 만들었습니다. 이것때문에 다른 아차상과 보너스가 없을 때도 flag를 처리해야 해서 코드가 길어져버렸네요. 너무 많아서 flag를 내려도 되겠지만 처음 구현했을 때여서 수정을 하지 않았습니다.각 숫자마다 계산이 되면 vnumber라는 배열에 저장을..
캐시 입출력 예제cacheSize : 3 cities : [ "Jeju","Pangyo","Seoul","NewYork","LA","Jeju","Pangyo","Seoul","NewYork","LA" ]return : 50 풀이과정문제에서의 조건은 LRU입니다. 최근에 사용된 것을 교체시켜야 합니다 일단 cacheSize만큼 공간을 만들기 위해 배열로 만들고 캐쉬의 사용 순서를 알기 위한 배열을 또 만들었습니다.그다음 cities를 한개씩 풀러오면서 캐시에 내용이 존재하지 않으면 값을 집어넣고 사용 순서는 count라는 숫자로 그냥 1개씩 늘렸습니다.count가 높을 수록 최근에 사용된 캐시라는 것으로 이용해서 캐시 사이즈가 꽉찼을 경우 count가 가장 큰 것을 바꾸는 방법을 이용해서 값을 구했습니다...
비밀지도 입출력 예제n : 5arr1 : [9,20,28,18,11]arr2 : [30,1,21,17,28]return : ["#####","# # #","### #","# ##",'#####"] 문제해설이번 문제를 풀려면 비트연산인 | 연산을 이용하면 바로 내가 원하는 값이 나오고 그것을 2진수로 바꾸는 과정을 이용해서 해결할 수 있습니다. 저는 string에 5개의 공간을 공백으로 만들고 2로 나누면서 나머지가 존재하면 뒤에서부터 #을 채우는 방식으로 2진수로 만들었습니다. 소스코드#include #include using namespace std; vector solution(int n, vector arr1, vector arr2) { vector answer(n); for (int i = 0; ..
문제 설명도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요. 해결 방법동그랗게 배치되어 있기 때문에 배열의 첫번째 집이 만약 훔친다면 마지막 집은 훔칠수 없습니다. 그리고 첫번째 값이 훔치지 않았다면 마지막 집을 훔칠 수 있습니다.이 2가지 경우를 고려하면서 문제를 풀어나갔습니다.인접한 집이 아닐 경우는 자신의 위치에서 1칸 띄거나 2칸 띌 수 있습니다. 이를 이용해서 동적계획으로 N번째의 집까지 훔..
문제 설명 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정합니다. 1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정합니다.2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정합니다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정합니다. 예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150일 때, 상한액을 127로 잡으면 위의 요청들에 대해서 각각 1..
문제 설명 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다. 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.입출력 예routes : [[-20,15], [-14,-5], [-18,-13], [-5,-3]]return : 2 해결 방법저는 우선순위 큐에서 가장 첫번째로 진출되는 순간에 단속카메라를 설치하는 방식으로 했습니다. 처음에 routes를 진입 지점을 기준으로 정렬 합니다. 입출력 예를 들면[[-20,15], [-18,-13], [-14,-5], [-5,-3]]이런..
문제 설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.입출력 예 n : 4costs : [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]return : 4 해결 방법costs에서 나와 있는 것을 이용해서 행렬을 만들었습니다. 그리고 가장 짧은 것을 구합니다.입출력 예에서 가장 짧은 것은 0, 1번째 섬의 다리 길이는 1입니다. 그리고 0,..
문제 설명Leo가 본 카펫에서 갈색 격자의 수 brown, 빨간색 격자의 수 red가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해 주세요 해결 방법저는 값들의 규칙을 찾아서 값을 구했습니다.카펫에서 가장 최소 brown와 red는 8, 1입니다.여기서 red를 늘렸을 때를 아래 표처럼 됩니다. *brown, red(가로,세로) 가로, 세로는 리턴값입니다.8,1(3,3) 10,2(4,3) 12,3(5,3) 14,4(6,3) 16,5(7,3) 18,6(8,3) 20,7(9,3) X 12,4(4,4) 14,6(5,4) 16,8(6,4) 18,10(7,4) 20,12(8,4) 22,14(9,4) X X 16,9(5,5) 18,12(6,5..
문제 설명질문한 세 자리의 수, 스트라이크의 수, 볼의 수를 담은 2차원 배열 baseball이 매개변수로 주어질 때, 가능한 답의 개수를 return 하도록 solution 함수를 작성해주세요. baseball :[[123, 1, 1], [356, 1, 0], [327, 2, 0], [489, 0, 1]]return 2 : (324, 328)해결 방법숫자 야구에서는 같은 숫자가 나오면 안됩니다. 또한 0도 안된다고 합니다.숫자 야구의 작은 경우 123과 가장 마지막 경우인 987까지를 baseball 변수와 비교해서 만족하면 값을 더하는 방식을 이용했습니다.각 숫자를 비교할 때 편하게 하기 위해 string은 [ ] 참조 방식이 가능하기 때문에 to_string함수를 이용해서 int를 string으로 ..