j-engine 님의 블로그

이 문제는 Linked-List를 뒤집는 문제입니다. 이전 노드, 현재 노드, 다음 노드를 각각 추적하며 각 노드가 가르키는 방향을 바꿔줍니다./** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */class Solution {public: ListNode* reverseList(ListNode*..

이 문제는 날짜 별로 주식의 가격이 적힌 배열이 주어집니다.그러면 어떤 날에 주식을 산 후 다른 날에 주식을 팔 때 가장 큰 이익이 얼마인지 찾는 문제입니다. 간단하게 하루하루가 지날 때마 가장 가격이 낮을 때를 사는 날로 정하고 가장 낮은 가격을 갱신해줍니다.이때 갱신한 날이 주식을 산 날입니다.이루 하루가 지날때마다 가장 낮은 가격을 빼 이득을 계산하며 최대 이득을 갱신해줍니다.  int maxProfit(vector& prices) { int profit = 0; int minPrice = prices[0]; // 첫날은 팔 수 없습니다. for (int i = 1; i

정렬된 Linked-List가 주어질 때 중복된 값을 가진 노드들을 삭제하는 문제입니다. 만약 다음(next) 노드가 현재 노드의 값과 같은 값을 가지면 두 노드는 중복된 것 입니다.중복된 노드를 유일한 노드로 만들어야 하므로 다음 노드를 삭제하고 그 다음 노드에 현재 노드의 next를 연결합니다.이 과정을 List의 끝까지 반복하면 중복된 노드들을 지울 수 있습니다. /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {}..

이 문제는 Linked-List에서 원하는 값을 전부 삭제해야하는 문제입니다. 찾는 값이 리스트 중간에 있는 경우 이전 노드의 next를 다음 노드에 연결한 다음 현재 노드를 삭제합니다.즉, 이전 노드를 추적하는 포인터가 필요합니다.또한, 만약 찾는 값이 중간이 아닌 맨 앞에 있으면 이전 노드를 추적할 필요 없이 head를 다음 노드로 만들고 맨 앞 노드였던 노드를 삭제해줍니다. 이렇게 두 과정을 차례대로 진행해주면 되는데 먼저 맨 앞에 있는 경우를 처리하고 리스트 중간에 있는 경우를 처리해주면 됩니다. /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(..

이 문제는 Linked-List가 주어졌을 때 이 리스트가 Palindrome인지 확인하는 문제입니다.Palindrome이란 보통 'eye', 'madam', '다시합시다' 등과 같이 역순으로 읽어도 같은 말이나 구절 또는 숫자를 의미합니다.이를 List에 대입하면 거꾸로 읽어도 같은 구조를 의미할 수 있습니다. 아주 간단하게 생각하면 리스트를 역순으로 하나 생성한 뒤 원래 리스트와 비교해 같은지 확인하는 방법이 있습니다.하지만 조금 더 빠르게 할 수 있는 방법도 있습니다. Palindrome은 역순으로 읽어도 같기 위해 반으로 나누었을때 뒤의 절반을 역순으로 만들면 앞의 절반과 뒤의 절반의 역순이 같습니다. 쉽게 생각해서 중간을 기준으로 반으로 접을때 같으면 Palindrom이라는 의미입니다. 그래서 ..

이 문제는 Linked-List가 주어졌을 때 리스트에 Cycle이 존재하는지 찾는 문제입니다.Cycle이란 이전에 방문했던 곳을 연결된 노드를 타고 갔을 때 다시 방문하게 되어서 결국 계속해서 도는 구간을 의미합니다. 노드의 값에 음수도 존재하기에 unordered_map을 활용해 이전에 노드를 방문한 적이 있는지 확인해 재방문하는 것이라면Cycle로 판단하는 구조로 문제를 풀었습니다. /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ bool hasCycle(ListNode ..

이 문제는 Linked-List에서 중간에 있는 노드를 찾아 반환하는 문제입니다.만약 배열이면 배열의 크기를 찾아 반으로 나눠 쉽게 중간값을 찾을 수 있습니다.하지만 Linked-List는 index가 아닌 포인터로 연결되어 있기에 포인터를 사용해야 합니다. 이때 Slow and Fast Pointer라는 걸 사용할 수 있습니다. 런너 기법이라고도 불립니다.Slow는 한 번에 한 칸씩 이동하는 포인터이고 Fast는 한 번에 두 칸씩 이동하는 포인터입니다.Slow 포인터가 한 칸 이동할 때 Fast 포인터는 두 칸 이동하므로 Fast 포인터가 Linked-List의 맨 마지막 노드혹은 nullptr에 도달하면 Slow 포인터는 Linked-List의 중간에 도달하게 됩니다. While Loop를 통해 Sl..

이 문제는 정수 배열이 NumArray 클래스를 초기화할 때 주어지면 이를 사용해 NumArray 클래스의 sumRange 함수를 완성하는 것 입니다.sumRange함수는 정수 left, right가 주어지면 이를 index로 활용해 left  가장 간단하게 풀려면 매번 sumRange가 호출될 때마다 loop를 돌며 값의 합을 구하면 됩니다.class NumArray {public: NumArray(vector& nums) :nums(nums) { } int sumRange(int left, int right) { int sum = 0; while (left nums;};/** * Your NumArray object will be instantiated and c..

계단을 올라갈 때 n번째까지 갈 수 있는 방법의 수를 물어보는 문제입니다.계단을 오를때 제한이 있는데 한 번에 1칸 또는 2칸씩 오를 수 있습니다. 이 뜻은 n번째 계단에 가기 위해서는 n-1번째 계단에서 1칸을 올라가거나 n-2번째 계단에서 2칸을 오를 수 있습니다.이를 쉽게 Recursion으로 풀 수 있습니다.  int climb(int n) { if (n == 0 || n == 1) // 안오르거나, 가장 첫 1칸 return 1; // 방법의 수는 1 // n번째 계단을 오르려면 n-1에서 한칸 또는 n-2에서 두 칸씩 오르면 된다 return climb(n - 1) + climb(n - 2); }(이 방..

이 문제는 트리를 좌우구조를 뒤집어주는 문제입니다.전체 트리 구조를 뒤집기위해 각각의 노드를 어떻게 해야할지 살펴보면 결국 각 노드의 왼쪽 자식과 오른쪽 자식 노드를 바꿔주면 됩니다.모든 노드의 자식 노드들을 바꿔줘야 하므로 DFS를 사용했습니다. Recursion/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * ..