// JavaScript 구현
function insertionSort(arr) {
  const n = arr.length;
  console.log("초기 배열:", arr);
  
  // 두 번째 요소(인덱스 1)부터 탐색 시작
  for (let i = 1; i < n; i++) {
    let key = arr[i];
    let j = i - 1;
    
    // key보다 큰 값들은 한 칸씩 오른쪽으로 이동(Shift)
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    
    // 알맞은 위치에 key 삽입
    arr[j + 1] = key;
  }
  
  return arr;
}

const arr = [5, 3, 1, 4, 2];
console.log("정렬 결과:", insertionSort(arr));

// JavaScript 구현
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    // 소수점 버림 방지 및 오버플로우 방지 공식 적용 권장
    let mid = left + Math.floor((right - left) / 2);
    console.log(`탐색 범위: index ${left} ~ ${right}, 중간값: ${arr[mid]}`);
    
    if (arr[mid] === target) {
      return mid; // 타겟을 찾음
    } else if (arr[mid] < target) {
      left = mid + 1; // 타겟이 오른쪽에 있음 -> 왼쪽 범위 버림
    } else {
      right = mid - 1; // 타겟이 왼쪽에 있음 -> 오른쪽 범위 버림
    }
  }
  
  return -1; // 타겟이 배열에 없음
}

const sortedArr = [1, 3, 5, 7, 9, 11, 13, 15];
const target = 11;
console.log("배열:", sortedArr);
console.log(`타겟 ${target}의 인덱스:`, binarySearch(sortedArr, target));

// JavaScript 구현 (Swapped 최적화 적용)
function bubbleSort(arr) {
  const n = arr.length;
  console.log("초기 배열:", arr);
  
  for (let i = 0; i < n - 1; i++) {
    let swapped = false; // 이번 턴에 Swap이 일어났는지 추적
    
    // 매 패스마다 가장 큰 값이 뒤로 확정되므로 끝에서 i만큼 빼줌
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // 배열 구조 분해 할당을 이용한 Swap
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    
    // 한 바퀴 돌았는데 단 한 번도 안 바뀌었다면? 이미 정렬 완료!
    if (!swapped) break;
  }
  
  return arr;
}

const arr = [5, 3, 1, 4, 2];
console.log("정렬 결과:", bubbleSort(arr));

// JavaScript 구현
function selectionSort(arr) {
  const n = arr.length;
  console.log("초기 배열:", arr);
  
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    
    // 현재 인덱스 이후부터 최소값의 인덱스를 찾음
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }
    
    // 최소값이 자기 자신이 아니라면 스왑(Swap)
    if (minIdx !== i) {
      let temp = arr[i];
      arr[i] = arr[minIdx];
      arr[minIdx] = temp;
    }
  }
  
  return arr;
}

const arr = [5, 3, 1, 4, 2];
console.log("정렬 결과:", selectionSort(arr));

// JavaScript 구현
function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    
    return merge(left, right);
}

function merge(left, right) {
    let result = [];
    let i = 0, j = 0;
    
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }
    
    return result.concat(left.slice(i)).concat(right.slice(j));
}

const arr = [38, 27, 43, 3, 9, 82, 10];
console.log("초기 배열:", arr);
console.log("정렬 결과:", mergeSort(arr));

// JavaScript 구현
function quickSort(arr, left = 0, right = arr.length - 1) {
    if (left >= right) return;

    // 파티셔닝 수행 후 피벗의 최종 위치를 받음
    const pivotIndex = partition(arr, left, right);

    // 피벗을 기준으로 좌/우 재귀 정렬
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
    
    return arr;
}

function partition(arr, left, right) {
    const pivot = arr[right]; // 가장 오른쪽 요소를 피벗으로 선택
    let i = left - 1;

    for (let j = left; j < right; j++) {
        if (arr[j] < pivot) {
            i++;
            // arr[i]와 arr[j] 교환
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    
    // 마지막으로 피벗을 제자리에 둠
    [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
    return i + 1;
}

const arr = [5, 3, 8, 4, 9, 1, 6];
console.log("초기 배열:", arr);
quickSort(arr);
console.log("정렬 결과:", arr);

// JavaScript 구현
const graph = {
  1: [2, 3],
  2: [4, 5],
  3: [6, 7],
  4: [],
  5: [],
  6: [],
  7: []
};

function dfs(graph, startNode) {
  const visited = new Set();
  const result = [];
  
  function explore(node) {
    if (visited.has(node)) return;
    
    // 방문 처리
    visited.add(node);
    result.push(node);
    
    // 인접 노드 깊이 우선 탐색 (재귀)
    for (const neighbor of graph[node]) {
      explore(neighbor);
    }
  }
  
  explore(startNode);
  return result;
}

console.log("DFS 탐색 결과:", dfs(graph, 1).join(" -> "));
// 출력 결과: 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7

// JavaScript 구현
const graph = {
  1: [2, 3],
  2: [4, 5],
  3: [6, 7],
  4: [],
  5: [],
  6: [],
  7: []
};

function bfs(graph, startNode) {
  const visited = new Set([startNode]);
  const queue = [startNode];
  const result = [];
  
  // shift()의 O(N) 방지를 위한 투 포인터 방식 권장
  let head = 0; 
  
  while (head < queue.length) {
    const node = queue[head++]; // O(1) 추출
    result.push(node);
    
    // 인접 노드들을 레벨 단위로 모두 큐에 삽입
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  
  return result;
}

console.log("BFS 탐색 결과:", bfs(graph, 1).join(" -> "));
// 출력 결과: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

// JavaScript 구현 (Top-Down: Memoization)
// 실무에서는 전역 객체보다 클로저나 클래스 인스턴스 멤버를 사용하는 것이 안전합니다.
function getFibonacciWithMemo() {
  const memo = {}; // 계산 결과를 저장할 캐시 객체
  
  return function fibo(n) {
    if (n <= 1) return n;
    
    // 1. 캐시 히트(Cache Hit) 확인
    if (memo[n] !== undefined) {
      console.log(`F(${n}) 캐시 히트!`);
      return memo[n];
    }
    
    // 2. 미연산 값이라면 점화식을 통해 계산 후 캐시에 저장
    console.log(`F(${n}) 계산 중...`);
    memo[n] = fibo(n - 1) + fibo(n - 2);
    
    return memo[n];
  };
}

const dpFibo = getFibonacciWithMemo();
console.log("F(5) 결과:", dpFibo(5));

// JavaScript 구현 (가장 단순한 O(V^2) 방식 - 코딩테스트용)
const graph = {
  'A': { 'B': 2, 'C': 5 },
  'B': { 'C': 1, 'D': 3 },
  'C': { 'D': 6 },
  'D': {}
};

function dijkstra(graph, start) {
  const distances = {};
  const visited = new Set();
  
  // 초기화
  for (let node in graph) {
    distances[node] = Infinity;
  }
  distances[start] = 0;
  
  while (true) {
    let currNode = null;
    let shortestDist = Infinity;
    
    // 방문하지 않은 노드 중 가장 거리가 짧은 노드 탐색 (내장 PQ가 없어서 선형 탐색)
    for (let node in distances) {
      if (!visited.has(node) && distances[node] < shortestDist) {
        shortestDist = distances[node];
        currNode = node;
      }
    }
    
    if (currNode === null) break;
    visited.add(currNode);
    
    // 인접 노드 거리 갱신 (Relaxation)
    for (let neighbor in graph[currNode]) {
      let cost = distances[currNode] + graph[currNode][neighbor];
      if (cost < distances[neighbor]) {
        distances[neighbor] = cost; // 최단 거리 갱신
      }
    }
  }
  
  return distances;
}

console.log("시작점 A 기준 최단 거리:", dijkstra(graph, 'A'));
// 출력: { A: 0, B: 2, C: 3, D: 5 }