알루 코딩

오늘 소개할 문제는 LeetCode 40번 문제 "Combination Sum II"입니다. 이 문제는 전형적인 백트래킹 문제라고 판단해서 실수할 수 있는 문제입니다. 백트래킹 알고리즘에서 어떤 부분을 주의해야 할지, 최적화는 어떻게 하면 좋은지에 대한 실마리를 포함하고 있는 문제입니다. 아래의 한 유저가 말씀해주신 것 처럼, 대부분의 회사의 채용 코딩인터뷰 문제 목록에 포함되어 있는 문제이기도 합니다. 문제 설명리트코드 40번 Combination Sum II 문제에서는 중복된 숫자가 포함된 배열에서 합이 특정 목표값(target)이 되는 모든 고유한 조합을 찾아야 합니다. 주어진 배열의 각 숫자는 한 번만 사용할 수 있으며, 같은 조합이 중복되어 결과에 포함되지 않도록 해야 합니다.문제 해결 과정1...

오늘 소개할 문제는 LeetCode 1334번 문제 "Find the City With the Smallest Number of Neighbors at a Threshold Distance"입니다. 이 문제는 그래프 이론과 최단 경로 알고리즘을 이해하는 데 중요한 문제로, 특히 다익스트라 알고리즘을 활용합니다.문제 설명리트코드 1334번 Find the City With the Smallest Number of Neighbors at a Threshold Distance 문제에서는 n개의 도시와 도로 정보(edges)가 주어집니다. 각 도로는 두 도시를 연결하며, 그 사이의 거리가 주어집니다. 주어진 distanceThreshold 이하의 거리 내에 있는 이웃 도시의 수가 가장 적은 도시를 찾아야 합니다..

오늘은 머지소트와 관련한 문제를 가져와봤습니다. 해당 문제는 Medium 난이도이지만, 어떠한 내장함수도 사용하지 않고, O(nlogn) 시간복잡도로 풀어야 하는 것이 관건입니다. 문제 설명리트코드 912번 Sort an Array 문제는 주어진 정수 배열을 오름차순으로 정렬하는 알고리즘을 구현하는 것입니다. 배열에는 중복된 값이 포함될 수 있으며, 출력 시 동일한 값의 순서는 그대로 유지되어야 합니다. 이는 기본적인 정렬 알고리즘을 연습하는 데 중요한 문제로, 다양한 정렬 기법을 활용할 수 있습니다. 다시 한번 강조하지만, 어떠한 내장함수도 사용하면 안됩니다. 즉, 이 문제는 정렬 함수를 쓰지 않고 직접 정렬 알고리즘을 구현할 수 있는지의 능력을 판단하려고 하는 것 같습니다. O(nlogn) 시간으로 ..

오늘은 어렵지 않습니다만, 삽질할 가능성이 있는 문제에 대해 다뤄보겠습니다. 이 문제는 알고리즘 복잡도와 효율적인 자료구조 사용에 대한 이해를 시험하는 좋은 연습이 될 것입니다. 해당 문제에서는 주어진 배열 nums 를 비우기 위해 필요한 최소 작업 횟수를 찾는 것입니다. 각 작업에서 nums 내의 똑같은 숫자를 제거할 수 있는데, (2개를 삭제하든지 3개를 삭제하든지) 둘 중 하나의 operation(연산)을 수행하면 서 nums 의 원소들을 제거하는 원리입니다. 최종적으로 nums 가 비워질 때까지 연산을 계속해서 하되, 최소의 연산으로 nums 를 비워야 하고, 이 때 이 최소의 연산 횟수를 반환하는 문제입니다. 제가 처음 접근한 방식은 각 숫자의 빈도수를 계산하여 동적 프로그래밍(DP)를 사용하는..

이 문제는 비교적 간단하지만, 간단하게 풀면 시간초과에 걸리기 때문에 조금은 생각을 해야 하는 문제입니다. 문제에서는 정렬된 정수 배열 nums가 주어집니다. 배열의 각 요소 'i' 에 대해, 해당 요소와 배열 내 다른 모든 요소 'j' 들과의 절대 차이인 |nums[i] - nums[j]| 의 합을 구하는 것이 목표입니다. 이 문제에서 각 원소를 순회하면서 절댓값 계산을 하면 nums의 길이가 10**5 까지 있기 때문에 시간초과가 날 수 밖에 없습니다. 이 문제를 효율적으로 해결하기 위해서는 누적합(prefix)와 역누적합(suffix)를 사용해야 합니다. 누적합(prefix sum)과 역누적합(suffix sum)의 사용은 꼭 알아야 하는 알고리즘 중에 하나입니다. prefix sum에 대해 잠시 ..