본문 바로가기

Algorithm/인프런(inflearn)86

[ 강의 후기 ] 자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 김태원 (내돈내산) 📍 [ 강의 후기 ] 자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 김태원 ✏️ 서론 학부시절 JAVA를 잠깐 배웠지만 클래스가 뭐고 인스턴스가 뭔지 수업을 들어도 전혀 감을 잡지 못해 손에서 놔버렸다. 대학교 졸업 후 2년 4개월의 군 복무를 마치고 나서 5개월 뒤인 20. 12. 22부터 취업을 하겠다는 다짐과 함께 프로그래밍 관련 기억이 모두 삭제된 채 코딩 테스트를 준비했다. 그로부터 3~4개월이 지났을 때 프론트엔드로 가려면 코딩 테스트의 언어로는 python 보다 이제부터 평생 달고 살아야 할 javascript로 해야겠다는 마음을 먹었다. python으로 공부를 하면서 2~3개 정도 스타트업의 코딩 테스트를 치렀는데 모두 python은 지원이 되지 않고 JS로만 응시가 가능했다. JS로.. 2021. 10. 15.
[ 자바스크립트(JavaScript) ] section10 - 5 - 최대 점수 구하기(냅색 알고리즘) 📍 section10 - 5 - 최대 점수 구하기(냅색 알고리즘) 문제: 선생님이 내주신 N 개의 문제를 풀려고 한다. 각 문제는 그것을 풀 때 얻는 점수와 푸는데 걸리는 시간이 주어진다. 제한시간 M 안에 N 개의 문제 중 최대 점수를 얻을 수 있도록 해야 한다. (해당 문제는 해당 시간이 걸리면 푸는 걸로 간주한다. 한 유형당 한 개만 풀 수 있다.) 첫 번째 줄에 문제의 개수 N과 제한 시간 M이 주어지고 두번째 줄부터 N줄에 걸쳐 문제를 풀 때 얻는 점수와 문제를 풀 때 걸리는 시간이 주어집니다. // 입력 5 20 10 5 25 12 15 8 6 3 7 4 // 출력 41 이전에 동일한 문제를 부분집합 + edgeCut으로 문제를 풀었다. 하지만, 만약에 문제의 개수가 100개 이상이거나 혹은 .. 2021. 10. 14.
[ 자바스크립트(JavaScript) ] section10 - 4 - 동전 교환(냅색 알고리즘) 📍 section10 - 4 - 동전 교환(냅색 알고리즘) 문제: 다음과 같이 여러 단위의 동전들이 주어져 있을 때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다. // 입력 3 1 2 5 15 // 출력 // (5, 5, 5) 동전 3개로 거슬러 줄 수 있다. 3 동전교환 문제는 저번에 dfs(부분집합) + edgeCut을 이용해서 푼 적이 있다. 만약에 동전의 종류가 100개 이상, 거스름 돈이 100,000 이상일 경우 DFS로 풀 수 없다. 이럴 때는 DP에서 냅색 알고리즘으로 풀어야 한다. dp는 거슬러줄 돈(m)만큼 배열의 크기를 선언하고 최소 동전의 개수를 구해야 하므로 개수를 제일 많이 거슬러주는 개수보다 큰 값으로 설정한다.(문.. 2021. 10. 14.
[ 자바스크립트(JavaScript) ] section10 - 3 - 최장 부분 증가수열(LIS) 📍 section10 - 3 - 최대 부분 증가수열(LIS) 문제: N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내고 길이가 5인 최대부분증가수열을 만들 수 있다. 이 문제는 LIS 문제인데, 저번에 현대카드 코딩테스트에서 LIS를 사용하는 문제가 나왔었다. (물론 그때는 몰라서 못 풀었다. 🥲 ) 이번기회에 배우고 다음에 LIS 문제가 나오면 말끔하게 풀어버리자. LIS문제도 마찬가지로 DP를 사용하는데, DP의 특징 중 하나인 각 단계별로 쪼갠 다음, 이.. 2021. 10. 14.
[ 자바스크립트(JavaScript) ] section10 - 2 - 돌다리 건너기 📍 section10 - 2 - 돌다리 건너기 문제: 철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다. 철수는 돌다리를 건널 때 한 번에 한 칸 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다. 철수가 개울을 건너는 방법은 몇 가지일까요?? 이전에 풀었던 계단 오르기 문제와 매우 흡사하다. 하지만 잘 생각해보면, dp[n]을 구하는 것이 아니라 dp[n+1]을 구하는 문제이다. 왜냐하면 개울을 건너기 위해서는 마지막 돌에 서있으면 안되고(dp[n]), 마지막 돌에서 한 칸 앞으로 전진해야 하기 때문(dp[n+1])이다. let n = 7; console.log(solution(n)); function solution(n){ let dp = Array.from({leng.. 2021. 10. 13.

티스토리툴바