Front-end/알고리즘(82)
-
[백준] 1463. 1로 만들기 (자바스크립트/javascript/js/node.js/동적계획법/다이나믹프로그래밍/동적프로그래밍)
문제를 풀기 위한 아이디어 Bottom-up 방식으로 접근해본다. dp 배열을 만든다. dp[n]에는 숫자 n이 1이 되기 위해 연산한 최소 횟수가 저장될 것이다. dp[1] = 0 이다. (1은 아무짓도 안해도 1이 되기 때문에) dp[2]는 2가 되기 전에 1에다 +1을 해야 나올 수 있는 수 이기 때문에 dp[1] + 1 = 1이 된다. (+1이라는 것은 연산횟수가 한 번 더해지기 때문에 더한 것이다.) dp[3]은 3이 되기 전에 이 수가 2였을 수도 있고 1이였을 수도 있다. 즉, 2에다 1을 더해도 3이 되고, 1에다 3을 곱해도 3이 된다. 즉 dp[3] = (dp[2] + 1 , dp[1] + 1) 중 최솟값이 된다. 그럼 dp[4]부터는 어떻게 구할 수 있을까? dp[4]는 2로 나누어 ..
2021.07.08 -
[백준] 1932. 정수 삼각형 (자바스크립트/javascript/js/node.js/동적계획법/동적프로그래밍/다이나믹프로그래밍)
문제를 풀기 위한 아이디어 삼각형의 각각 n번째 줄을 행이라고 하고 그 행에서 하나의 요소들을 열이라고 둔다면 같은 행 안에서 가장 첫 열과 가장 끝 열을 제외하고 중간에 있는 요소들은 겹친다. 즉 중복해서 더해진다. 예를 들면 0번째 행, 1번째 행은 중간에 있는 요소가 없기 때문에 안 겹치지만 2번째 행부터는 가장 첫 열인 8과 가장 끝 열인 0을 제외하고 중간에 있는 1은 그 전 행의 3과도 더해질 수 있고 8과도 더해질 수 있다. 지금 문제는 이 중에서 최댓값을 구하라고 했기 때문에 중복해서 더해지는 요소는 두 가지 경우 중 최댓값만 저장하면 된다. 이를 그림으로 표현하면 다음과 같다. 내가 작성한 코드 (자바스크립트) let fs = require("fs"); let input = fs.read..
2021.07.05 -
[백준] 1655. 가운데를 말해요 (자바스크립트/javascript/node.js/힙정렬/우선순위 큐)
문제를 풀기 위한 아이디어 힙을 이용해서 중간값을 구하는 문제이다. 이전에 블로그 포스팅으로 했었던 힙으로 중앙값찾기를 잘 연습했던 터라 이 문제는 빠르게 잘 풀 수 있었다. 다만 연습했었을 때에는 최소힙과 최대힙의 크기가 같을 때 최소힙에서 가장 작은 값, 최대힙에서 가장 큰 값을 더해서 2로 나눈 값이 중앙값이 되었다면 이번 문제에서는 둘 중 최솟값을 중앙값으로 지정하여야 한다. 이는 자바스크립트의 Math.min 메소드를 통해 쉽게 구현했다. (제 블로그를 검색을 통해 들어온 분들은 아래의 게시글에 설명이 되어있으니 참고하시면 됩니다.) https://nyang-in.tistory.com/155 [자바스크립트 자료구조] 힙(heap) - 연습문제 일련의 숫자에서 중앙값 찾기 중앙값이란 어떤 배열을 ..
2021.07.02 -
[프로그래머스] N으로 표현 (자바스크립트/javascript/js/동적계획법/동적프로그래밍/다이나믹프로그래밍)
문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 문제를 풀기 위한 아이디어 이 문제는 N을 1번 쓰는 경우, N을 2번 쓰는 경우 , .... , N을 8번 쓰는 경우까지 따져보아야 한다. 문제에서 N이 8보다 크다면 -1을 출력하라고 했으므로 N을 8번 쓰는 경우까지 구해보고 나오지 않는다면 -1을 출력하면 된다. use라는 9 크기의 배열을 만든다. (9인 이유는 N을 8번 쓰는 경우까지 구할 것인데 배열의 인덱스가 0에서 시작함을 감안하여 더 직관적으로 생각하기 위해서 N을 1번 쓰는 경우를 use[1]에 저장하고, N을 2번 쓰는 경우를 use[2]에 저장하고, ....
2021.07.02 -
[백준] 1149. RGB거리 (자바스크립트/javascript/js/node.js/동적 프로그래밍/다이나믹 프로그래밍 / 동적계획법)
문제를 풀기 위한 아이디어 규칙이 복잡해보이지만 숫자를 대입하여 생각해보면 결국 바로 인접한 집끼리만 다른 색이면 된다는 것이다. 일단 주어진 각 집을 빨강,초록,빨강으로 칠하는 비용들을 2차원 배열에 저장한다. input = [ [26, 40, 83], [49, 60, 57], [13, 89, 99] ] 그 다음으로는 첫번째집을 R로 칠한 경우 / 첫번째 집을 G로 칠한 경우 / 첫번째 집을 B로 칠한 경우를 모두 다 따져주면 된다. 이를 점화식으로 세우면, 두번째 집부터는 다음과 같은 점화식이 성립한다. input[i][0] = min(input[i-1][1], input[i-1][2]) + input[i][0] input[i][1] = min(input[i-1][0], input[i-1][2]) +..
2021.07.02 -
[백준] 9461. 파도반 수열 (자바스크립트/javascript/js/node.js/동적계획법/다이나믹 프로그래밍/동적 프로그래밍)
문제를 풀기 위한 아이디어 동적 프로그래밍 유형이 다들 그러듯이 점화식만 잘 세우면 된다. 점화식은 다른 분들의 코드를 보니까 여러 점화식이 나올 수 있는데 나는 그림을 보고 바로 유추할 수 있는 점화식을 사용했다. P(1) = 1 P(2) = 1 P(3) = 1 P(4) = 2 P(5) = 2 P(6) = 3 P(7) = 4 P(8) = 5 까지는 값을 미리 넣어놓고, P(9)부터는 P(N) = P(N-5) + P(N-1)을 사용했다. 사실 P(1)~P(3)까지만 넣어놓고 P(4)부터 P(N) = P(N-2) + P(N-3)을 쓰는 것이 더 좋은 방법인 것 같긴 하다. 하지만 나는 그림을 보고 예를 들어 P(9) = P(4) + P(8)의 합이라고 딱 그림에서 보기 쉬웠기 때문에 이렇게 점화식을 세웠다..
2021.07.01