알고리즘 이론 & 풀이

[백준] 1026번 - 보물 (nodejs)

1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 결과만 놓고 보자면 A는 오름차, B는 내림차로 정렬해서 곱하면 간단하게 풀리겠지만, 나는 문제에서 제시한대로 정직하게 B는 냅두고 A만 재배열하는 방법을 고안해 풀어보았다. 문제 옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다. 길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자. S = A[0] × B[0] + ... + A[N-1] × B[N-1] S의..

프로그래머스 Lv.0 | 저주의 숫자 3

문제 - https://school.programmers.co.kr/learn/courses/30/lessons/120871 풀이 for i는 0부터 n까지 1씩 증가하며 count를 증가시킨다. 만약 증가시킨 수가 3의 배수거나 3을 포함한다면, 그것을 벗어날 때까지 계속 1씩 증가시킨다. 그렇게 n번 숫자를 세면 최종 결과를 반환한다. function solution(n) { let count = 0; for(let i = 0; i < n; i++) { count++; while(count % 3 === 0 || count.toString().includes('3')) count++; } return count; }

[백준] 2178번 - 미로 탐색

문제 https://www.acmicpc.net/problem/2178 // 입력 4 6 101111 101010 101011 111011 // 출력 15 풀이 BFS로 최단거리 찾기 문제. 맨 처음에 풀 때는 백트래킹을 안해줘서 시간제한에 걸렸는데, visitied로 방문했던 곳을 관리해 한번 갔던 곳은 다시 안 가게 했더니 통과했다. const fs = require('fs'); const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n'); const [N, M] = input[0].trim().split(' ').map(Number); const maps = []; for (let i = 1; i < input.length; i..

[백준] 1260번 - DFS와 BFS (js)

문제 https://www.acmicpc.net/problem/1260 풀이 4 5 1 1 2 1 3 1 4 2 4 3 4 이걸 아래와 같이 정리한다. [ [], [ 2, 3, 4 ], [ 1, 4 ], [ 1, 4 ], [ 1, 2, 3 ] ] 1번 인덱스에 [2, 3, 4]가 있다는 것은 1과 2, 3, 4번 노드가 연결되어 있다는 뜻이다. 그리고 visited 배열을 둬서 갔던 곳을 다시 방문하지 않도록 true/false로 관리한다. graph와 visited 배열 모두 0번 인덱스는 비워두고 시작해서 직관적으로 1번 인덱스가 1번 노드라는 것을 알 수 있게 한다. dfs는 깊이 우선 탐색이기 때문에 for문과 재귀호출을 이용해서 구현한다. 아래로 파고들었다가 빠져나오면 for문을 이용해 형제 노..

프로그래머스 Lv.2 | 괄호 회전하기 js

문제 https://school.programmers.co.kr/learn/courses/30/lessons/76502 풀이 x만큼 왼쪽으로 회전한다는 것은 문자열을 0부터 x까지 잘라서, x+1 이후의 문자열의 꽁무니에 붙이는 것과 같다. substring으로 문자열을 양분해서 앞쪽 것을 뒤에 붙여주자. 괄호의 열림, 닫힘 여부는 stack을 사용하고, 괄호의 짝을 확인하기 위해 Map object에 짝을 저장해놓는다. 0부터 x번까지 모든 회전하는 경우의 수를 구해야 하므로 회전은 바깥for문이 담당한다. 본인이 왼쪽 괄호인지는 Map에 key가 존재하는지로 확인하고, 왼쪽 괄호라면 stack에 집어넣는다. 만약 Map에 없다면 오른쪽 괄호이므로 stack에 있던 것을 pop해서 본인의 짝인지 확인해..

프로그래머스 Lv.2 | 피보나치 수 js

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12945 풀이 n은 2 이상이므로 for문은 2부터 시작한다. 그리고 0과 1에 대한 값을 미리 초기화해놔서 F(2)부터 구해나가는데 문제가 없도록 한다. F(n)에 도달하게 되어 다 구하면 for문이 종료되고 맨 마지막 값이 바로 피보나치 수가 된다. 맨 마지막에 1234567로 나누지 않고 중간중간 나누는 이유는 바로 오버플로우의 위험 때문이다. 피보나치 수는 일정 수준이 되면 수가 매우 커지는데 이때 오버플로우가 발생해 -값으로 변해 의도치 않은 값으로 변해버릴 수 있다. 따라서 중간에 틈틈히 1234567의 나머지로 바꿔주는 것이다. function solution(n) { const f..

프로그래머스 Lv.2 | (스택/큐) 기능개발 js

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42586?language=javascript 풀이 큐로 풀었다. 기능개발에 걸리는 기간은 Math.ceil((100 - progresses[0]) / speeds[0]) 맨 앞에 있는게 안 나가면 뒤에는 맨 앞 날짜보다 작거나 같은 날짜가 계속 쌓이게 된다. 날짜 배열의 [0]번보다 큰 날짜가 나온다면 그동안의 기능들을 다 배포하게 되는데, 개발한 기능의 개수를 세주고 날짜 배열을 비우고, 새로운 날짜 기준부터 다시 시작한다. function solution(progresses, speeds) { const answer = []; let dates = [Math.ceil((100 - progre..

프로그래머스 Lv.1 | (스택/큐) 같은 숫자는 싫어 js

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12906?language=javascript 풀이 방법 1) 슬라이딩 윈도우 슬라이딩 윈도우 방식으로 풀었다. 본인과 본인 앞자리를 비교하는 방식이다. function solution(arr) { let answer = [arr[0]]; for(let i = 1; i < arr.length; i++) { if(arr[i - 1] !== arr[i]) answer.push(arr[i]); } return answer; } 방법 2) stack 아니면 answer의 맨 마지막 값과 중복되지 않는 새로운 수를 만나면 배열에 push하는 방식으로 풀 수도 있다. function solution(arr)..