분류 전체보기
-
프로그래머스 피로도 C++프로그래머스(Programmers) 2022. 5. 24. 23:25
입출력 예 k dungeons result 80 [[80,20],[50,40],[30,10]] 3 => 처음에는 DFS 혹은 BFS로 풀어야 하는 문제라고 생각했습니다. => 하지만 제한사항을 보면, dungeons의 길이는 최대 8개입니다. => 완전탐색을 해도 되는 조건이므로 완전 탐색을 시행하였습니다. => 헤더에 포함되어있는 next_permutation함수를 이용하였습니다. https://codingham.tistory.com/262 순열과 조합의 차이 순열 순서가 있는 조합 (중복 허용X) => 순서가 있으므로, 중복을 허용하지 않습니다. ex) A B C 가 있을 때 이 세명을 세울 수 있는 방법의 개수를 구하시오. => (A B C) (A C B) (B A C) (B C A) (C A B)..
-
괄호 회전하기프로그래머스(Programmers) 2022. 5. 18. 23:50
제한사항 s의 길이는 1 이상 1,000 이하입니다. 입출력 예 sresult "[](){}" 3 "}]()[{" 2 "[)(]" 0 "}}}" 0 입출력 예 설명 입출력 예 #1 다음 표는 "[](){}" 를 회전시킨 모습을 나타낸 것입니다. xs를 왼쪽으로 x칸만큼 회전올바른 괄호 문자열? 0 "[](){}" O 1 "](){}[" X 2 "(){}[]" O 3 "){}[](" X 4 "{}[]()" O 5 "}[](){" X 올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다. 입출력 예 #2 다음 표는 "}]()[{" 를 회전시킨 모습을 나타낸 것입니다. xs를 왼쪽으로 x칸만큼 회전올바른 괄호 문자열? 0 "}]()[{" X 1 "]()[{}" X 2 "()[{}]" O ..
-
프로그래머스 가장 먼 노드 C++프로그래머스(Programmers) 2022. 5. 17. 22:42
=> BFS를 사용해 각 노드로 가는 거리들을 구합니다. => 내가 지금 갈 노드 = 이전 노드 + 1; => 가장 멀리 있는 노드값을 answer에 반환합니다. #include #include #include #include using namespace std; int solution(int n, vector edge) { int answer = 0; vector graph(n+1); for(auto ed : edge) { int from = ed[0]; int to = ed[1]; graph[from].push_back(to); graph[to].push_back(from); } vector dist(n+1, -1); queue q; dist[1] = 0; q.push(1); int max =0; w..
-
백준 2747 피보나치수 C++백준 algorithm 2022. 4. 26. 20:29
입력 첫째 줄에 n이 주어진다. n은 45보다 작거나 같은 자연수이다. 출력 첫째 줄에 n번째 피보나치 수를 출력한다. 예제 입력 1 복사 10 예제 출력 1 복사 55 => 단순구현문제입니다. => 피보나치수를 저장할 수 있는 배열을 만들고 FOR문을 통해 피보나치수를 구합니다. => n의 한계치가 45이므로, 배열의 크기는 46이상이어야 합니다. #include #include #include #include #include #include #include #include #include using namespace std; long fibo[50]; int N; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >..
-
프로그래머스 전력망을 둘로 나누기 C++프로그래머스(Programmers) 2022. 4. 25. 20:58
제한사항 n은 2 이상 100 이하인 자연수입니다. wires는 길이가 n-1인 정수형 2차원 배열입니다. wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다. 1 ≤ v1 < v2 ≤ n 입니다. 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다. 입출력 예 nwiresresult 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 4 [[1,2],[2,3],[3,4]] 0 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 입출력 예 #1 다음 그림은 주어진 입력을 해결하는 방법 중 하나를 나타낸 것..
-
프로그래머스 게임 맵 최단거리 C++프로그래머스(Programmers) 2022. 4. 24. 23:47
제한사항 maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다. n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다. maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다. 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다. 입출력 예 mapsanswer [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[..
-
프로그래머스 가장 먼 노드 C++프로그래머스(Programmers) 2022. 4. 22. 22:23
=> BFS문제입니다. => 각 노드들이 맺고 있는 관계들을 벡터로 표현하였습니다. => 이를 vector로 표현하거나 배열로 하거나 편하신대로 하면 됩니다. => 해당 문제에서는 노드의 개수와 간선의 개수가 20,000개 , 50,000개 이므로 벡터를 사용하여 공간의 낭비를 줄였습니다. => 간선들을 표현한 이후에는 항상 사용하던 BFS를 사용하여 문제를 해결하였습니다. https://codingham.tistory.com/168 DFS, BFS code =>BFS 와 DFS code를 사용하기 위해 미리 정리해두었습니다. //int dist[100001]={0}; //bool check[100001];//갔다온지 확인하는 행렬 bool arr[MAX][MAX]; //인접행렬 vector list[M..
-
프로그래머스 영어 끝말잇기 C++프로그래머스(Programmers) 2022. 4. 21. 22:03
제한 사항 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다. words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다. 단어의 길이는 2 이상 50 이하입니다. 모든 단어는 알파벳 소문자로만 이루어져 있습니다. 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다. 정답은 [ 번호, 차례 ] 형태로 return 해주세요. 만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요. 입출력 예 nwordsresult 3 ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"] [3,3] 5 ["hello", "observe..