Algorithm/Baekjoon

Algorithm/Baekjoon

물건을 쪼갤 수 없는 배낭 문제(0/1 Knapsack Problem)

0/1 Knapsack Problem다이나믹 프로그래밍(Dynamic Programming : DP)을 활용하여 해결할 수 있다..DP는 큰 문제를 작은 문제로 쪼개서 해결한다.DP는 Devide-and-Conquer라는 원리에 기반을 두고 있으며, 이전에 계산해둔 값을 메모리(배열 등)에 저장해서 반복 작업을 줄이는 기법(Memoization)이 핵심이다.  예시가방에 담을 수 있는 물건의 무게와 가치가 아래의 표와 같이 있다고 가정하자.물건1234무게6435가치138612  ① 2차원 배열을 만드는데, 이 때, (i + 1)(j + 1) 크기의 배열을 만들고 0으로 초기화한다. 이 때, 행 i는 물건 i(0 ~ 4)까지 넣을 수 있을 때를 의미하고, 열 j(0 ~ 7)는 가방의 최대 무게를 의미한다...

Algorithm/Baekjoon

백준 12865번 - 평범한 배낭(Node.js)

백준 12865번 - 평범한 배낭(Node.js)https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)www.acmicpc.net   첫 번째 나의 풀이제출시 결과는 틀렸습니다.간단하게 이 코드에 대해 설명하자면, 이중 for문을 사용하여 모든 가치 or 가치의 합의 최댓값의 경우의 수를 worthArr이라는 배열에 넣어주고, worthArr의 값 중 최댓값을 답으로 설정하여 풀었다.하지만, 이 방법에는 생각해보니 ..

Algorithm/Baekjoon

백준 2357번 - 최솟값과 최댓값(Node.js)

백준 2357번 - 최솟값과 최댓값(Node.js)https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100www.acmicpc.net   첫 번째 나의 풀이제출시 런타임에러(TypeError) 발생TypeError가 발생하여 Type을 계속해서 바꿔주었지만, 끝내 이 방법으로는 해결하지 못했다. + 입력을 이런 방법으로 받는건지도 아직 잘 모르겠다. (거의 2일 동안 fs 모듈 사용해서 입력 받는 방법을 공부했음에도 ..)  두 번째 나의 풀이제..

Algorithm/Baekjoon

백준 1676번 - 팩토리얼 0의 개수(Node.js)

백준 1676번 - 팩토리얼 0의 개수(Node.js)https://www.acmicpc.net/problem/1676   첫 번째 나의 풀이처음 내가 이 문제를 보고 생각한 것을 위의 코드를 보고 설명할 것이다.9 ~ 11번째 줄은 입력된 N에 따라 N!을 계산하는 코드이다.13번째 줄은 구한 N!의 값을 split() 메서드를 이용하여 하나씩 잘라주고 그 값을 answer에 넣어주었다. *split()메서드를 이용하기 위해서 문자열로 만드는 작업이 필요하기 때문에 String()을 사용하여 문자열로 만드는 작업을 해주었다.15 ~ 21번째 줄은 위의 split() 메서드를 이용하여 자른 결과의 배열인 answer를 뒤에서부터 반복문을 사용하여 "0"이 나오면 count를 1씩 더해주고, "0"이 아닌..