궁금한게 많은 개발자 노트

해당 문제는 십진수를 담고 있는 이차원 배열로 주어진 삼각형 형태의 꼭지에서 삼각형의 제일 바닥까지 경로의 합 중 가장 작은 것을 반환하는 문제입니다. 만약 삼각형의 row번째에서 index의 원소를 택했다면, row+1번째에서는 index, index+1로만 움직일 수 있습니다.처음에는 삼각형 제일 위에서 아래로 BFS방식으로 모든 경로를 탐색하려 했으나, 시간 초과가 발생하여 가지 치기가 가능한 경우를 생각했지만 다음 row에 감소하는 경우가 있으므로 중간 경로에서 가지치기를 할 수 없었습니다.이에 반대로 올라가는 경우를 생각해보니, 문제에서 주어진 제약 조건처럼 O(n)의 공간 복잡도를 가지면서 처리를 하려면 DP(Dynamic Programing)로 해결해야 했고, 마지막 줄 기반으로 index,..

해당 문제는 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..