algorithm

[백준] 1697번 숨바꼭질 _ Node.js

문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 풀이 이 문제는 1초씩 움직이며 동생에게 도착하는 최소 시간을 구하는 문제이므로 BFS를 사용해보았다. 수빈이는 1초마다 +1 , -1 , X2로 세가지 방법으로 움직일 수 있다. 이 때 위치는 0 stdin[line++]; })(); function solution(){ const [N, K] = input().split(" ").map(Number); co..

[백준] 15988번 1, 2, 3 더하기 3

문제 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 해당 문제의 예시 입/출력을 보자. 4, 7, 10과 같은 작은 수가 나오더라도 이에 수 십배의 경우의 수가 나온다. n의 최댓값이 1,000,000인 것을 감안하면 완전 탐색은 불가능하다. 문제를 조금 더 분석해보자. 식으로 나타낼 수 있는 숫자는 1, 2, 3이다. 나타내야 하는 수를 k라 할 때, k를 나타내기 위해서는 k보다 작은 수에서 1,2,3을 더하면 된다. 즉 k를 1,2,3으로 나타 낼 수 있는 방법 k-1 +1, ..

[백준] 2178번 미로 탐색

문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 풀이 해당 문제는 처음에 DFS로 시도하였다. 하지만 시간초과가 나왔다. 미로의 최대 크기는 100X100 사이즈이므로 DFS나 완전 탐색으로 풀이 할 경우 시간 초과가 뜬다. 이 후 BFS로 풀이를 하였다. DFS는 queue의 현재 위치를 shift하여 해당 점에서 움직일 수 있는 모든 방향을 queue에 추가한다. 이 때 막히거나 방문한 곳은 push하지 않는다. 더해서 맵과 같은 크기의 이중 배열 visited..

[백준] 14888번 연산자 끼워넣기

문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 1+2+3-4×5÷6 1÷2+3+4-5×6 1+2÷3×4-5+6 1÷2×3-4+5+6 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌..

[Programmers]큰 수 만들기

문제 > 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 해당 문제는 탐욕범을 사용하여 풀 수 있다. 숫자를 제거하며 높은 자리 부터 탐욕적으로 채워나가면 된다. 주어지는 number의 첫 자리부터 시작하여 비어있는 stack에 하나씩 psuh해준다. push를 하기 전 저장된 stack의 top의 값과 비교한다. 이 때 top보다 현재 자리의 숫자가 크다면 해당 top을 pop해준다. 이렇게 pop된 숫자는 제거가 된 숫자이다. 그렇기에 제거가 될 때 k를 -1 해준다. 해당 과정을 반복하여 k가 0이 되면 해당 과정을 멈추고 sta..

순열/조합 (Permutation / Combination)

1. Combination (조합) 조합 : 순서 없이 n개 중에 r개를 뽑는 것 예) 10C3 = 1098 / 321 = 120 nCr = nCn-r이므로 10C3 = 10C7 const getCombinations = (array, selectNumber) => { const results = []; if(selectNumber === 1){ return array.map((element) => [element]); } array.forEach((fixed, index, origin) => { const rest = origin.slice(index+1); const combinations = getCombinations(rest, selectNumber - 1); const attached = co..