프로그래머스(31)
-
[프로그래머스] [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 -
[LeetCode] [Medium] ZigZag Conversion
1. Problem "PAYPALISHIRING" => "PAHNAPLSIIGYIR" Given a string and row of zigzag pattern. return a zigzag pattern string for line by line. 2. Sol1 store in order => each row a vector. and sum all vector 0~numRows-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 27 class Solution { public: string convert(string s, int numRows) { if(numRows == 1) return s; vector answer(numRo..
2021.03.21 -
[프로그래머스] [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++] 네트워크 (dfs)
1. 문제 컴퓨터의 네트워크가 몇개가 있는지 알아내야한다. 여기서 네트워크란 한 컴퓨터가 다른 컴퓨터에 연결되어 있으면 한 네트워크에 속해있다고 말한다. 2. dfs 연결된 간선이 있는지 없는지 확인만 하면된다. 모든 간선을 조사하고 모든 정점을 조사하는 dfs와 bfs를 사용하면 문제를 풀 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include #include using namespace std; void dfs(int here, vector& computers, vector& visited) { visited[here] = true; for(int there = 0; there
2021.03.18