Algorithm

[ 프로그래머스 ] 당구 연습 - JavaScript

https://school.programmers.co.kr/learn/courses/30/lessons/169198 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 프로그래머스의 마스코트인 머쓱이는 최근 취미로 당구를 치기 시작했습니다. 머쓱이는 손 대신 날개를 사용해야 해서 당구를 잘 못 칩니다. 하지만 끈기가 강한 머쓱이는 열심히 노력해서 당구를 잘 치려고 당구 학원에 다니고 있습니다. 오늘도 당구 학원에 나온 머쓱이에게 당구 선생님이"원쿠션"(당구에서 공을 쳐서 벽에 맞히는 걸 쿠션이라고 부르고, 벽에 한 번 맞힌 후 공에 맞히면 원쿠션이라..

[ 프로그래머스 ] 야근 지수 - JavaScript

https://school.programmers.co.kr/learn/courses/30/lessons/12927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다. Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리..

유클리드 호제법 (Euclidean algorithm)

2개의 자연수의 최대공약수를 구하는 알고리즘 1. 두 개의 자연수 a와 b ( a > b )가 주어진다. 2. a를 b로 나눈 나머지 r을 구한다. 3. r을 비교해본다. 3-1. r이 0이라면, 최대공약수는 b이다. 3-2. r이 0이 아니라면, a = b / b = r로 변경하여 2번으로 돌아간다. EX ) a = 24 / b = 18 r = 24 % 18 = 6이므로, a = 18 / b = 6이 된다. ( 2 > 3-2 ) r = 18 % 6 = 0이므로, 최대공약수는 b인 6이 된다. ( 2 > 3-1 ) EX ) a = 1071 / b = 1029 r = 1071 % 1029 = 42이므로, a = 1029 / b = 42가 된다. ( 2 > 3-2 ) r = 1029 % 42 = 21이므로,..

가장 긴 증가하는 부분 수열 (LIS problem)

Longest Increasing Subsequence 길이가 1이상인 수열이 주어질 때, 가장 길고, 증가하는 부분 수열의 길이를 찾는 문제 다이나믹 프로그래밍(DP, Dynamic Programming)을 사용해야 한다. 1. 시간 복잡도가 N^2인 알고리즘 A = { 10, 20, 30, 10, 20, 50 } DP에 넣어야 하는 정보는 A[ i ]로 끝나는 가장 긴 증가하는 부분 수열의 길이이다. 1 ) 인덱스 1은 무조건 1의 길이를 갖는다. index 0 1 2 3 4 5 6 A 0 10 20 30 10 20 50 DP 0 1 2 ) 두 번째 부터는 A[ 0 ]부터 A[ i - 1 ]중에 A[ i ]보다 작은 값을 찾고, 해당 인덱스의 DP가 가장 큰 값을 찾는다. 그리고 해당 DP의 값에 1..

최장 공통 부분 수열 (LCS problme)

Long Common Subsequence 한 개 이상의 문자열이 주어질 때, 중간에 다른 문자가 들어가더라도 공통되면서 가장 긴 부분 문자열을 찾는 문제 다이나믹 프로그래밍(DP, Dynamic Programming)을 사용해야 한다. EX ) A와 B 두 개의 문자열이 주어진다. => A = 'ACAYKP' / B = 'CAPCAK' 1 ) ( 문자열의 길이 + 1 ) 만큼 2차원 배열을 생성한다. 단, 인덱스가 0인 부분은 0으로 채워넣는다. - A C A Y K P - 0 0 0 0 0 0 0 C 0 A 0 P 0 C 0 A 0 K 0 2) 한 글자씩 비교한다. - A C A Y K P - 0 0 0 0 0 0 0 C 0 0 A 0 P 0 C 0 A 0 K 0 - 글자가 같지 않다면, 위의 값과 ..

배낭 문제 (Knapsack Problem)

배낭에 담을 수 있는 무게의 최대값이 정해져 있고, 가치와 무게가 정해져 있는 짐을 배낭에 담을 때, 가치의 합이 최대가 되도록하는 짐의 조합을 찾는 문제 1. 물건을 쪼갤 수 없어서 무게와 가치가 무조건 정수형태를 가지는 유형 다이나믹 프로그래밍(DP, Dynamic Programming)을 사용해야 한다. EX ) 최대 무게는 7이고, 각 물건의 무게와 가치는 다음과 같다. => [6, 13], [4, 8], [3, 6], [5, 12] 1) 가로는 가방의 최대 무게 / 세로는 가방에 들어간 물건의 개수이다. j / i 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 2 3 4 2) [6, 13] 물건을 집어 넣는다. 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 0..