알고리즘 문제풀이
-
[LeetCode] Best Time to Buy and Sell Stock (C++)알고리즘 문제풀이/백준 2021. 3. 7. 17:38
leetcode.com/problems/best-time-to-buy-and-sell-stock/ Best Time to Buy and Sell Stock - 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 그리디 유형의 문제, O(N^2) 풀이로는 입력값의 최대 크기가 10^5이므로 불가능합니다. 따라서 그리디 방식으로 접근하는데, 최소값을 갱신해가며 동시에 최대 이익을 갱신하는 것이 포인트입니다. class Solution { public: int maxPro..
-
[프로그래머스/Level 1] 신규 아이디 추천 (C++)알고리즘 문제풀이/프로그래머스 2021. 3. 7. 14:58
programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 카카오 기출 문제 해결을 위해 알아두면 좋을 것 1. 대문자 소문자 변형이 필요할 때, transform() 함수를 사용한다. 2. 문자열에서 알파벳을 찾을 때, isalpha() 함수를 사용한다. 3. 문자열에서 숫자를 찾을 때, isdigit() 함수를 사용한다. 4. 문자열에서 특정 문자를 찾을 때, strchr() 함수를 사용한다. 문자열을 이용한 구현 문제였습..
-
[LeetCode] Maximum Depth of Binary Tree (C++)알고리즘 문제풀이/LeetCode 2021. 3. 6. 18:10
leetcode.com/problems/maximum-depth-of-binary-tree/ Maximum Depth of Binary 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 역시나 리스트를 사용해 포인터의 개념이 필요했습니다. 트리의 DFS, BFS 탐색을 해보는 문제였습니다. /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * ..
-
[LeetCode] Merge Two Sorted Lists (C++)알고리즘 문제풀이/LeetCode 2021. 3. 4. 23:06
leetcode.com/problems/merge-two-sorted-lists/ Merge Two Sorted Lists - 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 singly-linked list. * struct ListNode { * int val; * ListNode *ne..
-
[프로그래머스/Level 3] 멀리 뛰기 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 27. 21:36
programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 기초 DP 문제였습니다. dp[n]을 n칸을 오르기 위한 경우의 수로 정의하고, 이에 대한 점화식을 세우면 됩니다. 1칸과 2칸 이동을 할 수 있으므로, n칸에 도착하는 방법은 n-1칸을 오르는 경우의 수에 1칸을 오르거나, n-2칸을 오르는 경우의 수에 2칸을 오르면 됩니다. 따라서 점화식은 dp[n] = dp[n -..
-
[프로그래머스/Level 3] 스타 수열 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 26. 01:15
programmers.co.kr/learn/courses/30/lessons/70130 코딩테스트 연습 - 스타 수열 programmers.co.kr 1. map을 통해 원소들의 빈도 수를 구하기 2. map의 key를 교집합으로 설정하고, 이때 만들 수 있는 최대 스타 수열의 길이는 value(빈도 수) * 2 3. a의 배열의 a[i], a[i + 1] 값을 비교하고, 이 값들이 key와 같은지 비교하며 조건을 맞추기 4. 조건을 통과하면 현재 스타 수열의 길이는 2씩 갱신하고, 다음 비교를 위해 i++ 처리 5. 현재 key를 교집합으로 스타 수열이 길이를 구했으면 최대값을 갱신, 위를 계속 반복하기 #include #include #include #include using namespace std..
-
[프로그래머스/Level 3] 야근 지수 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 25. 16:36
programmers.co.kr/learn/courses/30/lessons/12927 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr 문제에서 야근 지수를 최소화 하기 위해서는 작업량의 최대값을 매번 줄여가야합니다. 이러한 최대값을 구하기 위해서 우선순위 큐를 이용한다면, 문제를 쉽게 해결할 수 있습니다. #include #include #include using namespace std; long long solution(int n, vector works) { long long answer..
-
[프로그래머스/Level 3] 불량 사용자 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 24. 17:08
programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr 카카오 인턴 기출 카카오 기출문제였던 순위검색처럼 banned_list와 매칭될 수 있는 user_id의 모든 경우의 수를 비트 연산을 이용해서 구하려고 시도했는데, 올바른 접근 방법이 아니었던 것 같습니다. 두 아이디의 길이, 그리고 *이 아니고 다른 문자가 같은지를 통해 해당 아이디가 불량 사용자의 후보가 될 수 있는지 확인하고, 이를 DFS를 통해 모든 경우의 수를 구합니다..