궁금한게 많은 개발자 노트

해당 문제는 LRU Cache의 put/get동작을 직접 구현하는 문제로 LRU란 Least Recently Used원칙으로 cache를 유지하는 규칙을 뜻합니다. 즉 cache의 capacity가 가득 찼을 때 put일 들어오면, 가장 최근에 접근하지 않은 content를 삭제하고, 최근에 접근한 것들의 우선순위를 높이는 방식입니다. (새로 추가되면 가장 우선순위가 높음) Linked List와 hash table을 활용하여 구현하였습니다. Linked List의 head, tail을 사용하여 가장 최근에 사용한 content를 head에 두고, 우선순위가 가장 낮은 것은 tail에 있습니다. double linked list로 구현하여 hash table에 (key, node)로 저장해두어 key로 ..

해당 문제는 숫자로 이루어진 배열에서, 순서와 상관없이 배열 내 숫자 중 연속되어 증가하는 숫자들이 존재하는 것들 중 가장 긴 길이를 반환하는 문제입니다. 예를 들면 [100, 4, 200, 1, 3, 2]의 배열에서는 1,2,3,4가 연속하며 증가하는 가장 긴 숫자들이므로 4가 정답입니다. 이 문제를 해결하기 위해서는 우선 배열을 오름차순으로 정렬하고 나서 보면 연속되는 부분 배열들을 살펴보면 1,2,3,4와 100 그리고 200 이렇게 세 부분 배열로 나눌 수 있습니다. 이 경우에 각 시작점의 특징은 해당 숫자보다 -1인 숫자가 배열 내에 존재하지 않는다는 특징이 있습니다. 그래서 -1인 숫자가 배열에 존재하지 않으면 시작점으로 판단하고 하나씩 증가시키며 배열에 존재할 때까지의 길이를 비교하며 제일 ..

해당 문제는 Node로 구성된 Graph를 그대로 복제한 그래프를 반환하는 문제입니다. 기존에 주어진 Node를 그대로 반환하면 안되고 새로 생성하여 반환해야 합니다. BFS를 사용하여 Root Node에서 출발하여 해당 노드를 복제하고, 인접한 노드들을 Queue에 추가하고 다시 반복하는 방식으로 구현하였습니다. 이 과정에서 Hash Table을 사용하여 기존 Node가 key가 되고 새로 복제된 Node를 value로 추가하여 방문한 인접노드를 중복으로 생성하거나 BFS Queue에 추가하는 것을 방지하였습니다. /* // Definition for a Node. class Node { public: int val; vector neighbors; Node() { val = 0; neighbors =..

해당 문제는 두 Linked List가 주어지고, 각 링크드 리스트의 노드는 숫자를 나타내고 있으며 각 숫자는 head 부터 tail까지 한 숫자의 각 자릿수를 나타냅니다. 두 링크드 리스트의 숫자를 더한 결과의 링크드 리스트를 반환하는 문제입니다. 일반적으로 두 수의 덧셈은 가장 아랫자리부터 덧셈이 이루어지므로 stack에 각 링크드 리스트의 숫자를 넣어 가장 아랫자리부터 나올 수 있도록 준비하고 덧셈의 결과 값도 마찬가지로 stack에 넣어 링크드 리스트로 하나씩 빼내며 만들 수 있습니다. /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(n..

해당 문제는 숫자로 이루어진 배열에서, 서로 다른 인덱스 i, j, k가 i < j < k관계를 이루고, index에 존재하는 값도 nums[i] < nums[j] < nums[k]를 이루는 i, j, k가 존재하는지 여부를 판단하는 문제입니다. 연속성을 가질 필요는 없지만 해당 조건을 만족하기 위해서는 두 변수가 필요하고, 한 변수에는 가장 작은 값을 업데이트하고, 두 번째 변수에는 첫 변수보다 높은 값이 나타나면 업데이트, 그리고 세번째 아이템을 만났을 때 두번 째 변수보다 크다면 해당 조건을 만족하는 i, j, k가 존재한다는 의미입니다. 첫번째 변수가 채워졌는데 배열에서 다음 값이 더 작다면 다시 첫변수를 업데이트해주고, 더 크다면 두번째를 채우고, 두번째보다 더 큰 값이 나오면 조건을 만족한다고..