[알고리즘 노트]

2차원 리스트 90도 회전

• python 코드

def rotate_a_matrix_by_90_degree(a):
    n = len(a) # 행 길이 계산
    m = len(a[0]) # 열 길이 계산
    result = [[0]*n for _ in range(m)] # 결과 리스트
    for i in range(n):
        for j in range(m):
            result[j][n -i -1] = a[i][j]
    return result

• javascript 코드

function rotate(a){
    let n = a.length; // 행 길이 계산
    let m = a[0].length; // 열 길이 계산
    let result = Array.from(Array(n), () => new Array(m)); // 결과 리스트
    for(let i=0; i<n; i++){
        for(let j=0; j<m; j++){
            result[j][n -i -1] = a[i][j];
        }
    }
    return result;
}

조합

• javascript 코드 1 - 배열

const getCombinations = function (arr, length) {
  const result = [];
  
  // 1개씩 택할 때, 배열의 모든 원소 리턴
  if (length === 1) return arr.map((value) => [value]);
  
  arr.forEach((fixed, idx, origin) => {
	if (arr.length - idx < length) return;
    // fixed를 제외한 나머지
    const rest = origin.slice(idx + 1);
    // 나머지에 대해서 조합을 구함
    const combinations = getCombinations(rest, length - 1);
    // fixed 에 구해진 조합을 더함
    const attached = combinations.map((combination) => [fixed, ...combination]);

    result.push(...attached);
  });

  return result;
}

const exampleArr = [1,2,3,4];
getCombinations(exampleArr, 3);
// => [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ]

• javascript 코드 2 - DFS

function getCombinations(arr, length) {
  let result = [];
  let temp = Array.from({length:length},()=>0);

  function DFS(n, s) {
    if (n === length) {
      result.push(temp.slice());
    } else {
      for (let i = s; i < arr.length; i++) {
        temp[n] = arr[i];
        DFS(n+1, i+1);
      }
    }
  }
  DFS(0, 0);
  console.log(result);
}

getCombinations([1,2,3,4],3);
// => [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ]

---

중복 조합

function getCombinationsRe(arr, length) {
    const result = [];
    if (length === 1) return arr.map((value) => [value]);
    arr.forEach((fixed, idx, origin) => {
        const rest = origin.slice(idx);
        const combinations = getCombinationsRe(rest, length - 1);
        const attached = combinations.map((combination) => [fixed, ...combination]);
        result.push(...attached);
    });
    return result;
}

getCombinationsRe([1,2,3,4],3);
// => [ [ 1, 1, 1 ], [ 1, 1, 2 ], [ 1, 1, 3 ], [ 1, 1, 4 ],
// [ 1, 2, 2 ], [ 1, 2, 3 ], [ 1, 2, 4 ], 
// [ 1, 3, 3 ], [ 1, 3, 4 ], [ 1, 4, 4 ], 
// [ 2, 2, 2 ], [ 2, 2, 3 ], [ 2, 2, 4 ],
// [ 2, 3, 3 ], [ 2, 3, 4 ], [ 2, 4, 4 ],
// [ 3, 3, 3 ], [ 3, 3, 4 ], [ 3, 4, 4 ],[ 4, 4, 4 ] ]

---

순열

• javascript 코드

const getPermutations= function (arr, length) {
  const result = [];

  // 1개씩 택할 때, 배열의 모든 원소 리턴
  if (length === 1) return arr.map((value) => [value]);

  arr.forEach((fixed, idx, origin) => {
    // fixed 를 제외한 나머지
    const rest = [...origin.slice(0, idx), ...origin.slice(idx+1)]
    // 나머지에 대해서 순열을 구함
    const permutations = getPermutations(rest, length - 1);
    // fixed 에 구해진 순열을 더함
    const attached = permutations.map((permutation) => [fixed, ...permutation]);
    result.push(...attached);
  });

  return result;
};

getPermutations([1,2,3], 2);
// => [ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ] ]

---

중복 순열

• javascript 코드 - DFS

function getPermutationsRep(arr, length) {
  let result = [];
  let temp = [];
  function DFS(n) {
    if (n === length) {
      result.push([...temp]);
    } else {
      for (let i = 0; i < arr.length; i++) {
        temp[n] = arr[i];
        DFS(n + 1);
      }
    }
}
  DFS(0);
  return result;
}

getPermutationsRep([1,2,3],2);
// => [ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ],
//   [ 2, 1 ], [ 2, 2 ], [ 2, 3 ],
//   [ 3, 1 ], [ 3, 2 ], [ 3, 3 ] ]

---

BFS(Breadth First Search)

• javascript 코드

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "G", "H", "I"],
  D: ["B", "E", "F"],
  E: ["D"],
  F: ["D"],
  G: ["C"],
  H: ["C"],
  I: ["C", "J"],
  J: ["I"]
};

const bfs = (graph, startNode) => {
  let visited = []; // 탐색을 마친 노드들
  let needVisit = []; // 탐색해야할 노드들

  needVisit.push(startNode); // 노드 탐색 시작

  while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
    const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
    if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
      visited.push(node); 
      needVisit = [...needVisit, ...graph[node]];
    }
  }
  return visited;
};

bfs(graph, "A");
// => ["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]

---

DFS(Depth First Search)

• javascript 코드

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "G", "H", "I"],
  D: ["B", "E", "F"],
  E: ["D"],
  F: ["D"],
  G: ["C"],
  H: ["C"],
  I: ["C", "J"],
  J: ["I"],
};

// (graph, 시작 정점)
const dfs = (graph, startNode) => {
  let needVisitStack = []; // 탐색을 해야 할 노드들
  let visitedQueue = []; // 탐색을 마친 노드들

  needVisitStack.push(startNode);

  // 탐색을 해야 할 노드가 남아 있다면
  while (needVisitStack.length !== 0) {
    const node = needVisitStack.pop();
    if (!visitedQueue.includes(node)) {
      visitedQueue.push(node);
      needVisitStack = [...needVisitStack, ...graph[node]];
    }
  }

  return visitedQueue;
};

dfs(graph, "A");
// => ["A", "C", "I", "J", "H", "G", "B", "D", "F", "E"]

---

유클리드 호제법(최대공약수, 최소공배수)

• javascript 코드

function getGcd(a, b) {
    // a와 b의 나머지를 구한다.
    const mod = a % b;
    // 만약 나머지가 0일 경우 b를 반환한다.
    if (mod === 0) {
        return b;
    }
    // 만약 0이 아닐경우 a에 b를 넣고 b에 나머지인 mod를 넣어 해당 함수를 다시 호출해준다.
    return getGcd(b, mod);
}

function getLcm(a, b) {
    const gcd = getGcd(a, b);
    // 최소공배수 = ( 두 수의 곱 / 최대공약수 )
    const lcm = (a * b) / gcd;
    return lcm;
}

소수 판별

function isPrime(num){
    if(num === 1) return false;
    if(num === 2) return true;
    for(let i=2; i<=Math.floor(Math.sqrt(num)); i++){
        if(num % i === 0){
            return false; 
        }
    }
    return true; 
}

• 에라토스테네스의 체) 소수 개수 구하기

function countPrime(num){
    let arr = Array(num+1).fill(true).fill(false, 0, 2);
    for(let i=2; i*i <= num; i++){
        if(arr[i]){
            for(let j=i*i; j<=num; j+=i){
                arr[j] = false;
            }
        }
    }
    return arr.filter(e => e).length;
}

이진 탐색(재귀 사용)

const binarySearch = (arr, target, start, end) => {
    if ( start > end ) {
        return;
    }
    const mid = Math.floor(( start + end ) / 2);
    if ( arr[mid] === target ) {
        return mid + 1;
    } else if ( arr[mid] > target ) {
        return binarySearch(arr, target, start, mid-1);
    } else {
        return binarySearch(arr, target, mid+1, end);
    }
};

퀵 정렬

function quickSort(arr, start, end) {
    if (start >= end) return;
    let pivot = start;
    let left = start + 1;
    let right = end;
    let temp;

    while (left <= right) {
        while (left <= end && arr[left] <= arr[pivot]) {
            left++;
        }
        while (right > start && arr[right] >= arr[pivot]) {
            right--;
        }
        if (left > right) {
            temp = arr[right];
            arr[right] = arr[pivot];
            arr[pivot] = temp;
        } else {
            temp = arr[right];
            arr[right] = arr[left];
            arr[left] = temp;
        }
    }

    quickSort(arr, start, right - 1);
    quickSort(arr, right + 1, end);

    return arr;
}