전체 글

23.04.10. 풀었던 문제들

Leetcode 20. Valid Parentheses stack을 사용할 줄만 안다면, 쉽게 구현할 수 있는 문제. 백준의 stack의 첫 문제였던 것으로 기억한다. // Runtime 0 ms Beats 100% // Memory 6.2 MB Beats 81.54% class Solution { public: bool isValid(string s) { stack stk; for(char c : s){ if(c == '(' || c == '[' || c == '{') stk.push(c); else{ if(stk.empty()) return false; if(c == ')'){ if(stk.top() == '(') stk.pop(); else return false; } else if(c == ']'..

23.04.09. 풀었던 문제들

Leetcode 1857. Largest Color Value in a Directed Graph 문제를 읽고, 일단 귀찮은 문제라는 것은 깨달았다. 해야 하는 것만 해도 cycle 존재 여부 검증 cycle이 없는 경우, 모든 path에 대해 모든 색깔의 경우의 수를 구해야 한다. 이 문제의 경우 outgoing edge가 1개라는 조건이 없기 때문에 일반적인 directed graph에서 cycle 여부를 검증하는 방법을 사용해야 했고, 모든 path를 탐색해야 한다는 점에서 topological sort가 떠올랐다. 그러나 topological sort를 사용한 지 오래되어서 해당 구현은 이전에 쓴 게시글을 참고했다. topological sort의 큰 로직은 아래와 같다. source vertex..

23.04.08. 풀었던 문제들

Leetcode 133. Clone Graph Node pointer로 이루어진 graph 하나를 clone하는 문제. 중복된 edge는 없고, 각 Node가 가지고 있는 val은 unique하다는 조건에서 시작한다. 사실상 그렇게 어려운 문제는 아니다. DFS나 BFS를 쓰고, 그 과정에서 몇 줄만 추가해 주면 되는 문제. 첫 접근 일단 BFS로 풀었다. naive하게 2번의 BFS를 했다. 첫 BFS에서는 unvisit인 모든 Node에 대해 clone을 생성한다. 생성한 Node clone들을 value를 key로 가지는 map에 저장한다. ... 1 두 번째 BFS에서는 edge를 연결한다. 첫 번째 BFS에서 모든 Node를 찾았기 때문에 두 번째 BFS에서는 모든 clone들의 edge만 연결..

23.04.07. 풀었던 문제들

Leetcode 1020. Number of Enclaves 첫 접근 어제 풀었던 문제와 동일한 문제. boundary에 있지 않으면서 0으로 둘러싸여 있는 1을 찾는 문제이다. 어제는 추가 공간을 할당해 모든 island의 좌표를 추가로 저장했는데, 그렇게 말고 i번째 island가 enclave인지 여부, 그리고 i번째 island에 있는 1의 개수를 저장했다. // Runtime 87 ms Beats 30.50% // Memory 35.1 MB Beats 14.72% int dr[4] = {1, 0, -1, 0}; int dc[4] = {0, 1, 0, -1}; class Solution { public: int m, n; vector grid; vector visited; vector isEncl..

23.04.06. 풀었던 문제들

Leetcode 1254. Number of Closed Islands 많이 보던 grid에서 섬이 몇 개 있는지 탐색하는 문제이지만 추가 조건으로 모든 땅이 물 안에 있어야 하는 조건이 추가된다. 이 문제에서는 땅이 0, 물이 1로 표현되기에 모든 0으로 표현되는 연결된 영역이 모든 1 안에 있어야 한다. 이를 판별하는 법은 0으로 연결된 영역이 grid의 테두리가 아니면 된다. grid의 테두리가 아닌 0으로 영역된 섬들은 모두 1로 둘러싸여 있기 때문이다. DFS로 grid[r][c]가 0인 connected island를 모두 찾는다. 찾으면서 해당 좌표를 islands에 push한다. ... 1 DFS가 종료되면 모든 islands에 대한 정보를 찾은 것이다. islands의 모든 좌표를 순회하..

23.04.05. 풀었던 문제들

2439. Minimize Maximum of Array 첫 접근 오름차순인 부분수열에 대해 그들의 평균값이 될 수 있고, 남는 것을 균등히 분배할 수 있다. 1 3 5라면 -> 3 3 3이 될 것. 1 3 6라면 -> 3 3 4가 될 것. 1 3 7라면 -> 3 4 4가 될 것. 따라서 오름차순 부분수열을 찾고, [그 부분수열 합의 평균] + [나머지 존재 then 1 else 0]이 답일 것이라 생각했다. 그러나 [6, 9, 3, 8, 14]와 subarr를 바꾼 결과가 [7, 8, 8, 8, 9]처럼 또 오름차순인 경우에는 문제가 발생하며, strictly increasing이 아니라 monotonic increasing인 경우도 포함해야 한다. 그래서 이 접근은 틀린 접근이다. 다음 접근 전체 수..

23.04.04. 풀었던 문제들

Leetcode 2405. Optimal Partition of String 첫 접근 greedy로 풀었다. 어떤 index i를 탐색할 때, 지금까지 본 char가 아니라면 지금 string에 push, 한 번이라도 봤던 char라면 다음 string에 push하는 방법이다. 만약 이게 optimal이 아니라면 string의 길이가 더 길어져야 한다는 것인데, 그렇다면 한 string에서 모든 char가 unique하지 않게 되므로 모순. 따라서 optimal이다. // Runtime 325 ms Beats 5.4% // Memory 88 MB Beats 8.67% class Solution { public: int partitionString(string s) { int answer = 0, i = ..

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개이기 때문이다. 만약 어떤..

[개발서적] Clean Architecture 정리

Clean Code, The Pragmatic Programmer에 이어 Clean Architecture를 읽었다. Clean Architecture는 처음부터 끝까지 의존관계를 줄이는 방법을 소개하며 이를 통해 Open Closed Principle을 만족하는 유연한 프로그램을 작성하는 방법을 알려준다. 아직까지 느낀 점은 결국 중복을 없애고 DIP를 통해 추상화에 의존하게 작성하면 그것이 좋은 구조다는 것이다. 처음부터 끝까지 dependency에 관해 일관성 있게 이야기하기 때문에 하나 이상의 개발 프로젝트를 진행했던 개발자라면 자신이 진행했던 프로젝트의 구조와 dependency를 생각해 보는 계기가 될 것이다. 앞선 포스팅과 마찬가지로 감명깊게 읽은 부분, 필요하다고 생각하는 부분, 중요하다고..

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..