알루 코딩

오늘 소개할 문제는 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) 시간으로 ..

오늘은 matrix 와 관련한 문제를 가져와봤습니다.해당 문제는 Hard 라고 표기되어 있지만, Medium 정도의 난이도로 잘 생각한다면 코드는 길어져도 풀 수 있는 문제입니다.문제 설명리트코드 2392번 Build a Matrix With Conditions 문제는 주어진 조건에 따라 k * k 행렬을 구성하는 문제입니다. 행과 열에 대한 조건이 주어졌을 때, 각 숫자가 주어진 순서에 맞게 매트릭스에 배치되어야 합니다.각 조건은 '[a,b]' 형태로 주어지며, rowConditions 에서는 숫자 'a'가 숫자 'b'보다 윗 행에 위치해야 하고, colConditions 에서는 숫자 'a'가 숫자 'b'보다 왼쪽 열에 위치해야 함을 의미합니다. 나머지 행렬위치에는 0으로 채우면 됩니다. 만약 만족하는..

오늘은 누적합과 관련한 SubArray의 수를 구하는 문제를 가져와봤습니다. 문제는 짧지만 구현하기는 쉽지 않습니다. 문제 이해부터 해보겠습니다. 주어진 정수 배열 'nums'와 정수 'k'가 있을 때, 합이 'k'와 같은 연속된 부분 배열의 개수를 찾는 것이 이 문제의 목표입니다. 예를 들어, num = [1,2,-1,3] 이고 , k = 2 인 경우에는 두 개의 부분 배열 [1,2,-1] 과 [2] 가 목표 합을 만족합니다. 즉 답은 2가 됩니다. 이 문제를 봤을 때 뭔가 누적합을 이용한 풀이를 생각할 수 있습니다. 하지만, 제한 조건을 봤을 때 시간복잡도도 고려해야 문제를 통과할 수 있을 것 같습니다. 또, 주어진 배열에서 연속된 부분 배열 중 합이 k인 경우의 수를 찾는 것이 핵심인데, 여기서 배..