수달씨의 개발공간

[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] 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] 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) 공간복잡도로 해결 가능
• 테스트 케이스를 추가하여 다양한 상황에서 올바른 결과 확인 가능

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