PS/PS Log
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 귤 고르기 크기별 귤 ..
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.06. 풀었던 문제들
백준 단계별 30 union-find 20040 Cycle Game 4195 Virtual Friends 백준 단계별 31 Minumum Spanning Tree 9327 flying safely 1197 최소 스패닝 트 4386 freckles
22.09.02. 풀었던 문제들
백준 4803 트리 트리인지 검사하는 문제. tree는 acyclic connected graph임을 인지하고 cycle이 있는지 검사하면 된다
22.08.29. 풀었던 문제들
백준 1967 트리의 지름 - 나름 재밌는 문제. 임의로 뽑은 한 vertex가 longest path 중간에 있을 수 있으므로, vertex부터 longest vertex를 뽑고 해당 vertex부터 longest distance를 구하면 된다.