문제를 풀기 위한 아이디어 이 문제는 한마디로 순열을 구하는 것이다. 이전에 내가 포스팅했던 순열 알고리즘을 써도 되지만, 이 문제는 백트래킹 알고리즘 유형에 있던 문제이기 때문에 한번 백트래킹으로 풀어보았다. * 백트래킹 이란 ? 모든 조합의 수를 다 살펴보되 (완전탐색) 단 조건이 만족할 때에만 탐색하는 방법을 말한다. 쉽게 말해 해를 찾는 도중 해가 아닌 것 같으면 되돌아가서 해를 찾는 것이다. 완전탐색을 하는 방법으로는 DFS, BFS가 있다. 백트래킹은 DFS에서 효율적인 방법이다. 왜냐하면 DFS는 깊이 우선 탐색이므로 갈 수 있는 최대 깊이까지 갔다가 돌아온다. 우리는 끝까지 탐색하지 않아도 중간에 조건에 부합하지 않는 경우가 있어서 현재 경로가 잘못된 것임을 알 수 있는 경우가 종종 있다...

문제를 풀기 위한 아이디어 문제가 장황하지만, 결국 생각해야할 포인트는 단순하다. 가장 최저가인 곳에서 기름을 구매해서 제일 오른쪽 도시(도착점)까지 가면 되는데, 그 최저가인 지점까지 도착하기 전까지는 그 전에 있는 곳 중 최저가에서 구매를 해야 한다. 이게 계속 반복된다. 생각을 조금 전환시키면, 매 순간 순간마다 최저가를 갱신시키면 된다. 현재 최저가가 지금 머무르고 있는 곳의 가격보다 비싸다면 최저가가 갱신되는 것이다. 그렇게 해서 최저가와 갈 거리를 곱해서 총 비용에 누적시키면 된다. 내가 작성한 코드 (자바스크립트) let fs = require("fs"); let input = fs.readFileSync("예제.txt").toString().split("\n"); let cost = Big..

문제를 풀기 위한 아이디어 어려운 문제는 아니다. 그러나 제출했을 때 오류가 나서 다른 방법을 찾느라 좀 번거로웠던 문제이다. 일단 근본적으로 문제를 해결하는 방법은, 최솟값이 나오기 위해서는 마이너스를 최대한 크게 해서 빼는 것이 최솟값이 되기 때문에, 마이너스가 나타나면 마이너스 뒤에서 괄호 "("로 묶기 시작하여 또 다른 마이너스를 만나기 직전에 ")"를 추가하는 방법이다. 예제의 경우 55-50+40 이라면 55-(50+40) 이렇게 하는 것이다. 그렇게 하여 주어진 식을 배열로 다 나누어서 마이너스가 나타나면 "-("로 바꾸고 이런식으로 푼 다음에 마지막에 문자열로 합치고 eval을 이용해서 식을 계산했는데 처음에 런타임에러(SyntaxError)가 나와서 eval은 아무래도 좋은 방법이 아닌 ..

문제를 풀기 위한 아이디어 동적 프로그래밍의 대표적인 유형 중 하나인 0/1 배낭 문제이다. (배낭문제에 대한 포스트는 지난 게시글에 올렸으니 참고하실 분들은 참고하시면 됩니다.) 내가 작성한 코드 (자바스크립트) let fs = require("fs"); let knapsack = fs.readFileSync("예제.txt").toString().split("\n"); const N = Number(knapsack[0].split(" ")[0]); const K = Number(knapsack[0].split(" ")[1]); knapsack = knapsack.map((element) => element .trim() .split(" ") .map((value) => Number(value)) ); ..

오늘은 동적 프로그래밍 문제 중 대표적인 유형인 0/1 배낭 문제에 대해 알아보겠습니다. 물건의 개수 N이 주어지고, 배낭이 최대로 버틸 수 있는 무게 K가 주어지고 각 물건의 무게와 가치가 주어질 때 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구하는 문제입니다. 문제가 0/1 배낭 문제라고 불리는 이유는 물건을 쪼개서 넣을 순 없고 물건을 넣거나/안넣거나 둘 중 하나의 선택만 할 수 있기 때문입니다. 예를 들어 물건의 개수가 4개, 배낭의 무게는 7이고 각 물건의 무게와 가치가 다음과 같다고 합시다. 물건의 개수가 4개밖에 되지 않기 때문에 브루트포스(완전탐색)로 구하더라도 짧은 시간내에 금방 구할 수 있으나 물건의 개수가 조금만 늘어나더라도 따져보아야할 경우의 수는 기하급수적으로 늘어나기 때문에 ..

문제를 풀기 위한 아이디어 1. 직전까지의 부분합 + 현재 가리키고 있는 수 2. 현재 가리키고 있는 수 를 비교하여 더 큰 값을 부분합으로 저장한다. 즉, 지금까지 연속해서 더한 부분합+현재 가리키고 있는 수와 그냥 현재 가리키고 있는 수를 비교했는데 현재 가리키고 있는 수가 더 크다면 미련없이 이전 수들을 버리고 새롭게 시작하여도 OK라는 것이다. 예제 1을 가지고 예를 들어보면, [10, -4, 3, 1, 5, 6, -35, 12, 21, -1]에서 dp[7]까지는 쭉 더하다가 8번째 수인 12를 만났을 때 -14 + 12 vs 12를 비교해서 12가 더 크기 때문에 이전 값을 다 버리고 12부터 시작하는 것이다. 그렇게 해서 구한 모든 dp 값 중 최댓값을 출력하면 된다. 내가 구현한 코드 (자바..