궁금한게 많은 개발자 노트

해당 문제는 십진수를 담고 있는 이차원 배열로 주어진 삼각형 형태의 꼭지에서 삼각형의 제일 바닥까지 경로의 합 중 가장 작은 것을 반환하는 문제입니다. 만약 삼각형의 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인 숫자가 배열에 존재하지 않으면 시작점으로 판단하고 하나씩 증가시키며 배열에 존재할 때까지의 길이를 비교하며 제일 ..

해당 문제는 두 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가 존재한다는 의미입니다. 첫번째 변수가 채워졌는데 배열에서 다음 값이 더 작다면 다시 첫변수를 업데이트해주고, 더 크다면 두번째를 채우고, 두번째보다 더 큰 값이 나오면 조건을 만족한다고..