알고리즘/프로그래머스(30)
-
[프로그래머스] [C++] 기능개발 (stack, queue)
1. 문제 기능들을 개발하려고한다. 각 기능은 각각 먼저 빌드되어야하는 기능들이 있으며 빌드 되어야하는 순서대로 벡터에 진도율(최대100%)이 주어지고 하루에 진행하는 퍼센트가 주어질때 한번에 빌드되는 기능의 개수들을 담은 벡터를 리턴하여라 2. stack, queue 빌드 되어야하는 순서대로 벡터가 주어지니 이것의 첫번째 원소를 큐의 front, 스택의 top으로 보고 문제를 풀어도 상관없다. 100%까지 진행하도록 time을 설정하고 다음 원소들 중 100%가되는 모든 원소를 pop하면 문제가 해결된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include #include #include using namespace std; vec..
2021.03.23 -
[프로그래머스] [C++] 입국심사*** (binary search)
1. 문제 심사하는 직원들은 각각 심사하는데 시간이 전부 다르다 이 시간들의 배열이 주어지고 입국 심사해야하는 사람의 수 n이 주어진다. 이때 모든 사람을 심사했을때 걸리는 최소의 시간을 구하여라. 2. 큐를 활용한 풀이 => 시간 초과 이는 그리디 적으로 풀 수 있다. 모든 사람이 가장 빨리 끝나는 심사 위원을 선택만 하기만하면된다. 따라서 모든 시간을 우선순위 큐에 넣어놓고 n번을 그리디적으로 선택 하는 것이다. 그 후 가장 긴 시간을 찾으면 된다. 이는 nlogn 으로 입력이 아주 큰 문제이므로 시간초과가 나오게 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include #include #include #include us..
2021.03.23 -
[프로그래머스] [C++] 위장 (map)
1. 문제 [의상 이름, 의상 종류] 로 이루어진 배열이 주어진다. 이때 입을 수 있는 모든 경우의 수를 구하여라 단, 의상은 하나이상 입어야한다, 모든 종류를 다 입지 않아도 된다. 2. unordered_map 이 문제는 의상의 종류를 해쉬맵에 넣으면 간단하게 해결할 수 있다. 의상의 종류를 키로, 값을 한 종류의 의상들의 개수로 설정하면 다음과 같은 점화식을 유도할 수 있다. answer = Π(map[key[i]] + 1) -1 여기서 +1 은 입지않은 경우를 나타내고 -1은 전부 입지 않은 경우를 나타낸다. 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 #include #include #include using name..
2021.03.21 -
[프로그래머스] [C++] 순위 (shortest path)
1. 문제 대결 결과 일부가 주어진다. 이 대결 결과는 선수들의 절대적인 실력에 의해 결정된다. (실력이 더 좋다면 무조건 이김) 확실한 순위를 알 수 있는 선수들의 수를 반환하는 프로그램을 작성하여라. 2. 최단거리 이 문제는 모든 쌍의 경로를 구하는 문제이다. 모든 쌍 알고리즘 중에서 유명한 플로이드 알고리즘이나 단일 쌍 알고리즘을 V번 돌리는 알고리즘을 이용하여 문제를 해결 할 수 있다. 3. V * dfs 이 문제는 가중치가 없으므로 그냥 dfs를 V번 반복하였다. dfs에서 해당경로를 갈 수 있음을 보여줄 수 있게 src를 함수 매개변수에 추가적으로 넣었다. 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..
2021.03.20 -
[프로그래머스] [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