알고리즘 문제풀이
-
[프로그래머스/Level 2] 순위 검색 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 8. 16:40
programmers.co.kr/learn/courses/30/lessons/72412 s[0] >> s[1] >> s[2] >> s[3] >> num; getCombi(stoi(num)); } for(auto &s : scores) { sort(s.second.begin(), s.second.end()); } for(auto &q : query) { int score; stringstream ss(q); ss >> s[0] >> num >> s[1] >> num >> s[2] >> num >> s[3] >> num; score = stoi(num); vector v = scores[s[0] + s[1] + s[2] + s[3]]; if(v.size() != 0) { auto it = lower_boun..
-
[LeetCode/easy] Symmentric-Tree (C++)알고리즘 문제풀이/LeetCode 2021. 2. 8. 01:47
leetcode.com/problems/symmetric-tree/ Symmetric Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 재귀를 이용하여 각각 루트노드에서 왼쪽 노드와 오른쪽 노드 값이 같은지 비교합니다. /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), ..
-
[LeetCode/easy] Climbing-Stairs (C++)알고리즘 문제풀이/LeetCode 2021. 2. 8. 01:04
leetcode.com/problems/climbing-stairs/ Climbing Stairs - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 전형적인 dp 유형의 문제였습니다. dp[n]을 정의해보면, n층을 오를 수 있는 모든 경우의 수를 의미합니다. 그리고 계단은 1 혹은 2만큼 오를 수 있습니다. 마지막 n번째에서 생각해보면, n-1층에서 1만큼 오르는 경우, n-2층에서 2만큼 오르는 경우 두가지를 생각할 수 있는데, 즉 n-1층을 오를 수 있는 ..
-
[LeetCode/easy] Valid-Parentheses (C++)알고리즘 문제풀이/LeetCode 2021. 2. 7. 00:47
leetcode.com/problems/valid-parentheses/ Valid Parentheses - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 스택을 이용하여 괄호의 유효성을 판단하는 문제, 백준과 프로그래머스에서 많이 나온 유형입니다. (다른 점은 괄호의 종료가 소괄호, 중괄호, 대괄호 총 3가지라는 점) 아래의 세가지를 고려해주면 쉽게 해결할 수 있습니다. 1. 스택이 비어있는데 닫는 괄호가 오는 경우 : false 2. 스택에 값이 남아 있는 ..
-
[LeetCode/easy] Maximum Subarray (C++)알고리즘 문제풀이/LeetCode 2021. 2. 6. 15:24
leetcode.com/problems/maximum-subarray/ Maximum Subarray - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 인접한 숫자의 누적합을 구해가며 최대값을 갱신합니다. 근데 이때 누적합이 음수가 된다면 여태까지의 누적합이 최대값이 될 수 없으므로, 0으로 바꿔주고 다시 누적 합을 구합니다. 마지막에 기록되어있는 누적합의 최대값이 답이 됩니다. /* O(N) */ class Solution { public: int maxSub..
-
[LeetCode/easy] Two Sum (C++)알고리즘 문제풀이/LeetCode 2021. 2. 6. 13:14
leetcode.com/problems/two-sum/ Two Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 새롭게 알게된 점 stl map, unordred_map의 find 함수의 시간복잡도는 log(n), Red Black Tree 기반 /* 완전탐색 : O(N^2) */ class Solution { public: vector twoSum(vector& nums, int target) { vector answer; for(int i = 0; i..
-
[프로그래머스/Level 3] 섬 연결하기 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 5. 17:22
programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 다익스트라를 이용하여 해결하였습니다. 다만 시작점에서 각 정점까지의 누적 최단거리가 아니라, 해당 노드를 한번만 지나고 그 값이 최단거리가 되어야 합니다. 이렇게 되면 시작점이 어디냐에 따라 최소값이 다르게 나올 수 있기 때문에, 시작점을 0부터 n까지 모두 진행해보면서 어떤 시작점으로 다익스트라를 시작할 때 최소값을 구할 수 있는지 알아내야합니다. 테스트케이스 예 4, [[0, 1, 5], [0, 2, 3], [1, 2, 1], [1, 3, 2], [2, 3, 4]] : ..
-
[프로그래머스/Level 3] 네트워크 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 4. 23:20
programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 처음 DFS 진입이 몇번 일어나는지 구하면 되는 문제입니다. #include #include using namespace std; bool visit[201]; void DFS(vector computers, int idx, int n) { for(int i = 0; i < n; i++) { if(!visit[i] && computers[idx][i] == 1) { vi..