DS & Algorithm/baekjoon

[백준] 1157번 단어 공부 - JavaScript(NodeJS)

문제 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net 풀이 생각보다 엄청 간단하면서 생각보다 까다로울 수 있는 문제다. 문제의 키포인트는 아스키 코드를 활용해서 문자를 숫자로 바꿀 수 있느냐 일 듯 하다. 풀이 방향 조건이 생각보다 많다. 알파벳 대소문자를 구별하지 않으며, 알파벳 개수를 카운트 해야 하고 가장 많이 사용된 알파벳을 출력하는데, 2개 이상이라면 ?를 출력해줘야 한다. 내가 풀이한 방향은 다음과 같다. 1. 단어를 대문자로 바꾸고 A-Z순으로 정렬한다. 2. 단어의 각 알파벳들을 아스키코드를 이용해 A=0, Z=25의 인덱스 취..

[백준] 9663번 N-Queen - JavaScript(NodeJS)

문제 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 가장 중요한 문제의 조건은 퀸의 움직임이다. 퀸은 한 번 움직일 때 자기 위치에서 상하좌우+대각선 중 한 방향으로 무한정 이동 가능하다. 따라서 퀸이 서로 공격을 할 수 없는 예시를 그려보면 아래 그림과 같다. 이외에도 여러 경우가 있을테니, N이 주어졌을 때 퀸을 놓는 경우의 수를 구하면 된다. 풀이 방향 퀸의 움직임을 알고나면 문제가 쉬워진다. N개를 배치해야 하므로 DFS를 이용해 문제를 풀어보자. DFS에서 N x N를 모두 조회할 필요는 없다. 퀸은 서로 다..

[백준] 16198번 에너지 모으기 - JavaScript(NodeJS)

문제 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 풀이 N개의 에너지 구슬이 있다. 첫번째, 마지막을 제외한 X번째 구슬을 선택했을 때 다음을 따른다. 1 X번째 에너지 구슬을 제거한다. 2 X-1번째, X+1번째 에너지를 더해준다. 3 X번째 에너지 구슬이 제거되었으므로, 전체 N개의 구슬에서 1을 감소시키고 새로운 X번째 구슬을 선택한다. 4 에너지 구슬이 2개 남을 때 까지 반복했을 때 모은 에너지 양의 최댓값을 구하면 된다. 구슬의 개수가 3 { input.push(line); }) .on("c..

[백준] 16197번 두 동전 - JavaScript(NodeJS)

문제 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 풀이 문제의 조건을 요약해보자. 동전이 2개 주어진다. 버튼을 클릭해서 동전을 상하좌우로 이동시킨다. 동전은 벽을 넘을 수 없고, 보드에서 떨어뜨릴 수 있다. 두 동전은 같은 방향으로 한 칸씩 이동한다. 이를 참고해 두 동전 중 하나만을 떨어뜨리기 위해 버튼을 최소 몇번 눌러야 할지 구하자. 풀이 방향 우선 동전의 위치를 구해야 한다. 별 다른 방법이 없으므로, 보드 행렬에서 한칸씩 모두 조회해야 한다. 2개의 동전의 위치를 모두 구했다면, 버튼을 눌러 동..

[백준] 15658번 연산자 끼워넣기(2) - JavaScript(NodeJS)

문제 15658번: 연산자 끼워넣기 (2) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대 www.acmicpc.net 풀이 연산자 끼워넣기 { const N = +input[0]; const numbers = input[1].split(" ").map(Number); const operator = input[2].split(" ").map(Number); const operObj = { 0: (oper1, oper2) => oper1 + oper2, 1: (oper1, oper2) => oper1 - oper2, 2..

[백준] 14225번 부분수열의 합 - JavaScript(NodeJS)

문제 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 풀이 1182번 문제 풀이 sum + val, 0); sumArr[sum] = 1; return; } pick.push(S[L]); dfs(L + 1); pick.pop(); dfs(L + 1); } dfs(0); for (let i = 1; i < MAX_SUM; i++) if (!sumArr[i]) return i; }; // 백준에서 입력을 받는 코드 const input = []; r..