PS

    23.03.04. 풀었던 문제들

    프로그래머스 디펜스 게임 앞에서부터 priority queue를 써서 제일 큰 값을 줄여가면 되는 문제. 단순 구현이다. typedef long long ll; int solution(int n, int k, vector enemy) { priority_queue pq; int i = 0; ll sum = 0; while(1){ if(i = sum + enemy[i]){ // 이번 wave 감당 가능하면 넣음 sum += enemy[i]; pq.push(enemy[i]); i++; } else if(k > 0){ // 이번 wave 감당 불가면 무적건 써야 함. 없으면 불가 sum += enemy[i]; pq.push(enemy[i]); i++; k--; sum ..

    23.03.03. 풀었던 문제들

    프로그래머스 덧칠하기 많이 본 greedy / simulation 문제. 앞 또는 뒤에서부터 채워가는 게 optimal이다. // n : 구역, m : 롤러 길이 int solution(int n, int m, vector section) { int answer = 0; int size = section.size(); for(int i = 0; i

    23.03.02. 풀었던 문제들

    Leetcode 443. String Compressiong 어디선가 많이 본 string 압축 문제이다. 추가 공간을 할당하고 indexing 실수만 없다면 쉽게 문제를 해결할 수 있지만 이 문제는 in-place 방식으로 풀어야 한다는 추가 제약사항이 있다. 문제는 주어진 대로 구현하면 된다. 어떤 시점 i부터 chars[i]와 같은 마지막 index인 end를 저장하고, i부터 end까지 length를 계산해 넣어주면 된다. class Solution { public: int compress(vector& chars) { int n = chars.size(), cur = 0; for(int i = 0; i

    23.03.01. 풀었던 문제들

    Leetcode 912. Sort an Array 문제는 STL 없이 O(nlogn)의 정렬 함수를 만드는 것이다. - 대표적으로 구현하기 쉬운 merge sort를 쓰면 된다. class Solution { public: vector arr; void merge(int start, int end){ if(start == end) return; int mid = (start + end) / 2; // left : mid 포함, right: mid 포함 x vector left(arr.begin() + start, arr.begin() + mid + 1), right(arr.begin() + mid + 1, arr.begin() + end + 1); int leftlen = left.size(), righ..

    23.02.28. 풀었던 문제들

    Leetcode 652. Find Duplicate Subtrees tree 순회를 이용해 푸는 문제. 처음에는 leaf node부터 탐색하고, 이후에 올라오려 그랬다. 그러나 TreeNode struct에 parent를 가리키는 것이 없기 때문에 이렇게 풀 수 없었다. 그러다 떠올린 게 string으로 순회하고 겹치는 부분을 찾으면 되는 것 아닌가?였다. 일단 preorder로 순회 결과를 쭉 적고 거기서 겹치는 걸 어떻게 찾을지 고민했다. 그렇지만 이렇게 하면 너무 많은 탐색을 해야 한다. 그래서 고민하다 어떤 점부터 traverse 결과를 map에 넣어두면 똑같은 순회 결과가 몇개인지 알 수 있다를 생각했다. 그리고 이 접근이 맞았다! value가 똑같을 수 있으니 left와 right를 구분해 주..

    23.02.27. 풀었던 문제들

    리트코드 daily challenge - 427. Construct Quad Tree 전형적인 DFS 탐색 문제. 종료 조건을 잘 명시하면 쉽게 풀 수 있다. // Runtime 12 ms Beats 86.96% // Memory 15.7 MB Beats 66.30% /* // Definition for a QuadTree node. class Node { public: bool val; bool isLeaf; Node* topLeft; Node* topRight; Node* bottomLeft; Node* bottomRight; Node() { val = false; isLeaf = false; topLeft = NULL; topRight = NULL; bottomLeft = NULL; bottomRi..

    23.02.26. 풀었던 문제들

    리트코드 daily challenge - 72. Edit Distance LCS 비스무리한 DP 문제. LCS로 접근했는데, 안 풀려서 solution을 봤다. (문제 본 지 30분 경과..) dp[i][j]를 word1[0..i-1]을 word2[0...j-1]로 바꾸는 데 필요한 연산 횟수라고 하자. 그러면 word1[i] == word2[j]인 경우에는 dp[i][j] = dp[i-1][j-1]이다. 연산을 할 필요가 없기 때문 else, dp[i][j] = dp[i-1][j] + 1 : insert하는 경우 dp[i][j-1] + 1 : delete하는 경우 dp[i-1][j-1] + 1 : replace하는 경우 와 같은 경우의 수가 나온다. 사실상 dp 식만 세우면 바로 풀리는 문제. // R..

    23.02.25. 풀었던 문제들

    리트코드 daily challenge - 121. Best Time to Buy and Sell Stock 어떤 array가 주어지고, [ith element보다 뒤에 있는 것들 중 제일 큰 값 - ith element]을 maximize하는 문제. 실수했던 것은 answer가 0보다 작을 때는 0으로 출력해야 했는데, 이걸 인지하지 못했다. ith element보다 뒤에 있는 값들 중 제일 큰 값 - ith element를 모든 element에 대해 수행해야 한다. 그러나 이 접근을 flip해서, [ith element보다 앞에 있는 것들 중 제일 작은 것을 알아와서 ith element에서 그 값을 뺌]도 같은 문제가 된다. 이렇게 되면 앞에서부터 처리할 수 있어서 조금 편해진다. dp 문제인 것 같..

    23.02.24. 풀었던 문제들

    리트코드 daily challenge - 1675. Minimize Deviation in Array 주어진 array에서 짝수는 2로 나눌 수 있고, 홀수는 2배할 수 있을 때, [최대값 - 최소값]의 결과를 최소화하는 문제. 이것저것 접근하다가 다음과 같이 접근했다. 홀수를 2배하면 짝수가 되기 때문에 모든 경우의 수에서 수를 2배로 하는 것은 단 1번이다.(더 이상 커질 수 없다.) 나누는 것은 홀수가 될 때 까지 나눌 수 있다. 이것에 착안해서 한쪽방향으로만 연산하고자 했다. 증명은 다음과 같다. deviation을 줄이기 위해서는 max값을 줄이거나, min값을 늘려야 한다. 모든 홀수를 2배로 해버린다면, min값을 더 늘일 수 없다. 따라서 max값을 줄이는 연산만 남게 된다. max값을 줄..

    23.02.23. 풀었던 문제들

    리트코드 daily challenge - 502. IPO 오늘의 daily challenge는 hard 문제였다. 아직 medium도 시작하지 못했는데 어떻게 풀지..? 좀 막막했는데 문제를 읽다 보니 그리 어려운 것은 아니었다. 문제 조건은 k개의 프로젝트를 끝낼 수 있고, total capital를 최대화 하는 것이다. 초기 자본은 w이고 profit[i] : 순수익, capital[i] : 시작하기 위한 자본이다. 문제 제한 조건을 보았을 때 nlogn으로 풀어야 되는 문제같다. 최대한 naive하게 접근해 보자. 매 탐색 시 현재 w보다 작은 capitals 중 profit이 제일 큰 것을 빼내야 한다. (erase) 만약 profit이 같다면 capital이 작은 것을 빼내야 할 것이다. 모든 ..

    23.02.22. 풀었던 문제들

    리트코드 daily challenge - 1011. Capacity To Ship Packages Within D Days 딱 보고 느꼈다. 어..? ㅋㅋㅋ 이거 어떻게 하지? 면접이라 생각하고 한 5분 고민하다 힌트를 요청했다. 'binary search'... 아, parametric search구나. 생각해 보니 결정 문제로 바꾸어 생각해서 어떤 weight가 주어졌을 때, 그 weight가 days 안에 옮길 수 있는지 없는지는 O(n)으로 아주 쉽게 풀리는 문제다. wight 최소값은 1이고, 최대값은 25,000,000(weight size 500 * max weight element value 50000)이며, 이러면 O(nlogn)으로 시간 안에 풀리며, lower bound를 찾으면 된다..

    23.02.21. 풀었던 문제들

    리트코드 daily challenge - 540. Single Element in a Sorted Array 문제 조건이 logn이기 때문에 binary search쪽 알고리즘인 것 같다.에서 시작했다. binary search이기 때문에 절반씩 줄여나가야 할 것 같다. 추가로 문제 조건에서 nums.size()는 홀수이며, 1보다 크거나 같다. 이어서 base case부터 생각을 했다. base case, len == 1인 경우 : 남아있는 element가 답 base case, len == 3인 경우 : 1개짜리 골라 리턴하면 됨 len == 5인 경우 : 절반으로 나눠야 하기 때문에 2, 3으로 나눈다고 생각해 보자. 그러면 아래와 같은 2가지 경우가 생긴다. [1, 2 / 2 / 3, 3]과 같이..

    23.02.20. 풀었던 문제들

    리트코드 daily challenge - 35. Search Insert Position binary search(또는 lower bound)를 구현하는 문제. 내 포스팅에 작성되어 있다. 프로그래머스 lv.2 연속 부분 수열 합의 개수 환형 array라는 것에 착안해서 크기를 2배로 늘리면 쉽게 풀리는 3중for문 문제. 또는 조금 최적화해서 2중 for문으로 풀 수 있다. #include #include #include #include using namespace std; int solution(vector elements) { int size = elements.size(); elements.insert(elements.end(), elements.begin(), elements.end()); se..

    23.02.19. 풀었던 문제들

    리트코드 daily challenge - 103. Binary Tree Zigzag Level Order Traversal Binary Tree를 BFS를 써서 순회하는 문제. 처음 풀었을 때는 7ms(27.9%), 12.2MB(17.21%)가 나왔다. 왜 이렇게 많이 나왔을까.. 생각해 보고, 답안지를 보고 개선점을 생각했다. 개선점은 아래 코드에 주석으로 달아놓았다. typedef pair pni; // 개선 class Solution { public: vector zigzagLevelOrder(TreeNode* root) { int maxDepth = -1; vector answer; // BFS init queue q; q.push({root, 0}); while(!q.empty()){ // po..

    23.02.18. 풀었던 문제들

    리트코드 daily challenge - 226. Invert Binary Tree 처음 풀었을 때 3ms가 나왔다. DFS라는 함수를 따로 정의했기 때문인 것 같은데... 굳이 새로운 함수 안 짜고 바로 풀면 0ms가 나온다. 프로그래머스 lv 1 삼총사 3sum 문제인데, 여기서는 제한 조건이 널널해서 3중for문으로 풀어도 된다. 프로그래머스 lv 1 크기가 작은 부분 문자열 substring을 활용하는 문제 프로그래머스 lv 1 콜라 문제 반복문 쓰면 되는 수학 문제 프로그래머스 lv 1 푸드 파이트 대회 반복문 + reverse 쓰는 문제 프로그래머스 lv 1 가장 가까운 같은 글자 char c의 [이전 위치]를 기억해 두면 쉬운 문제. DP의 일종. 프로그래머스 lv 2 귤 고르기 크기별 귤 ..

    23.02.17. 풀었던 문제들

    프로그래머스 lv0 옹알이(1) - string 다루는 문제

    22.09.08. 풀었던 문제들

    백준 단계별 31 MST 2887 SVEMIR MST 문제이긴 한데, 단순히 MST로 풀면 안 되는 문제이다. 처음에 주어진 vertex의 개수가 10만 개이기 때문에, 이들 사이의 모든 edge를 고려한다면 10^2이 되어 메모리초과, 또는 시간 초과가 나게 된다. 따라서 규칙을 찾아서 풀어야 하는 문제였는데, 이 문제에서 dist는 min(x1-x2, y1-y2, z1-z2)이기 때문에 각 vertex 좌표를 입력받고, 정렬하고, 인접한 값의 차이로만 edge를 구성하면 된다. 왜냐하면, point가 a b c 순서일 때 kruskal의 정의 상 smallest edge부터 사용하기 때문에 b - a, c - b를 사용한다. 이 때 a -> c는 a -> b -> c로 표현되기 때문에 a -> c의 ..

    22.09.07. 풀었던 문제들

    백준 MST 1774 Building Roads 2887 SVEMIR

    22.09.06. 풀었던 문제들

    백준 단계별 30 union-find 20040 Cycle Game 4195 Virtual Friends 백준 단계별 31 Minumum Spanning Tree 9327 flying safely 1197 최소 스패닝 트 4386 freckles

    22.09.05. 풀었던 문제들

    백준 1976 여행 가자

    22.09.04. 풀었던 문제들

    백준 1717 집합의 표현 union-find 문제

    22.09.02. 풀었던 문제들

    백준 4803 트리 트리인지 검사하는 문제. tree는 acyclic connected graph임을 인지하고 cycle이 있는지 검사하면 된다

    22.09.01. 풀었던 문제들

    백준 5639 이진 검색 트리

    22.08.30. 풀었던 문제들

    백준 1991 트리 순회

    22.08.29. 풀었던 문제들

    백준 1967 트리의 지름 - 나름 재밌는 문제. 임의로 뽑은 한 vertex가 longest path 중간에 있을 수 있으므로, vertex부터 longest vertex를 뽑고 해당 vertex부터 longest distance를 구하면 된다.

    22.08.28. 풀었던 문제들

    CPS 본선 6번 upsolve

    22.08.26. 풀었던 문제들

    백준 1167 트리의 지름 요새 SQLD한다고 바쁘다.