soicem's note

문제: leetcode.com/problems/guess-number-higher-or-lower-ii/ Guess Number Higher or Lower II - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com MINMAX 알고리즘을 사용하는 문제. 어떤 수를 선택하던 상관없이 무조건 이길 수 있는 최소의 돈의 양을 return 해야한다. from i to j에서 사이의 값인 k를 택했을 때 i ~ k -1과 k + 1 ~ j 중에서 최악의 경우의 수를 찾으면..

booking 문제. My Calendar 1: leetcode.com/problems/my-calendar-i/ My Calendar I - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com class MyCalendar { public: vector reserves; MyCalendar() { } bool book(int start, int end) { for(auto reserve : reserves){ int oldStart = reserve[0]; int ..

문제: leetcode.com/problems/find-root-of-n-ary-tree/ mock interview를 수행하다가 막혀서... 문제 자체를 제대로 이해못했다. 조건이 findRoot는 A arbitrary order 속성을 가진 array에서 root를 찾는 문제이며 findRoot는 drive code다. 즉, serialized input data -> a arbitrary order array -> find root -> make a serialized date by using a root node 이런 흐름이다. root는 parent가 없으므로 parent가 없는 Node를 arbitrary한 order를 가진 array에서 찾으면 된다. set이나 visited array를 두..

문제: leetcode.com/problems/longest-increasing-subsequence/ Longest Increasing Subsequence - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com LIS 문제인데 O(nlogn) 해답이 재밌다. 처음에는 각 요소별로 재귀 진입해서 LIS를 하되 cache로 memoization을 해주는 O(N^2) 정도가 직관적으로 떠오른다. 더 최적화하면 LIS를 additional space에 만들고 해당 spa..

문제: leetcode.com/problems/candy/ Candy - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 적어도 1명의 아이는 1개의 캔디를 가져야하고 자기 옆에있는 친구보다 낮은 rating을 가졌으면 반드시 적은 캔디를 가져야한다. 반대로 rating이 높으면 많은 캔디를 가져야 한다. 기본적으로 V자일 때 두 선분이 만나는 점에서 상대적 rating을 확인하는 작업이 들어간다. 4가지 정도 cases가 있는데 중요한 점은 V자 일때 아래의 점..

문제: leetcode.com/problems/bulls-and-cows/ 문자열 중 같은 position에 있으면 A, 아니면 자리는 같지 않더라도 같은 값이 다른 포지션에 있을 경우 B다. class Solution { public: string getHint(string secret, string guess) { unordered_map m; int A = 0; int B = 0; for(int i = 0; i < secret.size(); i++){ if(secret[i] == guess[i]){ A++; secret[i] = ' '; guess[i] = ' '; } else { m[secret[i]]++; } } for(int i = 0; i < guess.size(); i++){ char c ..

문제: leetcode.com/problems/design-search-autocomplete-system/ 검색 시에 매칭되는 문자열들을 자동으로 완성시켜주는 알고리즘 구현이다. 검색창에서 특정 문자를 치면 해당 문자를 prefix로 포함한 문자열들을 나열해주는 것과 같다. 처음에 몇 번 입력했었다는 조건이 주어지며, 문자열을 검색할 때마다 카운트가 증가되는 것을 반영해주면 된다. 한 문자를 입력할 때마다 출력해야한다. 예시에서 보면 "I love you"라는 문자열을 추가적으로 입력했다. 이후에는 "I love you"라는 문자열의 times가 5에서 6으로 증가하며 이를 반영해서 문자열 추천을 해줘야한다. class AutocompleteSystem { public: priority_queue pq..

문제: leetcode.com/problems/insert-delete-getrandom-o1/ Insert Delete GetRandom O(1) - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com class RandomizedSet { public: /** Initialize your data structure here. */ unordered_map h; list lst; RandomizedSet() { } /** Inserts a value to the s..

link: leetcode.com/problems/serialize-and-deserialize-binary-tree/ Input: root = [1,2,3,null,null,4,5] Output: [1,2,3,null,null,4,5] /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Codec { public: string serializeLoop(TreeNode* node){ // from left to right if(!node){ ..

3주간의 겨울계절학기가 끝나고 2주정도 회사에 적응하며 시간을 보냈다. COVID-19 때문에 재택하고있는 상황이며, 남는 시간을 이용하여 학기중에 미뤄뒀던 공부들을 재개하고 끝나면 LLVM을 사용하여 컴파일러를 만들어볼까 생각한다. 주요 주제는 2가진데, 객체지향 디자인패턴과 TDD(Test Driven Development)다. 객체지향 디자인패턴은 3학년 2학기 소프트웨어 공학을 들으면서 추가 공부의 필요성을 느꼈고 방학때 보려했으나 인턴을 하는 바람에 2021년까지 지연되었다. 2학기 중에는 20학점에 교수님께 권유받아 금융 프로그래밍 관련 part time job을 했었고, 소프트웨어 교육센터에서 머신러닝 관련 R&D를 수행하였다. 금융 관련 part time job 도중에 팩토리 메소드 패턴 ..