자료구조 알고리즘 문제 (다시 보기)

---

 

 

문제 1

 

피보나치 수열을 순차적으로 출력하는 클로저 형태의 함수를 작성하기.

 

* 출력

: 호출될 때마다 다음 피보나치 수를 리턴하는 함수를 리턴해야 한다.

* 주의 사항

: 피보나치 수는 0과 1로 시작하며, 다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 됩니다.

* 예시) 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

: 리턴되는 클로저 내부 함수(inner function)의 구현은 recursive 혹은 iterative한 방법 중 어떤 것이어도 괜찮습니다.

* 입출력 예시

const fn = test1();
console.log(fn()); // --> 0
console.log(fn()); // --> 1
console.log(fn()); // --> 1
console.log(fn()); // --> 2
console.log(fn()); // --> 3
console.log(fn()); // --> 5

function test1() {
    // 0: 1 / 1: 1 / 2: 1 / 3: 2 / 4: 3 / 5: 5
    let num = 0;
    const fibonacci = function(num) { // 피보나치구하는 함수 만들기
      if (num < 2) return num;
      return fibonacci(num-2) + fibonacci(num-1)
    }
    return function() { // 함수를 리턴하면서 num++로 기록해준다.
      num++;
      return fibonacci(num-1)
    }
  }

 

문제 2

 

객체를 요소로 갖는 배열과 id를 입력받아, 해당 id값을 가지고 있는 객체를 리턴해야 합니다.

 

 

* 입력

 

인자 1 : arr

객체를 요소로 갖는 배열

arr[i]는 'id', 'name', 'children' 등의 속성을 갖는 객체

 

인자 2 : id

number 타입의 id

 

* 출력

 

object 타입을 리턴해야 합니다.

 

* 주의 사항

 

입력으로 주어지는 배열은 재귀적 구조를 가지고 있습니다. (입출력 예시 참고)

배열이 요소인 객체가 'children' 속성을 가질 경우, 해당 값은 초기 입력(arr)과 같은 구조를 지닌 배열입니다.

중첩 구조의 깊이(depth)에는 제한이 없습니다.

함수 test2는 재귀 함수로 구현되어야 합니다.

입력받은 id를 가진 객체가 없을 경우, null을 리턴해야 합니다.

입출력 예시 👇🏻

let input = [
  {
    id: 1,
    name: 'johnny',
  },
  {
    id: 2,
    name: 'ingi',
    children: [
      {
        id: 3,
        name: 'johnson',
      },
      {
        id: 5,
        name: 'steve',
        children: [
          {
            id: 6,
            name: 'lisa',
          },
        ],
      },
      {
        id: 11,
      },
    ],
  },
  {
    id: '13',
  },
];

let output = test2(input, 1);
console.log(output); // --> { id: 1, name: 'johnny' }

output = test2(input, 5);
console.log(output); // --> { id: 5, name: 'steve', children: [{ id: 6, name: 'lisa' }] }

output = test2(input, 99);
console.log(output); // --> null

function test2(arr, id) {
  // 객체를 요소로 갖는 배열과 id를 입력받아, 해당 id값을 가지고 있는 객체를 리턴
  // 반복문을 돌면서, 
  let newArr = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i].id === id) {
      return arr[i]
    } else if (arr[i].children) {
      let arrChild = arr[i].children
      newArr = newArr.concat(arrChild)
    }
  }
  if (newArr.length > 0) {
    return test2(newArr, id)
  }
  return null;
}

 

문제 3

간선들의 목록들을 받아 2차원 배열의 무향 그래프 매트릭스를 출력하는 함수를 작성해야 합니다. 입력값은 모두 2차원 배열이며, 배열의 인덱스를 그래프의 버텍스로 간주합니다. 첫 번째 입력값은 만드려는 매트릭스의 간선을 나타내었고, 두 번째 입력값은 삭제하려는 간선을 나타냅니다.

조건

각 간선은 2가지 정보를 담고 있습니다.
0번째: 간선의 시작 정점 (0 이상의 정수)
1번째: 간선의 도착 정점 (0 이상의 정수)

출력

2차원 배열의 무향 그래프를 출력하는 함수를 리턴해야 합니다.

주의 사항

두 번째 입력값의 삭제하려는 간선이 첫 번째 입력값에 없다면 무시합니다.
두 번째 입력값의 최대 버텍스는 첫 번째 입력값의 최대 버텍스와 동일합니다.
정점 0에서 정점 4로 이어주는 간선이 존재할 경우 정점 1, 2, 3도 존재합니다.
출력하는 버텍스의 개수는 입력값의 최대 버텍스 값을 초과하지 않습니다. (예: insertEdges의 최대 버텍스가 3이라면, 최대 크기가 3인 그래프입니다.)
반환하는 인접행렬은 2차원 배열이며, 행(row)는 바깥 배열, 열(column)은 안쪽 배열입니다.

let matrix = [[0, 0], [0, 0]]
matrix[0] === 0번째 행
matrix[0][0] === 0번째 행의 0번째 열
두 정점간의 간선의 유무는 0과 1로 표시합니다.
0: 두 정점간에 간선이 존재하지 않을 경우
1: 두 정점간에 간선이 존재할 경우

아래의 2차원 배열에서 세로축은 시작 정점, 가로축은 도착 정점입니다.

입출력 예시 👇🏻

// matrix 예시
const matrix = [
	[0, 0, 0],
	[0, 0, 0],
	[0, 0, 0],
];
const insertEdges = [
  [0, 3],
  [0, 2],
  [1, 3],
  [2, 1],
];
const removeEdges = [[1, 3], [1, 0]];
let output1 = test3(insertEdges, removeEdges);

console.log(output1);
/**
 * [
 *  [0, 0, 1, 1],
 *  [0, 0, 1, 0],
 *  [1, 1, 0, 0],
 *  [1, 0, 0, 0]
 * ]
 */

const insertEdges2 = [
  [0, 2],
  [2, 4],
  [1, 3],
  [2, 1],
];
const removeEdges2 = [
  [0, 3],
  [2, 1],
  [1, 0],
  [4, 2]
];

let output2 = test3(insertEdges2, removeEdges2);

console.log(output2);
/**
 * [
 *  [0, 0, 1, 0, 0],
 *  [0, 0, 0, 1, 0],
 *  [1, 0, 0, 0, 0],
 *  [0, 1, 0, 0, 0],
 *  [0, 0, 0, 0, 0],
 * ]
 */

function test3(insertEdges, removeEdges) {
  // 먼저 만들어줄 matrix의 길이를 구하는 작업
  const maxRow = insertEdges.map(function(row){ return Math.max.apply(Math, row); });
  const maxNum = Math.max.apply(null, maxRow); // max=최댓값이므로 max+1의 길이만큼 배열을 만들고 0을 채우자
  const matrix = Array.from(Array(maxNum+1), () => Array(maxNum+1).fill(0)); // 0으로 채운 matrix
  // 간선을 더하는 작업
  insertEdges.forEach((edge) => {
    const [ row , col ] = edge
    matrix[row][col] = 1
    matrix[col][row] = 1
  })
  // 간선을 삭제하는 작업
  removeEdges.forEach((edge) => {
    const [ row , col ] = edge
    matrix[row][col] = 0;
    matrix[col][row] = 0;
  })
  return matrix
}

 

---