알루 코딩

오늘 소개할 문제는 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 이하의 거리 내에 있는 이웃 도시의 수가 가장 적은 도시를 찾아야 합니다..

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

오늘은 자료구조 설계에 대한 흥미로운 문제를 가져왔습니다. 겉으로 봤을 때는 해당 문제가 쉽게 풀릴 것입니다. 즉, O(1)이 아니고서는 문제 구현이 쉬울 것 입니다. 하지만, 이 문제에서는 O(1)의 시간 복잡도로 요소를 삽입, 삭제 및 무작위로 가져오는 자료 구조를 구현하는 것이 핵심입니다. 저는 이 문제를 처음 시도했을 때, 파이썬의 'set'자료구조를 사용했습니다. 'set'을 사용하면 삽입과 삭제는 평균적으로 O(1)의 시간 복잡도를 가지기 때문이죠.(자세한 이유는 이 링크를 참조하세요) 하지만, 문제는 getRandom() 메소드에 있었습니다. rand()와 같은 함수는 해시 집합에서 사용할 수 없기 때문에, 'set'을 'list'로 변환하는 과정이 필요합니다. 이 때, O(n) 시간이 걸리..

스택의 어원은 '쌓는다' 입니다. 어원에서 짐작할 수 있듯이, 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조입니다. 이렇게 먼저 들어간 것이 마지막에 나오는 규칙을 후입선출 혹인 LIFO(Last IN First Out)이라고 합니다. 이 때, 스택에 삽입하는 연산을 push, 꺼내는 연산을 pop 이라고 합니다. 📖 스택의 동작 원리 이해하기 빈 통(빈 스택)에 사탕을 넣는다고 하면, 아래와 같이 나타낼 수 있습니다. 📖 스택의 ADT ADT는 우리말로 추상 자료형(abstract data type)인데요, 추상 자료형이란 인터페이스만 있고 실제로 구현은 되지 않은 자료형입니다. 일종의 자료형의 설계도라고 생각하면 됩니다. 그렇다면 스택은 어떤 정의가 필요한 자료구조일까요? 우선 스택에는 ..