DS & Algorithm

[프로그래머스] 땅따먹기 - 자바스크립트

문제 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 풀이 처음에는 DFS로 접근했다. N회까지 재귀를 돌면서, X행에서는 X-1행에서 선택하지 않은 열을 선택하여 더했다. 각각의 경우의 수로부터 N행까지 도달했을 때, 최댓값일 경우 최댓값을 갱신하도록 했다. 물론 주어진 행 N이 최대 100,000이기 때문에 재귀 호출로 인한 시간초과 이슈가 발생했다. 모든 경우의 수를 조회할 수 없다면, DP(동적 계획법)를 생각해봐야 한다. 풀이방법 DP답게 생각해보자. land 행렬은 N x 4 크..

[백준] 15990번 1, 2, 3 더하기 5 - JavaScript(NodeJS)

문제 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 숫자 n을 1,2,3의 합으로 표현하는 경우의 수를 구한다. 1,2,3을 여러 번 사용할 수 있으나, 연속되게 사용하면 안된다. 숫자 4를 표현할 때 1+1+2, 2+2 와 같이 연속되게 같은 숫자를 사용할 수 없다. 이 문제는 dp 유형으로 점화식을 구해야 한다. 우선 1부터 시작해보자. n=1 일 때, 1 n=2 일 때, 2 n=3 일 때, 1+2, 2+1, 3 n=4 일 때, 1+2+1, 1+3, 3+1 n=5 일 때, 1+3+1, 2+1+2, 3+2, 2+3 사실 이렇게만 보면 점화식을 파악하기 ..

[백준] 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개의 동전의 위치를 모두 구했다면, 버튼을 눌러 동..