수달씨의 개발공간

[LeetCode] Integer to Roman - 탐욕법(Greedy) 활용한 숫자 변환

📌 문제 설명

LeetCode의 "Integer to Roman" 문제는 주어진 정수를 로마 숫자로 변환하는 문제입니다.

• 입력: 정수 num
• 출력: 해당 정수를 로마 숫자로 변환한 문자열

🔹 로마 숫자 기본 규칙

숫자 로마 숫자

✅ 일반적인 로마 숫자는 큰 값부터 작은 값 순서로 표현됩니다.
예) 58 → LVIII (50 + 5 + 3)

🔹 예외 규칙 (뺄셈 적용)

숫자 로마 숫자 설명

✅ 특정 숫자(4, 9, 40, 90, 400, 900)는 작은 숫자가 큰 숫자 앞에 와서 뺄셈 역할을 합니다.

📌 해결 방법 (탐욕법 - Greedy Algorithm)

💡 핵심 아이디어

1. 큰 숫자부터 차례대로 변환해야 하므로 탐욕법(Greedy Algorithm) 활용
2. 큰 숫자부터 하나씩 확인하며 num에서 해당 값을 빼면서 로마 숫자 추가
3. 숫자가 0이 될 때까지 반복

✅ 코드 구현 (O(N) 복잡도)

export function intToRoman(num: number): string {
  // 1️⃣ 큰 값부터 매칭할 수 있도록 배열을 생성
  const romanMap: [number, string][] = [
    [1000, "M"],
    [900, "CM"],
    [500, "D"],
    [400, "CD"],
    [100, "C"],
    [90, "XC"],
    [50, "L"],
    [40, "XL"],
    [10, "X"],
    [9, "IX"],
    [5, "V"],
    [4, "IV"],
    [1, "I"],
  ];

  let result = "";

  // 2️⃣ 큰 값부터 순회하면서 숫자를 변환
  for (const [value, symbol] of romanMap) {
    while (num >= value) {
      result += symbol; // 3️⃣ 해당 로마 숫자를 추가
      num -= value; // 4️⃣ 숫자를 감소
    }
  }

  return result;
}

📌 예제 실행 과정

입력: num = 1994

1. 1994 >= 1000 → M 추가 → num = 994
2. 994 >= 900 → CM 추가 → num = 94
3. 94 >= 90 → XC 추가 → num = 4
4. 4 >= 4 → IV 추가 → num = 0

✅ 출력: "MCMXCIV"

📌 테스트 코드

describe("Integer to Roman", () => {
  it("converts numbers correctly", () => {
    expect(intToRoman(3)).toEqual("III");
    expect(intToRoman(58)).toEqual("LVIII");
    expect(intToRoman(1994)).toEqual("MCMXCIV");
  });
});

✅ 모든 테스트 케이스 통과! 🚀

📌 시간 복잡도 분석

연산 복잡도 설명

✅ 탐욕법을 활용하면 O(N)으로 최적화 가능! 🚀

📌 최종 정리

1. 큰 숫자부터 차례대로 로마 숫자로 변환해야 함 → 탐욕법 사용
2. 큰 값부터 매칭하는 배열을 만들고, 현재 숫자가 크면 반복해서 뺀다.
3. O(N) 시간 복잡도로 효율적으로 해결 가능!

💡 이제 유사한 문제에서도 "큰 값부터 탐욕적으로 처리하는 방식"을 고려해 보세요! 🚀

#LeetCode #IntegerToRoman #알고리즘 #TypeScript #탐욕법

[LeetCode] Trapping Rain Water - 효율적인 해결 방법 (Two Pointers)

📌 문제 설명

LeetCode의 "Trapping Rain Water" 문제는 높이 배열(height[])이 주어질 때, 빗물이 고일 수 있는 총량을 계산하는 문제입니다.

• height[i]: 각 기둥의 높이
• 각 기둥의 너비는 1로 고정
• 빗물이 얼마나 고일 수 있는지 계산해야 함

📌 문제 해결 과정

✅ 잘못된 접근 (Brute Force, O(N²))

모든 인덱스에서 왼쪽 최대(leftMax)와 오른쪽 최대(rightMax) 를 찾아 빗물을 계산하는 방법이 떠오를 수 있습니다.

export function trap(height: number[]): number {
  let water = 0;

  for (let i = 1; i < height.length - 1; i++) {
    const leftMax = Math.max(...height.slice(0, i + 1));
    const rightMax = Math.max(...height.slice(i));

    water += Math.max(0, Math.min(leftMax, rightMax) - height[i]);
  }

  return water;
}

🚨 문제점:

• Math.max(...arr)를 반복 호출해야 하므로 시간 복잡도 O(N²) 발생
• 배열이 길어질수록 매우 비효율적

📌 최적화된 해결 방법 (Two Pointers, O(N))

💡 핵심 아이디어: "양쪽에서 중앙으로 이동하며 작은 쪽을 기준으로 계산"

1. leftMax와 rightMax를 유지하면서 한 번의 순회로 해결
2. 작은 쪽(leftMax 또는 rightMax)을 기준으로 물을 계산
3. 양쪽 끝에서 중앙으로 이동하면서 빗물을 계산 (O(N))

✅ 작은 쪽을 기준으로 계산하는 이유:

• leftMax < rightMax라면 leftMax보다 높은 곳이 나오기 전까지 leftMax가 현재 위치에서 최대 물 저장 가능 높이
• 반대로 rightMax < leftMax라면 rightMax가 현재 위치에서 최대 물 저장 가능 높이

📌 최적화된 코드 (O(N))

export function trap(height: number[]): number {
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let water = 0;

  while (left < right) {
    if (height[left] < height[right]) {
      leftMax = Math.max(leftMax, height[left]);
      water += leftMax - height[left];
      left++;
    } else {
      rightMax = Math.max(rightMax, height[right]);
      water += rightMax - height[right];
      right--;
    }
  }

  return water;
}

📌 예제 분석

입력:

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];

Step-by-step 실행 과정

left right leftMax rightMax water 설명

✅ 최종 결과: 6 (가둘 수 있는 물의 양)

📌 시간 복잡도 분석

접근법 시간 복잡도 설명

✅ Two Pointers 사용하면 O(N)으로 해결 가능! 🚀

📌 최종 정리

1. 각 위치에서 고일 수 있는 물의 양 = min(leftMax, rightMax) - height[i]
2. 모든 인덱스에서 leftMax와 rightMax를 찾는 것은 O(N²)로 비효율적
3. "양쪽 끝에서 중앙으로 이동하면서 작은 쪽을 기준으로 물을 계산"하면 O(N)으로 해결 가능
4. O(N) 탐욕법(Two Pointers)로 해결 가능!

💡 이제 비슷한 문제에서 "양쪽에서 중앙으로 이동하는 방식"을 떠올려 보세요! 🚀

[LeetCode] Gas Station - 탐욕법(Greedy)으로 해결하기

📌 문제 설명

LeetCode의 "Gas Station" 문제는 각 주유소에서 얻을 수 있는 연료(gas)와 이동에 필요한 연료(cost)가 주어질 때, 전체 주유소를 한 바퀴 돌 수 있는 출발점을 찾는 문제입니다.

• gas[i]: i번째 주유소에서 얻을 수 있는 연료량
• cost[i]: i번째 주유소에서 다음 주유소로 이동하는 데 필요한 연료량
• 한 바퀴를 돌 수 있다면 출발 가능한 주유소의 인덱스 반환, 불가능하면 -1 반환
• 해결 가능한 경우는 유일함이 보장됨

📌 문제 해결 과정

✅ 직관적인 접근 (O(N²) 비효율적 방법)

처음에는 모든 주유소에서 출발을 시도하면서 한 바퀴를 도는 방식을 생각할 수 있습니다.

export function canCompleteCircuit(gas: number[], cost: number[]): number {
  let total = 0;
  const len = gas.length;

  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      const current = (i + j) % len;
      total += gas[current] - cost[current];
      if (total < 0) {
        total = -1;
        break;
      }
    }
    if (total >= 0) {
      return i;
    }
  }
  return -1;
}

하지만, 이 방식은 모든 주유소에서 출발을 시도하면서 한 바퀴를 도는지 확인하므로 O(N²) 시간이 걸려 비효율적입니다.

📌 최적화된 해결 방법 (탐욕법 - Greedy, O(N))

🚀 핵심 아이디어

1. 총 연료량(sum(gas))이 총 비용량(sum(cost))보다 작으면 절대 불가능 → -1 반환
2. 연료가 부족하면 출발점을 다음 주유소로 변경 (이전 주유소에서는 절대 출발 불가능)
3. 연료가 남아있다면 현재 출발점 유지

📌 코드 (O(N))

export function canCompleteCircuit(gas: number[], cost: number[]): number {
  let totalGas = 0;
  let totalCost = 0;
  let startIndex = 0;
  let currentGas = 0;

  for (let i = 0; i < gas.length; i++) {
    totalGas += gas[i];
    totalCost += cost[i];
    currentGas += gas[i] - cost[i];

    // 연료 부족 시, 출발 지점을 다음 주유소로 변경
    if (currentGas < 0) {
      startIndex = i + 1;
      currentGas = 0; // 새로운 출발점에서 다시 시작
    }
  }

  return totalGas >= totalCost ? startIndex : -1;
}

📌 코드 실행 과정 예제

입력:

gas  = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]

Step-by-step 실행 과정

i gas[i] cost[i] currentGas (남은 연료) startIndex (출발점)

✅ 최종 반환값: 3 (index 3에서 출발하면 한 바퀴 가능)

📌 시간 복잡도 분석

접근법 시간 복잡도 설명

✅ 탐욕법을 사용하면 O(N)으로 해결 가능! 🚀

📌 최종 정리

• 총 연료량 < 총 비용량이면 절대 불가능 (-1 반환)
• 연료 부족 시 출발 지점을 다음 주유소로 변경 (O(N) 순회 한 번만 수행)
• 탐욕법(Greedy)으로 최적화하여 O(N)에 해결 가능

💡 이제 비슷한 문제를 만나면 "탐욕법(Greedy) 접근"을 우선 고려해 보세요! 🚀

[LeetCode] Product of Array Except Self - 나누기 없이 배열 곱셈 구하기

📌 문제 설명

LeetCode의 "Product of Array Except Self" 문제는 각 요소를 제외한 나머지 요소들의 곱을 구하는 문제입니다.

• 단, 나누기 연산(/)은 사용할 수 없음
• 시간 복잡도는 O(N) 이어야 함
• 추가 공간 O(1)만 사용 가능 (answer[] 외의 추가 배열은 금지)

📌 문제 해결 과정

✅ 잘못된 접근 (나누기 활용 방법)

처음에는 전체 곱을 구한 후, 각 요소를 나누는 방식이 떠오를 수 있습니다.

const totalProduct = nums.reduce((acc, val) => acc * val, 1);
return nums.map(num => totalProduct / num); // ❌ 나누기 연산 금지

하지만 문제에서 나누기 연산을 사용할 수 없으므로 적용 불가합니다.

📌 올바른 해결 방법 (Prefix & Suffix 곱 활용)

🚀 핵심 아이디어

1. 왼쪽 곱(prefix product) 저장 → answer[i]에 nums[i] 왼쪽 요소들의 곱을 저장
2. 오른쪽 곱(suffix product) 계산 & 최종 결과 반영 → answer[i]에 nums[i] 오른쪽 요소들의 곱을 곱함

이렇게 하면 O(N) 시간 복잡도로 나누기 없이 문제를 해결할 수 있습니다.

📌 최적화된 코드 (O(N) 시간, O(1) 공간)

export function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const answer = new Array(n).fill(1);

  // 1️⃣ 왼쪽 곱(prefix product) 저장
  let left = 1;
  for (let i = 0; i < n; i++) {
    answer[i] = left;
    left *= nums[i]; // 왼쪽 누적 곱 계산
  }

  // 2️⃣ 오른쪽 곱(suffix product) 계산 & 최종 결과 저장
  let right = 1;
  for (let i = n - 1; i >= 0; i--) {
    answer[i] *= right;
    right *= nums[i]; // 오른쪽 누적 곱 계산
  }

  // 3️⃣ -0 방지 처리
  return answer.map((val) => (Object.is(val, -0) ? 0 : val));
}

📌 예제 분석

입력: [1, 2, 3, 4]

1️⃣ 왼쪽 곱 계산

i nums[i] left answer[i] (왼쪽 곱)

✅ answer = [1, 1, 2, 6]

2️⃣ 오른쪽 곱 계산 & 최종 값 적용

i nums[i] right answer[i] (최종)

✅ 최종 answer = [24, 12, 8, 6]

📌 Jest 테스트 코드

describe("Medium 238: Product of Array Except Self", () => {
  it("calculates the product of array except self for positive numbers", () => {
    expect(productExceptSelf([1, 2, 3, 4])).toEqual([24, 12, 8, 6]);
  });

  it("handles arrays containing zero", () => {
    expect(productExceptSelf([-1, 1, 0, -3, 3])).toEqual([0, 0, 9, 0, 0]);
  });

  it("handles multiple zeros in the array", () => {
    expect(productExceptSelf([0, 0, 2, 3])).toEqual([0, 0, 0, 0]);
  });

  it("handles arrays with a single zero", () => {
    expect(productExceptSelf([4, 0, 5])).toEqual([0, 20, 0]);
  });

  it("handles all elements being zero", () => {
    expect(productExceptSelf([0, 0, 0])).toEqual([0, 0, 0]);
  });

  it("handles negative numbers correctly", () => {
    expect(productExceptSelf([-1, -2, -3, -4])).toEqual([-24, -12, -8, -6]);
  });

  it("handles a single element (edge case)", () => {
    expect(productExceptSelf([42])).toEqual([1]);
  });

  it("handles two elements", () => {
    expect(productExceptSelf([3, 5])).toEqual([5, 3]);
  });

  it("handles negative numbers with zero", () => {
    expect(productExceptSelf([-1, 0, -2, -3])).toEqual([0, -6, 0, 0]);
  });
});

✅ 다양한 입력 케이스 검증하여 정확성 확보
✅ 테스트 케이스 추가 (0 포함, 음수 포함, 작은 배열 예외 처리)

📌 시간 & 공간 복잡도

연산 복잡도 설명

✅ 추가 공간 O(1)을 유지하면서 나누기 없이 해결 가능! 🚀

📌 최종 정리

• 나누기 없이 해결해야 함 → 왼쪽 곱(prefix), 오른쪽 곱(suffix) 활용
• 배열을 2번 순회(O(N))하여 각각 왼쪽/오른쪽 곱을 계산
• 추가 공간 O(1) 유지 (출력 배열 제외하고 추가 배열을 사용하지 않음)

💡 이제 비슷한 문제를 만나면 "Prefix & Suffix 곱"을 우선 고려해 보세요! 🚀

[LeetCode] Insert Delete GetRandom O(1) - 효율적인 데이터 구조 구현 (Set vs. Array + Map)

문제 설명

LeetCode의 "Insert Delete GetRandom O(1)" 문제는 특정 연산을 O(1) 시간 내에 수행하는 데이터 구조를 구현하는 문제입니다.

• insert(val): 값이 없으면 추가하고 true 반환, 이미 존재하면 false 반환
• remove(val): 값이 있으면 제거하고 true 반환, 없으면 false 반환
• getRandom(): 저장된 값 중 무작위 요소를 O(1) 시간에 반환

📌 문제를 풀면서 생각한 과정

처음에는 Set을 사용하여 삽입과 삭제를 O(1)에 구현했지만, 무작위 요소 반환(getRandom())이 항상 첫 번째 요소만 선택되는 문제가 발생했습니다.
따라서, 배열(Array)과 해시맵(Map)을 활용하는 방식으로 최적화하였습니다.

📌 Set을 사용한 초기 구현 (문제점 존재)

🚨 문제점

export class RandomizedSet {
  elements: Set<number>;

  constructor() {
    this.elements = new Set<number>();
  }

  insert(val: number): boolean {
    if (this.elements.has(val)) {
      return false;
    }
    this.elements.add(val);
    return true;
  }

  remove(val: number): boolean {
    return this.elements.delete(val);
  }

  getRandom(): number {
    const val = this.elements.values().next().value;
    return val ? val : 0;
  }
}

🚨 문제점 분석

1. getRandom()이 무작위가 아님
   • this.elements.values().next().value는 항상 Set의 첫 번째 요소를 반환 → 랜덤이 아님!
   • 문제 요구사항: 무작위 요소를 선택해야 함 (O(1) 시간 복잡도 보장 필요)
2. 무작위 요소 접근 시 O(N)이 걸림
   • Set은 인덱스를 지원하지 않으므로 랜덤 요소를 찾으려면 Array.from(set)[randomIndex] 형태가 되어 O(N)이 발생

✅ 해결책: 배열(Array) + 해시맵(Map)을 활용하여 모든 연산을 O(1)로 구현

📌 배열(Array) + 해시맵(Map) 활용한 최적화된 해결법

✅ 핵심 아이디어

1. 배열(Array) 사용 → 무작위 접근(O(1))이 가능
2. 해시맵(Map) 사용 → 값을 인덱스로 저장하여 O(1) 삭제 가능
3. 삭제 시 배열 마지막 요소와 교환하여 O(1) 유지

📌 최적화된 코드 (O(1))

export class RandomizedSet {
  private list: number[];
  private map: Map<number, number>;

  constructor() {
    this.list = [];
    this.map = new Map<number, number>();
  }

  insert(val: number): boolean {
    if (this.map.has(val)) {
      return false;
    }

    this.list.push(val);
    this.map.set(val, this.list.length - 1);
    return true;
  }

  remove(val: number): boolean {
    if (!this.map.has(val)) {
      return false;
    }

    const index = this.map.get(val)!;
    const lastElement = this.list[this.list.length - 1];

    // 마지막 요소와 삭제할 요소 위치 변경 후 pop
    this.list[index] = lastElement;
    this.map.set(lastElement, index);

    this.list.pop();
    this.map.delete(val);

    return true;
  }

  getRandom(): number {
    const randomIndex = Math.floor(Math.random() * this.list.length);
    return this.list[randomIndex];
  }
}

📌 실행 예제 분석

const obj = new RandomizedSet();
console.log(obj.insert(3)); // true
console.log(obj.insert(1)); // true
console.log(obj.insert(7)); // true
console.log(obj.remove(1)); // true
console.log(obj.getRandom()); // 3 또는 7 (무작위)

✅ 배열을 활용하여 getRandom()이 무작위 동작을 수행하도록 수정 ✅ 삭제 시, O(1) 시간 복잡도를 유지하도록 최적화

📌 시간 및 공간 복잡도 비교

연산 원래 코드(Set 사용) 수정 코드 (배열 + 맵) 설명

✅ 이제 getRandom()도 O(1)로 무작위 요소를 선택할 수 있음! 🚀

📌 Jest 테스트 코드

describe("Insert Delete GetRandom O(1)", () => {
  it("performs insert, remove, and getRandom correctly", () => {
    const obj = new RandomizedSet();
    expect(obj.insert(3)).toBe(true);
    expect(obj.insert(1)).toBe(true);
    expect(obj.insert(7)).toBe(true);
    expect(obj.remove(1)).toBe(true);
    expect([3, 7]).toContain(obj.getRandom());
  });

  it("returns false when inserting duplicates", () => {
    const obj = new RandomizedSet();
    expect(obj.insert(3)).toBe(true);
    expect(obj.insert(3)).toBe(false);
  });

  it("returns false when removing non-existent values", () => {
    const obj = new RandomizedSet();
    expect(obj.remove(5)).toBe(false);
  });
});

✅ 다양한 입력 케이스 검증하여 정확성 확보
✅ 테스트 케이스 추가 (중복 삽입, 삭제 확인)

📌 최종 정리

• Set을 사용하면 O(1) 삽입/삭제는 가능하지만, getRandom()이 O(N)이 됨
• 배열과 맵을 조합하면 O(1) 보장이 가능
• 무작위 요소를 빠르게 선택할 수 있도록 getRandom() 최적화

💡 이제 비슷한 문제를 만나면 "배열 + 해시맵"을 우선 고려해 보세요! 🚀

[LeetCode] H-Index - 연구 논문의 영향력 측정 (탐욕법 + 정렬)

문제 설명

LeetCode의 "H-Index" 문제는 연구자가 발표한 논문들의 인용 횟수를 분석하여 H-Index를 계산하는 문제입니다.

• 연구자가 발표한 논문의 인용 횟수가 배열 citations로 주어집니다.
• 연구자의 H-Index는 h 편의 논문이 최소 h번 이상 인용되었으며, 나머지 논문은 h번 이하로 인용된 경우의 최대값입니다.
• 항상 H-Index를 계산할 수 있다고 가정합니다.

📌 문제를 풀면서 생각한 과정

처음에는 각 논문의 인용 횟수를 순차적으로 확인하며 H-Index를 계산하는 방법을 떠올렸습니다.
하지만 효율적인 탐색이 필요하여 탐욕법(Greedy Algorithm)과 정렬을 활용한 최적화 방법을 도출했습니다.

📌 H-Index 계산 방법

✅ 핵심 아이디어

1. 논문을 인용 횟수 기준으로 내림차순 정렬합니다.
2. 각 논문이 i+1번째로 많이 인용된 논문인지 확인합니다.
   • citations[i] >= i + 1 → H-Index 가능
   • 더 이상 만족하지 않으면 마지막으로 i가 유효한 값이 됨

📌 탐욕법(Greedy) 코드

export function hIndex(citations: number[]): number {
  citations.sort((a, b) => b - a); // 내림차순 정렬

  let h = 0;
  for (let i = 0; i < citations.length; i++) {
    if (citations[i] >= i + 1) {
      h = i + 1;
    } else {
      break;
    }
  }

  return h;
}

📌 실행 예제 분석

console.log(hIndex([3, 0, 6, 1, 5])); // Output: 3
console.log(hIndex([1, 3, 1]));       // Output: 1
console.log(hIndex([10, 8, 5, 4, 3])); // Output: 4
console.log(hIndex([0, 0, 0, 0]));     // Output: 0
console.log(hIndex([100]));            // Output: 1

✅ 논문을 내림차순으로 정렬하여 탐색을 최적화 ✅ 각 논문이 i+1번째 이상 인용되었는지 확인 ✅ H-Index가 더 이상 증가하지 않으면 중단

📌 시간 및 공간 복잡도 비교

방법 시간 복잡도 공간 복잡도 특징

✅ 탐욕법(Greedy)과 정렬을 활용하여 최적의 해결법을 적용 🚀

📌 Jest 테스트 코드

describe("Medium 274: H-Index", () => {
  it("returns the correct H-Index for a standard case", () => {
    expect(hIndex([3, 0, 6, 1, 5])).toEqual(3);
  });

  it("returns the correct H-Index when values are small", () => {
    expect(hIndex([1, 3, 1])).toEqual(1);
  });

  it("returns the correct H-Index when all values are high", () => {
    expect(hIndex([10, 8, 5, 4, 3])).toEqual(4);
  });

  it("returns 0 when all citations are 0", () => {
    expect(hIndex([0, 0, 0, 0])).toEqual(0);
  });

  it("returns 1 when there is only one highly cited paper", () => {
    expect(hIndex([100])).toEqual(1);
  });
});

✅ 다양한 입력 케이스 검증하여 정확성 확보
✅ 테스트 케이스 추가 (단일 요소, 정렬된 점프, 초기 정지 상황)

📌 최종 정리

• 탐욕법(Greedy)과 정렬을 활용하여 O(N log N) 최적화 적용
• "현재 논문의 인용 횟수가 i+1개 이상인지"를 확인하여 H-Index를 계산
• 추가 배열 없이 O(1) 공간복잡도로 해결 가능

💡 이제 비슷한 문제를 만나면 "탐욕법 + 정렬"을 우선 고려해 보세요! 🚀

[LeetCode] Jump Game II - 최소 점프 횟수 찾기 (탐욕법 + DP)

문제 설명

LeetCode의 "Jump Game II" 문제는 배열의 시작점에서 끝점까지 최소한의 점프로 도달하는 문제입니다.

• nums[i]는 i번째 인덱스에서 최대 몇 칸까지 점프할 수 있는지를 나타냅니다.
• nums[0]에서 nums[n-1]까지 도달하는 최소 점프 횟수를 구해야 합니다.
• 항상 도달 가능하다고 가정됩니다.

📌 문제를 풀면서 생각한 과정

처음에는 "모든 경우를 탐색하면서 최소 점프 횟수를 찾는 방법이 있을까?" 라고 고민했습니다.
먼저 동적 계획법(DP) 방식으로 접근했지만 O(N^2)의 시간 복잡도로 인해 비효율적이었습니다.
이후 **탐욕법(Greedy Algorithm)**을 적용하면 O(N)으로 해결할 수 있음을 발견했습니다.

📌 DP (동적 계획법) 풀이 - 초기 접근 방법

✅ 핵심 아이디어

1. 각 인덱스까지 최소 점프 횟수를 저장하는 dp 배열을 사용
2. dp[i]는 인덱스 i에 도달하는 최소 점프 횟수를 의미
3. dp[i] = min(dp[i], dp[j] + 1)
   • j에서 i로 이동할 수 있는 경우 (j + nums[j] >= i)
   • dp[i]는 dp[j] + 1 (즉, j에서 한 번 점프해서 가는 방법이 기존보다 더 작다면 업데이트)

📌 DP 코드

export function jumpDP(nums: number[]): number {
  const dp = new Array(nums.length).fill(Infinity);
  dp[0] = 0; // 시작점은 점프 0번

  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j <= i + nums[i] && j < nums.length; j++) {
      dp[j] = Math.min(dp[j], dp[i] + 1);
    }
  }

  return dp[nums.length - 1]; // 마지막 인덱스까지의 최소 점프 횟수 반환
}

📌 실행 예제 분석

nums = [2,3,1,1,4]

초기 dp 배열:

[0, ∞, ∞, ∞, ∞]

i nums[i] dp 배열 변경

✅ 최소 점프 횟수: dp[4] = 2

📌 DP의 문제점

• 시간 복잡도: O(N^2) (이중 반복문)
• 공간 복잡도: O(N) (dp 배열 사용)
• 비효율적이며, 최적화 필요

📌 탐욕법(Greedy) 풀이 - 최적해 도출 과정

✅ 핵심 아이디어

1. 최대한 멀리 갈 수 있는 곳(farthest)을 계속 갱신한다.
2. 현재 점프 내에서 최대 도달 가능 위치(currentEnd)를 확인한다.
3. 현재 위치가 currentEnd를 넘어서면 점프 횟수를 증가시키고 새로운 currentEnd를 설정한다.
4. 이 과정을 반복하면 최소 점프 횟수로 마지막 위치에 도달할 수 있다.

📌 탐욕법(Greedy) 코드

export function jump(nums: number[]): number {
  let jumps = 0;
  let currentEnd = 0;
  let farthest = 0;

  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);
    if (i === currentEnd) {
      jumps++;
      currentEnd = farthest;
    }
  }

  return jumps;
}

📌 실행 예제 분석

nums = [2,3,1,1,4]

i nums[i] farthest currentEnd jumps 설명

✅ 최소 점프 횟수: 2

📌 탐욕법 vs DP 비교

방법 시간 복잡도 공간 복잡도 특징

✅ 탐욕법(Greedy)이 최적의 해결법! 🚀

📌 최종 정리

• DP는 직관적이지만, O(N^2) 복잡도로 비효율적
• 탐욕법(Greedy)은 O(N)으로 최적화 가능
• "현재 점프 내에서 가장 멀리 갈 수 있는 곳"을 선택하는 것이 최적의 해
• 추가 배열 없이 O(1) 공간복잡도로 해결 가능

💡 이제 비슷한 문제를 만나면 "탐욕법"을 우선 고려해 보세요! 🚀

[LeetCode] Jump Game - 탐욕법(Greedy) 풀이 및 최적화

문제 설명

LeetCode의 "Jump Game" 문제는 배열의 시작점에서 끝점까지 도달할 수 있는지 확인하는 문제입니다.

• nums[i]는 i번째 인덱스에서 최대 몇 칸까지 점프할 수 있는지를 나타냅니다.
• nums[0]에서 nums[n-1]까지 도달할 수 있으면 true, 불가능하면 false를 반환해야 합니다.

📌 처음 문제를 풀었을 때의 접근 방식

처음에는 배열을 사용하여 방문 가능 여부를 체크하는 방식으로 접근했습니다.

export function canJump(nums: number[]): boolean {
  const list = new Array(nums.length).fill(false); // 방문 가능 여부 배열
  list[0] = true; // 첫 번째 위치에서 시작 가능

  for (let i = 0; i < nums.length; i++) {
    if (!list[i]) continue; // 현재 위치(i)가 도달 가능하지 않다면 스킵
    let index = i;
    while (index < nums.length && index <= i + nums[i]) {
      list[index++] = true; // 현재 위치에서 갈 수 있는 범위까지 도달 가능 표시
    }
  }

  return list[nums.length - 1]; // 마지막 인덱스 도달 가능 여부 반환
}

✅ 동작은 하지만, 비효율적! (O(N^2) 시간복잡도로 최적화 필요)
✅ 공간 복잡도도 O(N), 추가 배열 사용으로 메모리 낭비

📌 최적화된 접근법: 탐욕법(Greedy Algorithm)

이 문제는 **탐욕법(Greedy Algorithm)**을 사용하면 효율적으로 O(N) 시간복잡도로 해결 가능합니다.

✅ 탐욕법(Greedy) 핵심 아이디어

• **"최대로 도달할 수 있는 위치(maxReach)"**를 계속 갱신하면서, n-1번째 인덱스까지 도달할 수 있는지 확인합니다.
• 현재 인덱스(i)가 maxReach보다 크면 → 더 이상 진행할 수 없으므로 false 반환.

export function canJump(nums: number[]): boolean {
  let maxReach = 0; // 최대로 도달할 수 있는 위치

  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) return false; // 현재 위치(i)가 maxReach보다 크면 도달 불가능
    maxReach = Math.max(maxReach, i + nums[i]); // 최대 이동 가능한 위치 갱신
    if (maxReach >= nums.length - 1) return true; // 마지막 인덱스에 도달 가능하면 바로 true 반환
  }

  return false;
}

✅ 시간복잡도: O(N), 배열을 한 번만 순회
✅ 공간복잡도: O(1), 추가 배열 없이 해결 가능

📌 실행 예제 분석

nums = [2,3,1,1,4]

i nums[i] maxReach 설명

✅ 결과: true

📌 시간 및 공간 복잡도 비교

방법 시간 복잡도 공간 복잡도 특징

✅ 탐욕법(Greedy)이 최적의 해결법!

📌 Jest 테스트 코드

describe("Jump Game", () => {
  it("returns true for reachable last index", () => {
    expect(canJump([2,3,1,1,4])).toEqual(true);
  });

  it("returns false for unreachable last index", () => {
    expect(canJump([3,2,1,0,4])).toEqual(false);
  });

  it("returns true for single element array", () => {
    expect(canJump([0])).toEqual(true);
  });

  it("returns true when all elements are large", () => {
    expect(canJump([10,10,10,10,10])).toEqual(true);
  });

  it("returns false for early stopping case", () => {
    expect(canJump([1,0,0,0])).toEqual(false);
  });
});

✅ 다양한 입력 케이스 검증하여 정확성 확보
✅ 테스트 케이스 추가 (단일 요소, 큰 값, 초기 정지 상황)

📌 최종 정리

• 탐욕법(Greedy)이 최적의 해결법 (O(N))
• "최대 도달 가능 위치(maxReach)"를 계속 갱신하면서 도달 여부 판단
• 추가 배열을 사용하지 않고 O(1) 공간복잡도로 해결 가능
• 테스트 케이스를 추가하여 다양한 상황에서 올바른 결과 확인 가능

💡 이제 비슷한 문제를 만나면 "탐욕법"을 우선 고려해 보세요! 🚀

[LeetCode] Best Time to Buy and Sell Stock II - Greedy & DP 풀이

문제 설명

LeetCode의 "Best Time to Buy and Sell Stock II" 문제는 여러 번 매매하여 최대 이익을 얻는 문제입니다.

• prices[i]는 i번째 날의 주가를 나타냅니다.
• 여러 번 매매 가능하지만, 보유 중에는 추가 매수가 불가능합니다. (즉, 한 번 매수하면 반드시 매도 후 다시 매수 가능)
• 최대 이익을 구하는 것이 목표입니다.

처음 문제를 풀었을 때의 생각

처음에는 **"최적의 매수-매도 시점을 찾는 문제"**라고 생각했어요.
하지만, **"가격이 오를 때마다 매수-매도를 반복하면 최대 이익을 얻을 수 있다"**는 점을 깨달았습니다.
이 접근법은 탐욕법(Greedy Algorithm)으로 해결 가능하며, O(N) 시간 복잡도로 최적의 결과를 얻을 수 있습니다.

또한, 동적 계획법(DP)으로도 해결 가능하지만, 탐욕법이 훨씬 직관적이고 효과적인 방식이었습니다.

탐욕법(Greedy) 풀이

✅ 핵심 아이디어

• 가격이 오를 때마다 이익을 취하는 것이 최적의 전략입니다.
• 즉, 모든 상승 구간에서 매수-매도를 반복하면 최대 이익을 얻을 수 있음.

export function maxProfit2(prices: number[]): number {
  let sum = 0;
  for (let index = 1; index < prices.length; index++) {
    if (prices[index] > prices[index - 1]) {
      sum += prices[index] - prices[index - 1];
    }
  }
  return sum;
}

📌 실행 예제 분석

prices = [7,1,5,3,6,4]

날짜 주가 수익 계산 누적 이익

✅ 최종 이익: 7

📌 시간 및 공간 복잡도

• 시간 복잡도: O(N) → 배열을 한 번 순회
• 공간 복잡도: O(1) → 추가적인 공간 사용 없음

동적 계획법(DP) 풀이

✅ DP 접근법의 핵심 개념

이 문제에서 우리는 매일 두 가지 선택을 할 수 있습니다.

1. 주식을 보유한 상태 (hold)
   • hold[i] = i번째 날까지의 최대 이익 (주식을 보유한 상태)
   • hold[i] = max(hold[i-1], sell[i-1] - prices[i])
2. 주식을 보유하지 않은 상태 (sell)
   • sell[i] = i번째 날까지의 최대 이익 (주식을 보유하지 않은 상태)
   • sell[i] = max(sell[i-1], hold[i-1] + prices[i])

✅ 결국, sell[n-1] (마지막 날 주식을 보유하지 않은 상태의 최대 이익)이 정답입니다.

export function maxProfitDP(prices: number[]): number {
  if (prices.length === 0) return 0;

  let sell = 0; // 주식을 보유하지 않은 상태의 최대 이익
  let hold = -prices[0]; // 주식을 보유한 상태의 최대 이익 (초기값: 첫날 주식을 샀을 때)

  for (let i = 1; i < prices.length; i++) {
    sell = Math.max(sell, hold + prices[i]); // 현재 주식을 팔거나, 팔지 않는 경우 중 최댓값
    hold = Math.max(hold, sell - prices[i]); // 현재 주식을 사거나, 기존 주식을 유지하는 경우 중 최댓값
  }

  return sell;
}

📌 시간 및 공간 복잡도

• 시간 복잡도: O(N)
• 공간 복잡도: O(1)

탐욕법(Greedy) vs. 동적 계획법(DP) 비교

방법 시간 복잡도 공간 복잡도 특징

✅ 이 문제는 탐욕법(Greedy)이 최적의 해결법이며, DP보다 직관적이고 효율적입니다.

Jest 테스트 코드

describe("Best Time to Buy and Sell Stock II", () => {
  it("calculates max profit for increasing prices", () => {
    expect(maxProfit2([1,2,3,4,5])).toEqual(4);
  });

  it("calculates max profit for fluctuating prices", () => {
    expect(maxProfit2([7,1,5,3,6,4])).toEqual(7);
  });

  it("returns 0 for decreasing prices", () => {
    expect(maxProfit2([7,6,5,4,3,2,1])).toEqual(0);
  });
});

✅ 다양한 입력 케이스를 검증하여 정확성 확보 ✅ 가격이 오르지 않는 경우([7,6,5,4,3,2,1])도 테스트하여 0 반환 확인

📌 최종 정리

• 탐욕법(Greedy)이 가장 적절한 해결법 (O(N))
• DP도 사용 가능하지만, 탐욕법이 훨씬 직관적이고 효율적
• 테스트 케이스를 추가하여 다양한 상황에서 올바른 결과 확인 가능

💡 이제 비슷한 문제를 만나면 "탐욕법"을 우선 고려해 보세요! 🚀

[LeetCode] Majority Element - 보이어-무어 투표 알고리즘 (Boyer-Moore Voting Algorithm) 풀이

문제 설명

LeetCode의 "Majority Element" 문제는 배열에서 과반수 요소(majority element)를 찾는 문제입니다.

과반수 요소는 배열 길이 n의 절반(⌊n / 2⌋)을 초과하여 등장하는 요소입니다. 문제에서 항상 과반수 요소가 존재한다고 보장되므로, 이를 활용하여 최적화된 방법을 사용할 수 있습니다.

처음 문제를 풀었을 때의 생각

처음에는 각 숫자의 등장 횟수를 카운트해서 가장 많이 등장하는 숫자를 찾으면 되겠다고 생각했어요. 하지만 직접 구현해 보니 추가적인 메모리를 사용해야 했고, 더 최적화할 방법이 필요했습니다.

이 문제에서는 추가 메모리 없이 O(N) 시간 복잡도로 해결 가능한 보이어-무어 투표 알고리즘(Boyer-Moore Voting Algorithm)을 활용할 수 있습니다.

비효율적인 접근 방식 (카운팅을 활용한 풀이)

export function majorityElement(nums: number[]): number {
  const counts: Record<number, number> = {};

  for (const n of nums) {
    counts[n] = (counts[n] || 0) + 1;
  }

  return Object.keys(counts)
    .map(Number)
    .reduce((a, b) => (counts[a] > counts[b] ? a : b));
}

✅ 시간 복잡도 O(N)
❌ 공간 복잡도 O(N) (추가 해시맵 사용)

이 방법도 작동하지만, 공간 복잡도를 최적화할 방법이 필요합니다.

보이어-무어 투표 알고리즘 (Boyer-Moore Voting Algorithm)

이 문제는 과반수 요소가 항상 존재한다는 점을 활용하면, 투표 개념을 적용해서 공간 복잡도를 O(1)로 최적화할 수 있습니다.

✅ 보이어-무어 알고리즘 실행 과정

export function majorityElement(nums: number[]): number {
  let candidate = 0;
  let count = 0;

  for (const num of nums) {
    if (count === 0) {
      candidate = num;  // 새로운 후보 설정
    }
    count += num === candidate ? 1 : -1;  // 같으면 증가, 다르면 감소
  }

  return candidate;
}

✅ 시간 복잡도 O(N)
✅ 공간 복잡도 O(1)
✅ 배열을 한 번만 순회하며 해결 가능

보이어-무어 알고리즘 원리 (쉽게 이해하기)

배열을 투표하는 사람들로 생각해 보자.

• 각 숫자는 후보(candidate) 가 될 수 있음.
• 같은 숫자는 찬성표(++) 를 던지고, 다른 숫자는 반대표(--) 를 던짐.
• 과반수 요소는 항상 절반 이상 존재하므로, 최종적으로 살아남는 후보는 무조건 과반수 요소가 됨.

예제 실행 과정

nums = [2,2,1,1,1,2,2]

단계 현재 숫자 후보(candidate) 개수(count) 설명

✅ 최종 후보: 2 (과반수 요소)

Jest 테스트 코드

describe("Majority Element - Boyer-Moore Voting Algorithm", () => {
  it("returns the majority element from an odd-length array", () => {
    const nums = [3, 2, 3];
    expect(majorityElement(nums)).toEqual(3);
  });

  it("returns the majority element from an even-length array", () => {
    const nums = [2,2,1,1,1,2,2];
    expect(majorityElement(nums)).toEqual(2);
  });

  it("handles an array where all elements are the same", () => {
    const nums = [5, 5, 5, 5, 5, 5, 5];
    expect(majorityElement(nums)).toEqual(5);
  });
});

✅ it 설명을 명확하게 추가하여 테스트의 목적을 알기 쉽게 정리
✅ 다양한 테스트 케이스 추가

결론

처음에는 배열을 순회하며 카운팅하는 방식을 생각했지만, 공간 복잡도를 최적화할 필요가 있었습니다.

보이어-무어 투표 알고리즘은 과반수 요소가 항상 존재한다는 점을 이용하여 최적화할 수 있었습니다. 🎯

이제 과반수 요소를 찾는 문제를 만나면 보이어-무어 알고리즘을 활용해 보세요! 🚀