Jeong in Tech

문제

https://www.acmicpc.net/problem/15650

접근

문제 15649 N과 M(1) 과 비교했을 때,

• 고른 수열은 오름차순이어야 한다.

라는 조건이 추가됐다. 즉, [4,3] 의 경우 [3,4] 로 정렬되어 경우의 수 [4,3]와 [3,4]는 같은 것으로 간주된다.

N과 M (1)는 재귀를 위한 for loop에서 index를 항상 맨 처음부터 다시 돌았다면(모든 경우의 수를 위해), 이 문제에서는 지난 숫자는 제외하고 for loop을 진행한다(중복을 피하기 위해)

풀이

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ")
  .map(Number);

const [N, M] = input;
const output = [];
let result = "";
const checked = Array(N).fill(false);

function dfs(level, start) {

  if (level === M) {
    result += `${output.join(" ")}\n`;
    return;
  }

  for (let i = start; i < N; i++) {
    if (checked[i]) continue;
    
    checked[i] = true;
    output.push(i + 1);
    dfs(level + 1, i);
    output.pop();
    checked[i] = false;
  }
}

dfs(0, 0);

console.log(result);

[공부정리] 순열 vs 조합 vs 중복순열 vs 중복조합 (feat. 백준 N과 M 문제 시리즈)

문제

https://www.acmicpc.net/problem/15649

접근

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

➡️ 수의 범위가 작아 완전탐색 으로 접근

중복 없는 수열

➡️ 백트래킹

➡️ 수열 문제니까 조합(combination) 또는 순열(permutation) 인데, 중복이 없다고 했으므로 순열 문제.

풀이

const input = require("fs").readFileSync('/dev/stdin').toString().trim().split(" ").map(Number);

const [n, m] = input;
let result = "";
const output = [];
const checked = Array(n).fill(false);

function dfs(cnt) {
	
    if (cnt === m) {
        result += `${output.join(" ")}\n`;
        return;
    }

    for (let i = 0; i < n; i++) {
        if (checked[i] === true) continue;
        checked[i] = true;
        output.push(i + 1);
        dfs(cnt + 1);
        output.pop();
        checked[i] = false;
    }
}

dfs(0);

console.log(result);

문제

https://www.acmicpc.net/problem/14502

접근

- 완전탐색을 하며 지도에 벽3개를 세울 수 있는 경우를 모두 다 조사해야한다.

- 각 벽3개를 세운 경우를 복사하여, 해당 복사본으로 각 경우의 안전지대 수를 구한다.

- 가장 큰 안전지역의 갯수를 반환한다.

풀이

참조 풀이 - https://velog.io/@ywc8851/%EB%B0%B1%EC%A4%80-14502-%EC%97%B0%EA%B5%AC%EC%86%8C-javascript

const fs = require("fs");

// 문제 링크 : https://www.acmicpc.net/problem/14502
// 제출 시 path : /dev/stdin

const input = fs
  .readFileSync("./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map((v) => parseInt(v)));

const [COL, ROW] = input.shift();
const graph = input;

const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];

let max = Number.MIN_SAFE_INTEGER;

// 각 벽이 설치된 경우의 안전지대 갯수를 구한다.(BFS)
const countSafePlace = (graph) => {
  let cnt = 0;
  const queue = [];

  for (let i = 0; i < COL; i++) {
    for (let j = 0; j < ROW; j++) {
      if (graph[i][j] === 2) queue.push([i, j]);
    }
  }

  while (queue.length) {
    const [virusX, virusY] = queue.shift();

    for (let i = 0; i < 4; i++) {
      const [nx, ny] = [virusX + dx[i], virusY + dy[i]];

      if (nx >= 0 && nx < COL && ny >= 0 && ny < ROW && graph[nx][ny] === 0) {
        graph[nx][ny] = 2;
        queue.push([nx, ny]);
      }
    }
  }

  for (let i = 0; i < COL; i++) {
    for (let j = 0; j < ROW; j++) {
      if (graph[i][j] === 0) cnt++;
    }
  }

  return cnt;
};

const solution = (cnt) => {
  if (cnt === 3) {
    const copy = graph.map((v) => [...v]);
    const num = countSafePlace(copy); // 각 벽이 설치된 경우의 안전지대 갯수를 구한다.(BFS)
    max = max < num ? num : max;
    return;
  }
  for (let i = 0; i < COL; i++) {
    for (let j = 0; j < ROW; j++) {
      if (graph[i][j] === 0) {
        graph[i][j] = 1;
        solution(cnt + 1);
        graph[i][j] = 0;
      }
    }
  }
};

solution(0); // 1.벽3개를 세우는 전체 경우의 수를 구한다.(DFS)

console.log(max);

- DFS + BFS 풀이를 모두 쓰는 식이었다.

- DFS 에서 break 문 return 써서 꼭 해당 재귀 종료해주기.

- copy 꼭 해서 원본 배열 상하지 않도록 해주기.

- 왜 벽을 세울 때는 DFS 를, 바이러스를 퍼뜨릴 때는 BFS 를 사용한 걸까?

문제

https://www.acmicpc.net/problem/10828

접근

결과

9번 제출 & 힌트 1 끝에 성공!

- 계속 시간 초과가 낳는데 이 경우 console.log (출력)을 최소한으로 만들어야 하는 거였다. 일일이 출력 대신 result [] 에 담은 후 한 번에 출력했더니 시간 초과 문제를 해결할 수 있었다.

- 힌트를 통해 swtich 문에 default 를 넣어 더 잘쓰는 법을 배울 수 있었다.

풀이

참조 풀이

https://gurtn.tistory.com/67

안녕하세요,

글쓰는 또라이,
일명 글또 8기를 시작하게 되었습니다.

글또 공식 노션 보러가기

글또 페이스북 보러가기

왜 글또를 시작했나?

개발을 공부한지 1년, 다른 분야보다도 기술 분야는 글로 하는 소통이 더 활발할 분야라는 인상을 받았다.

짧은 프로젝트 하나를 하더라도 노션을 통해 서로의 작업 현황을 공유하는 부분이 인상적이었고,

서로 다른 시간에 작업하더라도 언제든 확인할 수 있게끔 기록을 남겨두는 것이란 생각이 들었다.

- 또 개인적으로는 전문적인 기술 내용의 공유는 말로 하기 보다 잘 정돈된 글로 공유할 때 더 효과적이라고 생각한다.

마지막으로 프로젝트가 끝난 후에도 '회고'라는 글쓰기 활동을 통해 스스로와 팀원들에게 소통하는 시간을 가지는 점에서도

개발 분야에서 글쓰기란, 개인성장과 동료 간의 소통을 위해 필수적인 역량이란 생각이 들었다.

추가적으로 개인 브랜딩과 홍보 수단으로써 글의 힘이 크다.

벨로그라는 개발자들을 위한 블로그 플랫폼도 따로 있을 정도로...

어느 개발 모임에 가도 '파워블로거'가 가지는 영향력이 크다는 것도 꽤 인상적이었다.

이런 점들을 고려할 때 꾸준한 글쓰기를 통해 미리 글쓰기 역량을 키워놓아야겠다는 생각이 들었다. 

하지만 이런 생각을 하고 야심차게 시작한 블로그를 방치한지 어느덧 1년이 다되었다.

무엇이든 습관이 되지 않은 것을 습관으로 만드는 데는 꾸준함이 필요한 법인데, 그게 참 혼자서 하기가 쉽지 않다.

그래서 글또를 신청하게 되었다.

뭐든 함께 하면 꾸준히 하기 쉽기에...글을 쓰지 않으면 자극해줄 누군가가 필요했다.

글또는 이런 곳이었다

개발자들이 모여 2주에 한 번씩 글을 쓰고 피드백을 받을 수 있는 커뮤니티.

예치금 10만원을 넣고 글을 한 번씩 쓰지 않을 때마다 돈이 차감된다.

영리 목적 모임은 아니기 때문에 이렇게 걷힌 금액은 기부된다고...

글의 양식은 자유! 회고를 써도 좋고 기술 정보 나누는 글을 써도 좋다고 한다.

무엇보다 좋은 점은 글또콘 등 다른 개발분야의 분들과 활발히 네트워킹 할 수 있는 곳이 있어 

지속적으로 영감을 받을 수 있는 장이 있다는 것이 매력적이다.

지원부터 OT까지, '개발자'들의 글쓰는 커뮤니티라 개발 관련 활동 질문이 많을 거란 예상과 달리

"너는 누구냐"는 철학적인(?) 질문이 많았다는 것이 의외였다.

그도 그럴 것이  글또는 지원서에서부터 "삶의 지도"를 그려보는 항목이 있었는데,

내 삶을 돌아보며 현재 나를 만든 과거의 일련의 사건들을 나열하고 성찰을 적는 것이었다.

보통 기술적인 질문을 묻는 것이 아니라 새로웠다. 이 시간을 통해 기술에 집중된 글을 쓰는 것도 중요하지만,

계속해서 내가 지금 어디에서 무엇을 하고 있는지를 인지하고

거시적인 방향성을 잃지 않는 것이 훨씬 중요하다는 생각을 하게 되었다.

반년간 4회정도 진행 예정이라는 커피드백 시간을 위한 설문조사에서 역시 "내가 어떤 사람인가"에 대한 질문이 주를 이뤘다.

그 중 "타인과의 관계 속의 나" 는 어떤 사람인지,를 돌아보게 해준 사진 속 질문이 인상 깊었다.

좋은 질문들 덕에 나에 대한 진솔한 성찰을 가질 수 있는 시간이었다.

앞으로는 자율적인 글쓰기 시간이 되기에, 위 질문들만큼 의미 있는 주제를 떠올릴 수 있을지 모르겠다.

그래도 글또가 단순 정보 전달보다 성찰을 통한 성장에 취지를 두고 만들어진 커뮤니티라는 걸 알 수 있었고,

이러한 모임에서의 교류를 통해 더 많은 영감을 받을 수 있으리라.

앞으로 글또에서

그렇게 시작한 2023 상반기, 글또와 함께하면서 계획한 일들을 회고하는 시간으로 가져가고자 한다.

 2023년 상반기 우선순위는 역시: 취업 준비, 그리고 방통대 학점 관리이다. 이에 대한 회고가 주를 이루는 주제가 될 것이다.

진솔한 성찰을 통해 배운 것을 소화하고 체화하고 싶다.

이를 위해 스스로를 위해 몇 가지 규칙을 세워보았다.

1. '매주 토요일 오전'은 글을 읽고 쓰는 시간으로 정한다.

2. 피드백을 활용한다. 내 머릿속에서 나오는 건 거기서 거기다.

매주 팀원들에게 피드백을 달고 받으며 피드백 시간을 활용하자.

3. 글쓰기가 다가 아니다. 적극적인 커피챗 참여를 통해 사람을 통해서도 영감 얻기.

4. 담백하게 쓴다. 쓸데없는 과장, 수사 x

5. 글쓰기 전 반드시 사실 확인을 한다.

6. 문체를 통일하여 일정한 문체를 유지한다.

7. 글은 올린 후에도 계속해서 퇴고한다.

8. 링크드인과 글또 슬랙을 이용해 다른 이들의 글을 읽는 시간을 가진다.

얼마나 지킬 수 있을지 모르겠지만 반 년간 한 번 열심히 해보자!

문제

https://www.acmicpc.net/problem/2178

접근

1. DFS -> time over

2. BFS 

풀이

take-1: 실패 (10)

- [0,3] 큐를 마지막으로 반복문이 멈췄다. 

- idxPairs 까지는 뽑히는데 validPairs 에서 아무것도 검출되지 않았다. -> nx, ny 범위조건을 둘다 N 으로 해놨었다.

const solution = (input) => {
  const [N, M] = input.shift().split(" ").map(Number);
  const graph = [...input].map((v) => v.split("").map(Number));
  let answer = Number.MIN_SAFE_INTEGER;

  const inValidRange = (pair) => {
    const [nx, ny] = pair;
    if (nx < 0 || ny < 0 || nx >= N || ny >= N) return false;
    else if (graph[nx][ny] === 1) return true;
    return false;
  };

  const bfs = (row, col) => {
    const queue = [[row, col]];
    const seen = new Array(N).fill(0).map(() => new Array(N).fill(false));
    seen[row][col] = true;
    let cnt = 1;

    while (queue.length) {
      const [x, y] = queue.shift();
      graph[x][y] = 0;
      const idxPairs = [
        [x - 1, y],
        [x, y + 1],
        [x + 1, y],
        [x, y + 1],
      ];
      const validIdxPairs = idxPairs.filter((v) => inValidRange(v));

      for (let idxPair of validIdxPairs) {
        const [nx, ny] = idxPair;
        if (graph[nx][ny] === 1 && !seen[nx][ny]) {
          seen[nx][ny] = true;
          cnt++;
          console.log("nx,ny: ", nx, ny, "\n", "cnt: ", cnt, "queue: ", queue);
          queue.push([nx, ny]);
        }
      }
    }
    return cnt;
  };

  const count = bfs(0, 0);
  answer = answer < count ? count : answer;

  return answer;
};

console.log(solution(input));

take - 2: fail (17)

const solution = (input) => {
  const [N, M] = input.shift().split(" ").map(Number);
  const graph = [...input].map((v) => v.split("").map(Number));
  let answer = Number.MIN_SAFE_INTEGER;

  const inValidRange = (pair) => {
    const [nx, ny] = pair;
    if (nx < 0 || ny < 0 || nx >= N || ny >= M) return false;
    if (graph[nx][ny] === 1) return true;
    return false;
  };

  const bfs = (row, col) => {
    const queue = [[row, col]];
    const seen = new Array(N).fill(0).map(() => new Array(M).fill(false));
    seen[row][col] = true;
    let cnt = 1;

    while (queue.length) {
      const [x, y] = queue.shift();
      graph[x][y] = 0;
      const idxPairs = [
        [x - 1, y],
        [x, y - 1],
        [x + 1, y],
        [x, y + 1],
      ];

      const validIdxPairs = idxPairs.filter((v) => inValidRange(v));
      console.log(x, y);
      console.log(idxPairs);
      console.log(validIdxPairs);

      for (let idxPair of validIdxPairs) {
        const [nx, ny] = idxPair;
        if (graph[nx][ny] === 1 && !seen[nx][ny]) {
          seen[nx][ny] = true;
          cnt++;
          queue.push([nx, ny]);
        }
      }
      console.log("queue: ", queue);
    }
    return cnt;
  };

  const count = bfs(0, 0);
  answer = answer < count ? count : answer;
  return answer;
};

console.log(solution(input));

tial-3: success!!

const solution = (input) => {
  const [N, M] = input.shift().split(" ").map(Number);
  const graph = [...input].map((v) => v.split("").map(Number));
  let answer = Number.MIN_SAFE_INTEGER;

  const inValidRange = (pair) => {
    const [nx, ny] = pair;
    if (nx < 0 || ny < 0 || nx >= N || ny >= M) return false;
    if (graph[nx][ny] === 1) return true;
    return false;
  };

  const bfs = (row, col) => {
    const queue = [[row, col]];
    const seen = new Array(N).fill(0).map(() => new Array(M).fill(0));
    seen[row][col] = 1;

    while (queue.length) {
      const [x, y] = queue.shift();
      graph[x][y] = 0;
      const idxPairs = [
        [x - 1, y],
        [x, y - 1],
        [x + 1, y],
        [x, y + 1],
      ];

      const validIdxPairs = idxPairs.filter((v) => inValidRange(v));
      console.log(x, y);
      console.log(idxPairs);
      console.log(validIdxPairs);

      for (let idxPair of validIdxPairs) {
        const [nx, ny] = idxPair;
        if (graph[nx][ny] === 1 && !seen[nx][ny]) {
          seen[nx][ny] = seen[x][y] + 1;
          queue.push([nx, ny]);
        }
      }
      console.log("queue: ", queue);
    }
    return seen[N - 1][M - 1];
  };

  const count = bfs(0, 0);
  answer = answer < count ? count : answer;
  return answer;
};

console.log(solution(input));

문제

https://www.acmicpc.net/problem/2667

접근

풀이

// 공통 상단 코드
// 백준 제출시
// const address="/dev/stdin"

// VSC 테스트시
const address = "./input.txt";
const input = require("fs")
  .readFileSync(address)
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split("").map(Number));

시도 1

결과: 실패

3,9,7,11

로 나옴 (답은 3,7,8,9)

seen(visited) 에 뭔가 중복이 있을 거라 생각하고 봤더니

Set()은 중복값이 안되는 걸로 알았는데 object 는 배열로 안치나보다. 

const solution = (input) => {
  const [N, ...graph] = input;
  let numOfComplex = 0;
  const houses = [];

  const filter = (pair) => {
    const [nx, ny] = pair;
    if (nx < 0 || ny < 0 || nx >= N || ny >= N) return false;
    else if (graph[nx][ny] === 1) return true;
    return false;
  };

  const bfs = (row, col) => {
    const seen = new Set();
    const queue = [[row, col]];
    seen.add([row, col]);
    let house = 0;
    console.log(`queue (${row}, ${col}): `, queue, "\n");

    while (queue.length) {
      const [x, y] = queue.shift();
      console.log("shifted: ", [x, y]);
      console.log("seen: ", seen);
      console.log("queue after loop: ", queue);
      graph[x][y] = 0;
      const idxPairs = [
        [x - 1, y],
        [x, y + 1],
        [x + 1, y],
        [x, y - 1],
      ];
      const validIdxPairs = idxPairs.filter((idx) => filter(idx));
      console.log("valid pairs:", validIdxPairs, "\n");
      for (const idxPair of validIdxPairs) {
        const [nx, ny] = idxPair;
        if (graph[nx][ny] === 1 && !seen.has([nx, ny])) {
          seen.add([nx, ny]);
          house++;
          queue.push([nx, ny]);
        }
      }
    }

    houses.push(house);
  };

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (graph[i][j] === 1) {
        numOfComplex++;
        bfs(i, j);
      }
    }
  }

  const answer = [numOfComplex, ...houses];
  return answer.join("\n");
};

console.log(solution(input));

시도2

수정사항:

- seen set -> arr

- house++ 새 라운드 시작할 때도 실행

- 인풋 받을 때 "\n" 까지만 받고 일일이 할당. 구조분해 x. 

결과: 실패

콘솔에는 답으로 뜨나 백준 제출시 "틀렸습니다"

const solution = (input) => {
  const N = +input.shift();
  const graph = input;
  let numOfComplex = 0;
  const houses = [];

  const filter = (pair) => {
    const [nx, ny] = pair;
    if (nx < 0 || ny < 0 || nx >= N || ny >= N) return false;
    else if (graph[nx][ny] === 1) return true;
    return false;
  };

  const bfs = (row, col) => {
    const seen = new Array(N).fill(0).map(() => new Array(N).fill(false));
    const queue = [[row, col]];
    let house = 0;
    seen[row][col] = true;
    house++;

    while (queue.length) {
      const [x, y] = queue.shift();
      graph[x][y] = 0;
      const idxPairs = [
        [x - 1, y],
        [x, y + 1],
        [x + 1, y],
        [x, y - 1],
      ];
      const validIdxPairs = idxPairs.filter((idx) => filter(idx));
      for (const idxPair of validIdxPairs) {
        const [nx, ny] = idxPair;
        if (graph[nx][ny] === 1 && !seen[nx][ny]) {
          seen[nx][ny] = true;
          house++;
          queue.push([nx, ny]);
        }
      }
    }

    houses.push(house);
  };

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (graph[i][j] === 1) {
        numOfComplex++;
        bfs(i, j);
      }
    }
  }

  const answer = [numOfComplex, ...houses];
  return answer.join("\n");
};

console.log(solution(input));

문제

https://www.acmicpc.net/problem/2606

접근 

기본적인 그래프 탐색 문제. 

연결된 노드가 몇 개인지를 구하는.

단, 맨 처음 노드 시작을 인덱스 0이 아닌 1로 시작해줘야 한다.

풀이

const fs = require("fs");
const input = fs.readFileSync("./input.txt").toString().trim().split("\n");

function solution(input) {
  const N = +input.shift(); // 노드 수
  const M = +input.shift(); // 간선 수
  const edges = input.map((v) => v.split(" ").map(Number));

  // 그래프 그리기
  const vertices = Array(N + 1)
    .fill(0)
    .map(() => []);
  for (let edge of edges) {
    const [v0, v1] = edge;
    vertices[v0].push(v1);
    vertices[v1].push(v0);
  }

  // 실행
  const seen = new Set();
  let count = 0;
  const dfs = (start) => {
    for (let end of vertices[start]) {
      if (!seen.has(end)) {
        seen.add(end);
        count++;
        dfs(end);
      }
    }
  };
  seen.add(1);
  dfs(1);
  console.log(seen);
  return count;
}

console.log(solution(input));

참조: https://www.acmicpc.net/source/54379165

문제

https://www.acmicpc.net/problem/2468

접근 

- N보다 큰 수가 있는 부분을 탐색하고, 한 부분의 탐색이 끝날 때 cnt++ 을 한다. cnt 최댓값을 구한다. 

- 결과: 중도포기

풀이

// 백준 제출시
// const address="/dev/stdin"

// VSC 테스트시
const address = "./input.txt";
const input = require("fs").readFileSync(address).toString().trim().split("\n");

const N = +input[0];
const areas = input.slice(1).map((v) => v.split(" ").map((v) => +v));

const offsetX = [0, 0, -1, 1];
const offsetY = [-1, 1, 0, 0];

const dfs = (x, y, height, visited) => {
  offsetX.forEach((dx, i) => {
    const nx = x + dx;
    const ny = y + offsetY[i];
    if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny]) {
      visited[nx][ny] = true;
      dfs(nx, ny, height, visited);
    }
  });
};

let maxCount = 0;
for (let height = 0; height <= 100; height++) {
  let count = 0;
  const visited = [...Array(N)].map((_, x) =>
    [...Array(N)].map((_, y) => areas[x][y] <= height)
  );
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (!visited[i][j]) {
        visited[i][j] = true;
        dfs(i, j, height, visited);
        count++;
      }
    }
  }
  maxCount = Math.max(maxCount, count);
}

console.log(maxCount);

출처(https://tesseractjh.tistory.com/188)

문제

https://www.acmicpc.net/problem/2178

접근

 두 정수 N, M(2 ≤ N, M ≤ 100) 으로 완전탐색을 해도 무방하다.

DFS:

D(0,0) -> D

1. 백트래킹을 어떻게 하지?

visited 이용

2. 행과 열의 크기가 다를 때 도착지점 설정

더 긴 쪽만큼 순환

3. case3 통과 x

각각의 수들은 붙어서 입력으로 주어진다. <- 이 부분을 주의해서 N,M,graph 입력을 수정해줬더니 해결.

4. 시간 초과...

-> BFS 로 풀어보자.

풀이

풀이 참조

인프런 강의 그래프 탐색 - 섬나라 아일랜드 문제와 비슷하여 이를 참고했다.

같은 문제 dfs vs bfs 접근 비교

문제

https://www.acmicpc.net/problem/14888

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

접근

3    //N
3 4 5 // 수열
1 0 1 0 // 각각 +,-,*,/ 연산자의 갯수

이라면

만들 수 있는 식

3+4*5 = 35

3*4+5 = 17

- 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 이므로 -> 완전탐색 

- 수열은 이미 주어졌으니 따로 구할 필요 x

- 연산자의 순서에 따라 값이 달라지니 순열(permutation) 문제겠구나.

-- 1. 들어온 수열과 연산자를 각각 다른 배열에 넣는다. 

-- 2. 수열.join("연산자")로 반복문을 돌린다.

--- 2-1.결과를 array 에 푸시한다. 

--- 2-2.연산자 배열의 위치를 바꾼다.

-- 3. 결과 배열에서 가장 작은 수와 가장 큰 수를 찾아 리턴한다.

1. 들어온 수열과 연산자를 각각 다른 배열에 넣는다. 

const input = require("fs")
  .readFileSync(address)
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map(Number));

function getOperations(arr) {
  const operations = ["+", "-", "*", "/"];

  operations.forEach((v, idx) => {
    let amount = arr[idx];
    for (let j = 0; j < amount; j++) {
      operations.push(operations[idx]);
    }
  });

  return operations;
}

function solution(input) {
  const [N, A, amount] = input;
  const operations = getOperations(amount);

  return operations;
}

 2-1. 재귀를 이용해 결과를 array 에 푸시한다.

// 백준 제출시
// const address="/dev/stdin"

// VSC 테스트시
const address = "./input.txt";

const input = require("fs")
  .readFileSync(address)
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map(Number));

const getOperations = (arr) => {
  const operations = ["+", "-", "*", "/"];

  operations.forEach((v, idx) => {
    let amount = arr[idx];
    for (let j = 0; j < amount; j++) {
      operations.push(operations[idx]);
    }
  });

  return operations;
};

function solution(input) {
  const [N, A, amount] = input;
  const operations = getOperations(amount);

  const results = [];
  let result = Number.MAX_SAFE_INTEGER;
  let check = Array(N).fill(0);

  const recursion = (idx) => {
    if (idx === N - 1) return;
    const copy = [...A];
    let tmpOp = operations.slice(0, 2);
    copy.splice(idx + 1, 0, tmpOp[0]);
    copy.splice(N, 0, tmpOp[1]);
    let tmp = operations.shift();
    operations.push(tmp);
    const test = eval(copy.join(""));
    results.push(test);
  };

  recursion(0);

  let min = Math.min(...results);
  let max = Math.max(...results);
  let answer = `${min}\n${max}`;

  return answer;
}

console.log(solution(input));

2-2.연산자 배열의 위치를 바꾼다.

const changeArrayOrder = function(list, targetIdx, moveValue) {
  // 배열값이 없는 경우 나가기
  if (list.length < 0) return;

  // 이동할 index 값을 변수에 선언
  const newPosition = targetIdx + moveValue;

  // 이동할 값이 0보다 작거나 최대값을 벗어나는 경우 종료
  if (newPosition < 0 || newPosition >= list.length) return;

  // 임의의 변수를 하나 만들고 배열 값 저장
  const tempList = JSON.parse(JSON.stringify(list));

  // 옮길 대상을 target 변수에 저장하기
  const target = tempList.splice(targetIdx, 1)[0];

  // 새로운 위치에 옮길 대상을 추가하기
  tempList.splice(newPosition, 0, target);
  return tempList;
};

풀이

시도 끝에 결국 실패. 여전히 재귀로 구현하는 것은 아직 어렵다.

// 백준 제출시
// const address="/dev/stdin"

// VSC 테스트시
const address = "./input.txt";

const input = require("fs")
  .readFileSync(address)
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map(Number));

const getOperations = (arr) => {
  const operations = ["+", "-", "*", "/"];

  operations.forEach((v, idx) => {
    let amount = arr[idx];
    for (let j = 0; j < amount; j++) {
      operations.push(operations[idx]);
    }
  });

  return operations;
};

function solution(input) {
  const [N, A, amount] = input;
  const operations = getOperations(amount);

  const results = [];
  let result = Number.MAX_SAFE_INTEGER;
  let check = Array(N).fill(0);

  const recursion = (idx) => {
    if (idx === N - 1) return;
    const copy = [...A];
    let tmpOp = operations.slice(0, 2);
    copy.splice(idx + 1, 0, tmpOp[0]);
    copy.splice(N, 0, tmpOp[1]);
    let tmp = operations.shift();
    operations.push(tmp);
    const test = eval(copy.join(""));
    results.push(test);
  };

  recursion(0);

  let min = Math.min(...results);
  let max = Math.max(...results);
  let answer = `${min}\n${max}`;

  return answer;
}

console.log(solution(input));

참조풀이

https://gobae.tistory.com/49

https://junghyeonsu.tistory.com/196