전체보기

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

[N2T] Naver2Tistory 리팩토링 시작

CS와 OOP, SOLID를 공부하거나 클린 코드 등 여러가지 개발 서적들을 읽으면서 내가 작성한 코드의 부족함을 느꼈다. 특히 Naver2Tistory의 경우 오픈소스로 배포했음에도 필요없는 부분이 많은 것 같아 리팩토링하려 한다. 목표는 [Naver2Tistory 이외에도, 확장성을 고려 + 유지보수하기 쉬운] 코드로 작성하고자 한다. 일단 해야 할 것 같은 부분은 아래 5개정도이다. 주석 삭제. 쓸데없는 주석을 좀 많이 적긴 했다. 공개되는 부분을 제외하고 내부 로직으로 돌아가는 부분은 삭제하는 게 좋을 것 같다. interface, polymorphism, map을 사용하는 방식 등 고민하고 확장성 있게 코드를 작성해 보자. 이 프로그램은 Naver2Tistory이지만 여러 가지 기능이 추가되어 ..

[개발서적] The Pragmatic Programmer 정리

Clean Code에 이어 The Pragmatic Programmer를 읽었다. 이 책은 개발자로써 어떠한 마음가짐을 가져야 하는지, 어떠한 방법을 사용해야 하는지에 대해 매우 개략적으로만 다룬다. 주변에서 이제 막 프로젝트를 하나 끝낸 개발자 지망생들에게 한 번씩 읽어보라고 추천하고 싶은 책이다. 현대 개발론에서 사용하는 agile, prototype, CICD, TDD, DDD 등에 대한 내용을 한 단락으로 정리하기 때문에 개발하면서 불편했던 점을 이렇게 해결할 수 있구나, 하는 큰 방향성을 제시해 주기 때문이다. Clean Code 포스팅과 마찬가지로 감명깊게 읽은 부분, 내게 필요하다고 생각하는 부분만 간단하게 정리했다. 그 중에서도 중요하다고 느낀 문장은 *를 쳐서 표기했다. 서문 개발자는, ..

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.21. 풀었던 문제들

Leetcode 2348. Number of Zero-Filled Subarrays 첫 접근 [0으로 이루어진 연속된 max subarray]를 찾고, 그 subarray가 가지는 [0으로 이루어진 subarray]는 1 + 2 + ... + [해당 array length]이다. [0으로 이루어진 연속된 max subarray]를 찾고 계산하면 늦을 것 같아 미리 1부터 n까지 합을 prefix sum으로 계산해 두었다. 이후 탐색을 시작하며, [현 index]가 0인 경우에 더 이상 0이 아닐 때까지 i를 더해 0으로 이루어진 max subarray를 찾는다. 이후 계산한 값을 가져온다. // Runtime 255 ms Beats 5.13% // Memory 150.3 MB Beats 6.34% typ..

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 다음 것부터 복사해 ..

[개발서적] 다시 쓰는 Clean Code 정리

개발에 대해 아무것도 모를 때 읽었던 Clean Code와 어느 정도 경험을 쌓고 나서 다시 보는 Clean Code는 느낌이 달랐다. 직접 프로그램을 유지보수하지 않고 개발만 했던 시절에는 모든 내용이 내 머리속에 있었기 때문에 "대체 왜 interface를 사용하는 거지? 굳이? 그냥 수정하면 되는 거 아닌가?"라고 생각했다. 지나고 보니 우매한 생각이었다. 여러 프로그램을 유지보수하다보니 요구사항을 반영할 때 기존 코드를 최소한으로 만져야 하고, dependency가 꼬여있지 않아 추가하고 싶은 기능만 추가하는 것의 중요성을 깨달았다. 기존 코드가 난잡하면 유지보수 하는데는 훨씬 많은 cost가 든다는 걸 개발병을 하면서 너무 많이 겪었다. 나는 소스 코드는 하나의 글이라 생각한다. 잘 쓴 글은 서..

23.03.19. Clean Code 읽은 후 목표 - 끝!

리팩토링 저번에 작성한 글의 계획을 따라 Java, OOP, Solid Principles를 정리했고 이번 주는 Clean Code를 읽고 정리하고 있다. 읽다 보니 내가 지금까지 작성한 게 Clean Code가 맞나?라는 생각이 들었고 전부 다는 못 되더라도 내가 작성한 코드를 내가 책임져야 한다는 생각이 들었다. 지금 github에 올라가 있는 프로젝트는 크게 Meerkat, Bizkicks, Naver2Tistory, Pocarpool의 4가지이다. 이 중에서 실 배포되고 있는 코드는 Naver2Tistory 하나 뿐이고 나머지는 모두 팀으로 작성한 코드이기 때문에 일단 Naver2Tistory부터 리팩토링을 해보려 한다. 리팩토링 할 부분은 크게 4가지 정도인 것 같다. 주석 삭제. 쓸데없는 주석..

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인 경우 넣지 않음..

[OOP] SOLID 정리

앞선 게시글에서 객체지향 설계 원칙인 SOLID Principle에 대해 알아보았다. 이 글에서는 SOLID Principle을 사용해야 하는 이유, 그리고 각각의 원칙들의 연관성에 대해 조금 살펴본다. 왜 설계 원칙이 중요할까? 사용자 요구사항의 변경은 정말 시시때때로 이루어진다. 요구사항이 바뀌면 한숨부터 나오는 것은 사실이다. 그렇지만 이러니저러니 해도 결국 그 요구사항을 받아들여 프로그램을 수정해야 한다. 왜? 결국 프로그램을 사용하는 건 사용자니까. 이런저런 요구사항을 전부 수정하다보면 코드가 꼬이는 일도 비일비재하다. 초기에는 깨끗한 설계도 이것저것 덧붙이다 보면 지저분해지기 마련이니까. 그래서 더더욱 유지보수성과 확장성이 높으면서도 버그가 적게 발생할 수 있는 좋은 설계가 중요하다. SOLI..

[OOP] SOLID - Dependency Inversion Principle

이 글은 객체지향 5대 원칙, SOLID principle 중 D인 Dependency Inversion Principle, 의존성 역전 원칙에 대해 알아본다. 정의 dependency를 가지는 component가 구현체가 아닌 추상화에 의존해야 한다는 원칙이다. 각 모듈들이 dependency를 가질 때(상위 module이 하위 module을 사용할 때) concretion이 아닌 abstraction에 의존해야 한다. abstraction은 concretion에 의존하면 안 된다. concretion은 abstraction에 의존해야 한다. 결국 모든 경우에 abstraction에 의존해야 한다. 예전의 설계는 상위 module이 하위 module의 concretion을 직접적으로 사용하며, 이 때 ..

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

[OOP] SOLID - Interface Segregation Principle

이 글은 객체지향 5대 원칙, SOLID Principle 중 Interface Segregation Principle에 대해 다룬다. 정의 Interface Segregation Principle은 object는 자신이 사용하지 않는 method를 포함한 interface에 의존하면 안 된다는 원칙이다. 이 원칙은 dependency와 overhead에 대한 이야기이다. 언제 사용해야 할까? 만약 어떤 class C가 interface I를 implement하는 예시를 생각해 보자. interface I에는 method A, B, C 등 여러 가지 method가 있다. 그러나 class C는 method A밖에 사용하지 않는다. 이 경우 class C에서는 사용하지 않는 method B, method ..

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

[OOP] SOLID - Liskov Substitution Principle

이 글은 객체지향 5대 원칙, SOLID principle 중 L인 Liskov Substition Principle을 다룬다. 정의 subtype이 항상 supertype로 치환할 수 있어야 한다는 원칙이다. 이 원칙은 polymorphism에 관련된 이야기이다. 다르게 설명하자면 supertype을 사용하는 위치에 subtype을 넣어도 프로그램 수행에는 변화가 없어야 한다는 말이다. 따라서 supertype에서 사용하는 method는 subtype에서도 사용할 수 있어야 한다. polymorphism을 공부했다면 method overriding과 upcasting에 대해 이미 알고 있을 것이다. Liskov Substitution Principle를 따른다면 upcasting한 상태에서 parent..