문제를 풀기 위한 아이디어 이 문제는 한마디로 순열을 구하는 것이다. 이전에 내가 포스팅했던 순열 알고리즘을 써도 되지만, 이 문제는 백트래킹 알고리즘 유형에 있던 문제이기 때문에 한번 백트래킹으로 풀어보았다. * 백트래킹 이란 ? 모든 조합의 수를 다 살펴보되 (완전탐색) 단 조건이 만족할 때에만 탐색하는 방법을 말한다. 쉽게 말해 해를 찾는 도중 해가 아닌 것 같으면 되돌아가서 해를 찾는 것이다. 완전탐색을 하는 방법으로는 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은 아무래도 좋은 방법이 아닌 ..

네이버 부스트캠프 6기 웹·모바일에 최종합격했다. ✨🎉 맨날 블로그에는 공부하는 게시글만 올렸었지 나의 이야기를 적는 것은 어색하기도 하고 원래 성격도 내 이야기를 잘 안하는 성격이라 이런 게시글은 처음인 것 같다. 사실 1차, 2차 코딩테스트 후기를 남기는 분들도 많지만, 나는 뭔가 내 성격상 후기를 남겼다가 합격하지 못하면 뭔가 씁쓸할 것 같아서 올리더라도 최종합격까지 하고 올리고 싶다는 생각에 올리지 않았었다. 1차 코딩테스트(객관식 모름 & 1솔) 지난 달에 네이버 부스트캠프 웹·모바일 과정 6기 모집글을 보고 지원했고 서류를 작성했다. 모든 지원자가 1차 코딩테스트를 볼 기회가 주어졌으며, 1차 코딩테스트는 6월 24일 목요일에 보았다. 지난기수 시험친 분들의 후기를 보았을 때 난이도가 그렇게 ..

문제를 풀기 위한 아이디어 동적 프로그래밍의 대표적인 유형 중 하나인 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개밖에 되지 않기 때문에 브루트포스(완전탐색)로 구하더라도 짧은 시간내에 금방 구할 수 있으나 물건의 개수가 조금만 늘어나더라도 따져보아야할 경우의 수는 기하급수적으로 늘어나기 때문에 ..