프로그래머스(31)
-
[프로그래머스] [C++] 가장 큰 수 (sort)
1. 문제 정수가 담긴 배열이 주어진다. 이 정수를 전부 문자열로 덧붙인다고 할때 숫자가 최대가 되게 하여라. 2. 비교함수 작성 이 문제는 비교함수에서 정수를 to_string으로 문자열로 변환하고 문자열을 + 연산하여 사전순으로 큰지 작은지 비교할 수 있다. 이는 아스키 코드상에서 문자 '0' ~ '9' 의 상대적 크기가 숫자 0 ~ 9 와 같기때문에 가능한 일이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include #include #include using namespace std; bool comp(const int& a, const int& b) { string sa = to_string(a), sb = to_string(b); re..
2021.03.18 -
[프로그래머스] [C++] 정수 삼각형 (dp)
1. 문제 정수로 이루어진 삼각형에서 맨끝에서부터 맨아래쪽 까지의 경로들에서 거쳐간 숫자의 합중 최대값을 구하여라 2. Iterative Dynamic Programming 이 문제는 삼각형의 제일 맨 아래부터 두개의 수중 큰 수를 바로 위의 정수에 더하면 자연스럽게 triangle[0][0]에 가장 큰값이 들어가게 된다. 이것은 반복적 동적계획법으로 재귀적으로도 풀수있지만 메모리가 좀 더 소비된다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 #include #include using namespace std; int solution(vector triangle) { for(int i = triangle.size()-2; i >= 0 ; i--) for(int j = 0; j
2021.03.17 -
[프로그래머스] [C++] 조이스틱
1. 문제 조이스틱을 다음과 같이 조작하여 AA...A 에서 이름을 기록하는 최소의 조작 수를 구하여라 위 = 알파벳 다음글자 (Z->A) 아래 = 알파벳 이전 글자 (A->Z) 왼쪽 = 커서 왼쪽으로 (맨 왼쪽 => 맨 오른쪽) 오른쪽 = 커서 오른쪽으로 (맨 오른쪽 => 맨 왼쪽) 2. greedy 이문제는 그리디로 푸는 문제가 아닌것같지만 그리디 항목에 있어서 그리디로 풀었다. 그리디는 최소임을 보장하지 않는다. "CANAAAAANAN" 의 경우 최소는 48이지만 그리디한 방법 현재상태에서 최선을 선택하면 49가 나온다고한다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36..
2021.03.16 -
[프로그래머스] [C++] 소수 찾기 (brute-force)
1. 문제 0~9로 이루어진 문자열이 주어진다. 적절히 자르고 붙여서 중복되지 않은 숫자를 만드는 경우의 수 중 소수인 숫자들의 개수를 구하여라. 2. 에라토스테네스의 체와 브루트 포스(dfs) 일단 나올 수 있는 최대 숫자까지 모든 숫자에대해 소수인지 아닌지 판별하여 전역 변수에 기록하였다. 이것은 에라토스테네스의 체의 알고리즘으로 소수를 판별하였다. 그 후 입력으로 주어진 문자열을 가공하여 0~9의 개수를 담은 배열을 만들었다. 이렇게 배열을 만들고 dfs를 하게되면 한번의 실행에 0~9를 탐색하지만 중복된 숫자를 따로 처리하지 않을 수 있다. dfs로 다른 숫자들을 붙여나가며 소수인지를 판별해나가며 개수를 카운트한다. 3. 코드 아쉬운점: 함수명을 dp로 한점 1 2 3 4 5 6 7 8 9 10 ..
2021.03.16 -
[프로그래머스] [C++] N으로 표현 (dp)
1. 문제 이 문제는 N 과 number가 주어진다. 이때 N은 1~9 의 수이며 11, 222, 3333, 33 , 444, 8 등과 같이 N을 여러개 이어붙인거에 덧셈 곱셈 뺄셈 나눗셈하여 number를 만드는 최소 N의 개수를 구하는 문제이다. 2. 문제 변형 주어진 N을 x라 할때 다음과 같은 배열을 만들어 조합탐색해나가면 문제를 해결할 수 있다. [ x, xx, xxx, xxxx, xxxxx, xxxxxx, xxxxxxx, xxxxxxxx ] 이 배열 원소들이 그래프의 정점이라고 가정하고 간선은 연산이라고 생각하여 dfs를 돌리면 답을 얻을 수 있다. 이때 그래프의 형태는 한정점에서 한정점까지 4개의 방향간선이 뻗어나가, 간선의 개수가 많아진다. 이를 암시적 그래프 형태로 표현하여 간선을 신경쓰..
2021.03.15 -
[프로그래머스] [C++] 디스크 컨트롤러 (heap)
1. 문제 디스크에 작업요청이 들어온다. 이때 작업이 들어오는 시간과 수행되는 시간이 주어질 때 모든 작업의 요청부터 종료까지의 최소 평균을 구하여라. 2. 최소 힙, 그리디 증명 이 문제는 그리디한 방법으로 해결할 수 있다. 무조건 실행할 수 있는 작업중에서 가장 수행시간이 짧은것을 수행하는 것이다. 이것의 증명은 다음과 같이 할 수 있다. 만약 수행할 수 있는 작업 a , b, c, d 가 있다고 하자 이때 만약 작업시간이 가장 긴 a를 수행하게 되면 시작시간과 상관없이 b, c, d 가 기다리는 시간이 a의 긴 수행시간을 더해서 기다려야하기 때문에 전체 평균은 증가할 수 밖에 없는 것이다. 반대로 만약 작업시간이 가장 짧은 b를 수행하게 되면 나머지들의 대기시간도 짧아지고, 전체 평균은 이것을 선택..
2021.03.11