전체 글

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