PS

23.04.03. 풀었던 문제들

Leetcode 881. Boats to Save People two pointer + greedy 문제. 각 boat에 최대 2명의 인원이 올라가고, limit보다 넘으면 안 되므로 오름차순 정렬한 이후 제일 큰 것을 올리고, 이후 작은 것을 올릴 수 있으면 올린다. 이것을 반복하면 된다. class Solution { public: int numRescueBoats(vector& people, int limit) { sort(people.begin(), people.end(), less()); int s = 0, e = people.size()-1; int answer = 0; while(s

23.04.02. 풀었던 문제들

Leetcode 2300. Successful Pairs of Spells and Potions 문제를 보고 binary search임을 깨달았다. 일단 문제에서 주어지는 size n, size m의 배열이 있다. 이 배열의 모든 값을 곱하면 O(nm)으로, $10^{10}$으로 시간 초과가 난다. 다른 방법이 없을까? 문제를 잘 살펴보면 어떤 potion의 값 p에 대해 어떤 값 x가 주어졌을 때 success를 만족하는지 안 하는지는 px가 success보다 크거나 같은지 여부로 쉽게 알 수 있다. 그러면 역으로 p가 주어졌을 때 success를 만족하는 x값을 역산할 수 있다. 만약 potion이 [1, 2, 3, 4, 5]에 success가 7이라면 success를 만족하는 x값은 [7, 4, 3..

23.04.01. 풀었던 문제들

Leetcode 704. Binary Search 이진 탐색으로 풀면 되는 간단한 문제. // Runtime 42 ms Beats 45.34% // Memory 27.6 MB Beats 18.24% class Solution { public: int search(vector& v, int input) { int start = 0, end = v.size()-1, mid; while(start

23.03.31. 풀었던 문제들

Leetcode 1444. Number of Ways of Cutting a Pizza 문제를 보고, 일단 recursion dp 문제임을 깨닫고 dp로 해결하려 했다. dp[i][j][k] = 좌표 i, j에서 k번 cutting할 수 있는 개수라고 정의했다. 그러면 각 탐색 시 i, j, k에 대해 탐색하고, memoization을 사용하면 된다. 또, 각 탐색 시 i, j에 대해 [row로 쪼갤지, col로 쪼갤지]를 결정해야 한다. 그래서 [쪼갤 수 있는지 여부]를 판단하는 로직을 작성해야 한다. 그러나 [i, j]부터 [m, n]까지 전부 다 뒤지면서 경우의 수를 본다면 row 개수 m에 대해 mn 전체 순회해야 하고, col 개수 n에 대해 mn 전체를 순회해야 하므로 각 탐색에서 mn(m+n..

23.03.30. 풀었던 문제들

Leetcode 87. Scramble String 어떤 string s1에 특정 연산을 반복해 s2를 만들 수 있는지 문제. DP 문제이다. 기본적인 직관은 s1의 substring이 s2의 scramble인지 확인하는 것이다. 또한, s1의 각 index에 대해 앞/뒤의 단어를 자르고, 또 앞뒤 단어를 바꿀 수 있기에 이를 모두 계산해 보면 된다. top-down으로 풀 때, s1의 index를 기준으로 s1, s2를 쪼개고 각각의 subproblem 4개를 풀 수 있다. base case : s1 == s2이면 return true s1의 앞쪽 substring과 s2의 앞쪽 substring && s1의 뒤쪽 substring과 s2의 뒤쪽 substring ... 1번, 2번 순서를 바꾼 s1의..

23.03.29. 풀었던 문제들

Leetcode 1402. Reducing Dishes Intuition 문제를 보고, 일단 정렬한 후 뽑기 시작할 시작지점을 고르면 될 것이라 생각했다. 오름차순 정렬되어 있는 상태에서, 제일 끝 index i를 시작지점으로 여기고 여기부터 시작한다.(제일 끝 index가 제일 큰 값이므로) 이 때, i가 한 칸 앞으로 당겨지면 총 계에 arr[i-1] + arr[i] + ... + arr[n-1]이 더해져야 한다. 이 값을 sum이라고 할 때 sum이 0보다 크다면 i를 한 칸 앞으로 당겨 sum을 maximize할 수 있다. 그러면 sum이 0보다 크면 이것을 반복하면 된다. arr[i-1] + ... + arr[n-1]은 prefix sum으로 쉽게 구할 수 있다. 따라서 O(n)으로 풀리는 문제..

23.03.28. 풀었던 문제들

Leetcode 983. Minimum Cost For Tickets dp로 풀리는 문제. dp[i]를 ith day의 cost라 하자. 그러면 다음과 같은 점화식을 찾을 수 있다. dp[i-1] + [현재 값이 day에 있으면 cost[0]] dp[i-7] + 7일권 cost dp[i-30] + 30일권 cost 항상 그렇듯 dp[i]를 뭘로 정의하냐에 따라 점화식을 세우기 쉬워지기도 하고, 어려워지기도 한다. 점화식을 잘 세워보자. // Runtime 4 ms Beats 69.83% // Memory 9.6 MB Beats 81.2% class Solution { public: int handleOutbound(int day, int value){ if(day - value < 0) return 0;..

23.03.27. 풀었던 문제들

Leetcode 64. Minimum Path Sum 간단한 DP 문제. array의 top left부터 bottom right까지, [오른쪽으로 움직이거나, 아래로 움직이거나] 2개의 선택지로 도달하는 최소 weight를 얻어내는 방법이다. graph로 생각하면 top left부터 모든 vertex까지 dijkstra로 알아내야 하면 O(nlogn)이다. 그러나 이 문제의 경우 DP를 사용할 수 있다. dp[r][c] = weight[r][c] + (dp[r-1][c], dp[r][c-1]) // Runtime 7 ms Beats 90.29% // Memory 9.5 MB Beats 98.74% class Solution { public: int minPathSum(vector& grid) { int ..

23.03.26. 풀었던 문제들

Leetcode 2360. Longest Cycle in a Graph directed graph에서 cycle을 찾는 문제이다. 예전에 소마 코테였나? cycle을 찾는 문제를 DFS로 푼 적이 있었다. 그것처럼 풀면 될 것 같았다. 로직은 아래와 같다. DFS를 한다. visited하지 않은 vertex를 찾으면 일반적인 DFS를 수행한다. 이 때, 방문 기록을 따로 기록한다. - 1번 visited한 vertex를 찾으면 탐색을 종료하고, 지금까지 방문 기록에서 해당 vertex를 찾는다. 만약 있다면 cycle이 있는 것이다. 없다면 cycle이 없는 것이다. - 2번 이렇게 생각할 수 있는 이유는 directed graph이고, 모든 vertex에서 edge가 최대 1개이기 때문이다. 만약 어떤..

23.03.25. 풀었던 문제들

Leetcode 2316. Count Unreachable Pairs of Nodes in an Undirected Graph 이 문제를 처음 딱 봤을 때, disjoint set의 개수를 구하고, 이 배열을 arr이라고 했을 때, index i에 대해 [arr[i] * sum of arr[i+1] to end]를 구하면 되는 것을 알 수 있다. disjoint set의 개수를 구하는 것은 DFS, 또는 union-find를 이용해 쉽게 구할 수 있다. 그렇지만 index i에 대해 [arr[i] * sum of arr[i+1] to end]를 어떻게 쉽게 구할 수 있을까? 첫 번째 접근 : DFS + prefix sum 나는 prefix sum을 떠올렸다. i > j일 때 psum[i] - psum[j..

23.03.24. 풀었던 문제들

Leetcode 1466. Reorder Routes to Make All Paths Lead to the City Zero 이 문제는 0부터 DFS를 시작한다고 생각하면 아주 쉽게 풀린다. 비록 주어진 edge는 directed이지만 이를 indirected로 바꾼다. 대신 outgoing인지 incoming인지에 대한 flag를 하나 둔다. 이후 0부터 DFS 또는 BFS를 하고, edge가 incoming일 때만 해당 edge를 바꾸어 주면 된다. // Runtime 342 ms Beats 93.65% // Memory 106.6 MB Beats 74.70% struct edge{ int next; bool isOutgoing; }; class Solution { public: int answer;..

23.03.23. 풀었던 문제들

Leetcode 1319. Number of Operations to Make Network Connected 처음에는 [사용하지 않는 edge 개수]를 구하면 된다고 생각했다. 그래서 각 edge에 사용 여부를 표시하고 전체 DFS 후 disjoint set의 개수를 알아내고, 사용하지 않은 edge 개수를 알아내면 문제를 풀 수 있을 거라 생각했다. 그러나 각 edge에 사용 여부를 표시하는 것이 까다로웠다. 굳이 이렇게 풀어야 하나? 라는 생각도 들고. 그러다가 어제 푼 union-find 문제가 생각났다. 어? union-find로 풀면 쉽게 풀리겠는데? 로직은 아래와 같다. 모든 edge에 대해 union한다. 이 때 다른 disjoint set인 경우(root가 다른 경우)에는 두 disjoi..

23.03.22. 풀었던 문제들

Leetcode 2492. Minimum Score of a Path Between Two Cities 첫 번째 접근 2022 카카오 인턴 코딩테스트 4번 문제와 비슷하다. dijkstra를 하되, [지금까지 path + v->w weight]로 dijkstra하는 것이 아니라 [지금까지 path, v->w weight] 중 min값으로 dijkstra해야 한다. // Runtime 560 ms Beats 39.70% // Memory 130.3 MB Beats 58.31% typedef pair pii; struct cmp{ bool operator()(pii &a, pii &b){ if(a.second == b.second) return a.first < b.first; return a.second ..

23.03.20. 풀었던 문제들

Leetcode 605. Can Place Flowers 간단한 simluation 문제. 앞에서부터 순회한다. [현재 위치(i)] 앞에는 1이 없어 설치 가능하다는 것을 전제로 한다. 위 전제를 맞춰주기 위한 indexing이 필요하다. 만약 arr[i] == 0이라면 i+1이 범위 밖이거나 arr[i+1]이 0이라면 설치할 수 있다. 설치했다면 i부터 [0, 0, ?]인 상태이므로 i += 2를 한다. 설치하지 못했다면 [0, 1, ?]인 상태이므로 i += 1을 한다. arr[i] == 1이라면 문제 조건에 따라 arr[i+1]은 무조건 0이다. 단 i+1에도 설치하지 못한다. 따라서 i += 2를 한다. // Runtime 10 ms Beats 97.73% // Memory 20.3 MB Beat..

23.03.19. 풀었던 문제들

Leetcode 211. Design Add and Search Words Data Structure 먼젓번 풀었던 Leetcode 208. Implement Trie처럼 trie를 구현하는 문제이다. 단 .이라는 wildcard가 추가되어 이에 대한 로직을 작성해야 한다. 기본적인 trie의 로직은 저번에 풀었던 문제와 동일하므로 넘기고 .에 대해 어떻게 처리했는지만 서술하려 한다. 만약 [현재 탐색중인 char]이 .이 아니라면 trie 탐색하는 것처럼 탐색한다. [현재 탐색중인 char]이 .이라면 [현재 탐색중인 TrieNode의 모든 child]를 탐색해야 한다. 따라서 DFS를 사용한다. DFS를 위해 searchHelper function을 만들고 현재 탐색중인 word 다음 것부터 복사해 ..

23.03.18. 풀었던 문제들

Leetcode 1472. Design Browser History 문제에서 주어진 대로 풀면 되는 문제. 간단한 구현 문제이다. 입력은 5000이기 때문에 vector.erase() 등을 사용해 O($n^{2}$)으로 풀어도 2천만 정도로 상관 없다. 그러나 효율적으로 생각해 보면 erase는 O(n)의 시간이 걸리기 때문에 사용하지 않고 생각해 보자. 전체 history를 한 vector에 넣고 [현재 탐색 가능한 길이]를 len으로 저장한다. 만약 idx가 len-1이라면 idx가 최신인 상태이고, idx가 len - 2 이하라면 back() method를 몇 번 호출해 forward를 할 수 있는 상태이다. 이 때 forward는 최대 len-1까지만 진행할 수 있다. 그러면 back할 때는 le..

23.03.17. 풀었던 문제들

Leetcode 208. Implement Trie (Prefix Tree) Trie의 search, insert, startsWith method를 구현하는 문제이다. Trie는 string으로 이루어진 tree이다. 뭐.. 자료구조야 알고 있으니까 넘어가고. 첫 접근 TrieNode에는 2개의 정보가 있다. 해당 node가 가지고 있는 char 정보인 value, 해당 node가 가지고 있는 childs로의 pointer인 next. search나 startsWith 시에는 current node의 childs가 해당 문자를 가지고 있는지 검사하고 없으면 false를 리턴한다. 가지고 있다면 아래로 내려간다. 이 때, startsWith의 경우 문자열의 끝인지 아닌지 상관없이 startsWith st..

23.03.16. 풀었던 문제들

Leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal 어떤 binary tree의 inorder와 postorder 순회 결과가 주어졌을 때 tree를 구성하는 문제이다. 이 때 inorder와 postorder의 모든 element는 unique하다. 첫 접근 : time O($n^{2}$), space O(n) 일단 postorder의 제일 마지막 index가 root인 것(rootidx라 하자), 그리고 inorder에서 rootidx 왼쪽의 것은 왼쪽 subtree, 오른쪽의 것은 오른쪽 subtree임을 알 수 있다. 따라서 각 탐색에서 왼쪽/오른쪽을 나누어야 한다는 것은 쉬운 직관으로 알 수 있다. 그럼 다음 탐색에서..

23.03.15. 풀었던 문제들

Leetcode 958. Check Completeness of a Binary Tree 첫 접근 첫 접근은 각 layer를 검사하는 방식으로 생각을 했는데 생각보다 귀찮은 경우의 수가 많아서 binary tree를 array로 표기하려 했다. 이렇게 표기해도 된다고 생각했던 이유는 vertex size가 최대 100이었기 때문이었다. 그러나 1자로 길게 늘어진 tree의 경우에는 최대 $2^{100}$의 array가 필요했고 이건 아니다 싶어 다른 방법으로 전환했다. 두 번째 접근 : time, space O(n) 각 layer마다 탐색하는 방식이다. 각 layer에서 아래와 같은 조건으로 탐색할 수 있다. 각 layer 탐색 시 left -> right 순서대로 탐색할 때 null이 나온 후 notn..

23.03.14. 풀었던 문제들

Leetcode 129. Sum Root to Leaf Numbers 각 vertex에서 값 : 이전 vertex 값 * 10 + 현재 vertex 값 이 조건으로 모든 leaf node의 값의 합을 구하는 문제이다. 문제를 처음 보고 함수에 추가 인자를 넣고 싶지 않아 처음에는 tree traversal로, leaf부터 올라오면 안되나? 생각했다. 그러나 이렇게 풀면 마땅한 방법이 없다. 추가 공간을 써야 하기도 하고. 그래서 그냥 함수에 추가 인자를 하나 넣고 풀었다. DFS()함수는 아래와 같은 역할을 한다. 현 vertex의 값을 구한다.(prev * 10 + cur->val) 현 vertex가 leaf면 전역변수 sum에 값을 더해줌 leaf가 아니라면 left, right를 탐색함 그리고 ma..

23.03.13. 풀었던 문제들

Leetcode 101. Symmetric Tree 문제를 받자마자 1번의 순회로 해결할 수 있는 경우가 있을 것 같아 left를 순회하는 것과 right를 순회하는 것을 따로따로 복잡하게 생각해 보다가 vector에 left inorder 탐색 결과와 right inorder 탐색 결과를 넣고 이 둘을 비교하는 방식을 썼다. 그러나 이렇게 풀면 틀린다. 다르게 생긴 tree지만 같게 들어가는 경우가 생긴다. 틀린 걸 확인하고 다르게 코드를 짜기 시작했다. 각 탐색에서 left와 right를 한번에 탐색하고, left와 right가 같고, 탐색가능할 때(null이 아닐 때) 그 때 좌우 탐색 결과를 보는 거다. 만약 left와 right 둘 다 null이면 symmetric이다. 만약 left와 righ..

23.03.12. 풀었던 문제들 - 2023 KAKAO BLIND RECRUITMENT

Leetcode 23. Merge k Sorted Lists 문제 k개의 정렬되어 있는 list를 정렬하는 문제이다. 제일 쉽게 접근한다면 모든 list element를 하나의 vector에 넣고 전체 sort하던가 또는 counting sort하는 방식을 생각할 수 있을 것이다. 입력 조건은 -10000 val; } }; class Solution { public: ListNode* mergeKLists(vector& lists) { priority_queue pq; // k개의 list 제일 앞에 있는 것을 pq에 넣음. 이 때 pq에 NULL을 허용하지 않겠다. for(ListNode* v : lists){ if(v != NULL) pq.push(v); // *** 유의! NULL인 경우 넣지 않음..

23.03.11. 풀었던 문제들

프로그래머스 숫자 타자 대회 첫 접근 첫 접근은 greedy였다. 각 탐색 시 왼손을 움직이는 경우와 오른손을 움직이는 경우 2개의 경우의 수가 있으므로 brute-force를 사용하면 $2^{100000}$이므로 가뿐하게 시간 초과가 난다. 따라서 greedy를 사용했다. dp[i][j] : 숫자 i를 손 i로 입력했을 때 최솟값으로 두고, j는 0 또는 1이다. dp[i][0](i번째 수를 왼손으로 누른 수) = min(이전에 왼손으로 누르고 또 왼손으로 누른 경우, 이전에 오른손으로 누르고 또 오른손으로 누른 경우)로 계산해 dp[i][0] = min(dp[i-1][0] + weights[이전 왼손 위치][numbers[i]], dp[i-1][1] + weights[이전 왼손 위치][numbers[..

23.03.10. 풀었던 문제들

Leetcode 382. Linked List Random Node 어떤 singly linked list의 head가 주어졌을 때 모든 index를 같은 확률로 리턴하는 함수를 만드는 문제이다. 첫 접근 : 1번의 순회, O(n) 공간 별다른 제약이 없는 초기 조건에서 아래와 같이 작성했다. linked list의 전체 node를 vector에 넣고 rand() v.size() index를 리턴한다. class Solution { public: vector v; Solution(ListNode* head) { while(head != NULL){ v.push_back(head); head = head->next; } } // 추가 공간을 사용해서 rand() index 리턴 int getRandom()..

저수지 샘플링 Reservoir Sampling

어떤 array에서 random한 i번째 element를 뽑고 싶다고 하자. 일반적으로 전체 배열의 size를 알아내고 rand () % size를 한 후 해당 index를 가져오는 방식을 택할 것이다. 그러나 모종의 이유로 전체 배열 size를 알 수 없는 상황에서도 무작위 추출을 할 수 있다. 예를 들어 array가 아니라 singly linked list여서 끝을 모르고, 단 1번 순회해야 한다는 조건이라면? 1번의 순회로 size를 알아내도 index에 접근하는 데 O(n)이 걸리기 때문에 해결할 수 없다. 이런 상황에서 Reservoir sampling을 사용한다. Reservoir Sampling 정의 Reservoir sampling은 어떤 배열을 1번에 1개의 element만 보며 순회할 ..

23.03.09. 풀었던 문제들

Leetcode 142. Linked List Cycle II 어떤 linked list의 head가 주어졌을 때 cycle이 없으면 NULL, cycle이 있으면 cycle의 시작 vertex를 리턴하는 문제. space를 O(n)으로 쓰면 set같은 걸 써서 중복검사를 통해 쉽게 풀 수 있다. 그러나 O(1)로 풀어야 하는 게 진짜인 문제. 2개의 pointer를 이용해 답을 구할 수 있다. 한 번에 2개 뒤로 이동하는 fast pointer, 한 번에 1개 뒤로 이동하는 slow pointer 이렇게 2개를 둔다. 만약 cycle이 없다면 fast는 진행 중 NULL을 만난다. 이 경우 return NULL cycle이 있다면 fast는 slow보다 항상 빠르기 때문에 k바퀴를 돈 후 slow po..

23.03.08. 풀었던 문제들

Leetcode 875. Koko Eating Bananas 어제와 동일한 문제. 문제를 딱 보면 parametric serach로 풀어야 할 것 같은 문제였다. 구해야 하는 값(k)의 범위는 넓지만 k가 정해졌을 때 array를 순회하면서 다 먹을 수 있는지 여부는 쉽게 구할 수있고(O(n)) 정답이 연속적이다. (어떤 t가 답이면 t보다 큰 모든 값은 답이 될 수 있다) 모든 binary search문제가 그렇듯 상한을 어떻게 두느냐가 중요하다. 여기서는 piles[i]의 max값이 상한인데, k가 piles[i]보다 크더라도 모든 piles를 먹는 데 걸리는 시간은 동일하기 때문이다. 따라서 상한은 max of piles array이다. 순회하며 계산해도 되지만 명시적인 값을 두는 게 더 빠를 것 ..

23.03.07. 풀었던 문제들

Leetcode 2187. Minimum Time to Complete Trips 문제를 딱 보면 parametric serach로 풀어야 할 것 같은 문제. time의 범위는 아주 넓지만 time이 정해졌을 때 totalTrips는 구하기 쉽고(O(n)) 정답이 연속적이다. (어떤 t가 답이면 t보다 큰 모든 값은 답이 될 수 있다) 다만 유의해야 할 점은 time의 상한을 어떻게 두느냐이다. totalTrips가 $10^{7}$, time[i]가 $10^{7}$일 때 정답은 $10^{14}$, 만약 time.len이 더 커지면 정답은 더 작아진다. 따라서 상한을 $10^{14} + 1$로 두었다. (근데 이렇게 안하고 LLONG_MAX로 두어도 된다. 다만 이 경우는 overflow 나지 않게 sta..

23.03.06. 풀었던 문제들

Leetcode 1539. Kth Missing Positive Number 증가수열 arr과 숫자 k가 주어질 때 arr에 있지 않은 k번째 배열을 찾는 문제. O(n)으로 풀면 바로 풀린다. O(n) solution // Runtime 6 ms Beats 53.33% // Memory 9.7 MB Beats 38.5% class Solution { public: int findKthPositive(vector& arr, int k) { vector missings; int num = 1, arridx = 0; while(1){ if(arridx < arr.size() && num == arr[arridx]){ // not missing num++; arridx++; } else{ // missing ..

23.03.05. 풀었던 문제들

Leetcode 1345. Jump Game IV 어디선가 DP로 많이 본 문제. 첫 접근은 아래와 같이 dijkstra로 풀었다. 그러나 이 경우 for문 때문에 worst case $O(n^{2})$이 날 수 있다. 예를 들어 [1, 1, 1, 1, 1, 1, 1,1 ,1 ,1 ,1 ,1, 2]인 경우 1이 있는 부분을 계속 탐색하기 때문이다. dijkstra는 O(ElogV)인데, 위와 같은 경우 E가 $V^{2}$이 되기 때문이다. typedef pair pii; // .first : index, .second : dist struct cmp{ bool operator()(const pii&a, pii&b){ if(a.second == b.second) return a.first > b.first..