구현

구현이란

머리속 알고리즘을 코드로 구현하는 것을 의미합니다. 넓은 의미로 모든 코딩테스트 문제를 구현이라고 할 수도 있습니다.

구현은 피지컬 싸움이라고도 하는데, 이때의 피지컬은 사용하는 1. 언어의 문법에 얼마나 능숙하느냐, 2. 코드 작성 속도가 얼마나 빠르냐에 따라 갈린다고 합니다..

대표적인 구현은 두가지가 있습니다.
1. 완전탐색 : 가능한 모든 경우를 계산
2. 시물레이션 : 주어진 알고리즘을 한 단계식 계산

---

완전 탐색 예시

주어진 숫자 배열에서 합이 특정한 값(target)이 되는 모든 가능한 숫자 쌍을 찾는 문제

완전 탐색 알고리즘은 가능한 모든 경우의 수를 탐색하므로, 시간 복잡도는 일반적으로 O(N^2)입니다.

function findPairs(nums, target) {
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        result.push([nums[i], nums[j]]);
      }
    }
  }

  return result;
}

const numbers = [2, 4, 5, 7, 9];
const targetSum = 9;

const pairs = findPairs(numbers, targetSum);
console.log(pairs);

---

시물레이션 예시

주어진 문자열에 따라 로봇의 이동을 시뮬레이션하고, 최종 위치를 반환하는 문제입니다.

문자열의 길이에 비례하여 시뮬레이션을 진행하므로, 시간 복잡도는 O(N)

function simulateRobotMovement(steps) {
  let position = [0, 0]; // 초기 위치 (x, y)
  const directions = {
    L: [-1, 0], // 왼쪽으로 이동 (x -= 1)
    R: [1, 0],  // 오른쪽으로 이동 (x += 1)
    U: [0, 1],  // 위로 이동 (y += 1)
    D: [0, -1]  // 아래로 이동 (y -= 1)
  };

  for (const step of steps) {
    const [dx, dy] = directions[step];
    position[0] += dx;
    position[1] += dy;
  }

  return position;
}

const moves = "LLUURRDD";
const finalPosition = simulateRobotMovement(moves);
console.log(finalPosition);

---