상권's
TIL 33 (순열/조합, GCD / LCM, 정규표현식) (2021.11.10) 본문
-오늘의 코플릿 2021.11.10-
2차원 M x N 배열을 나선형(spiral)으로 순회해야 합니다.
입력
인자 1 : matrix
세로 길이(matrix.length)가 M, 가로 길이(matrix[i].length)가 N인 2차원 배열matrix[i]는 string 타입을 요소로 갖는 배열matrix[i][j].length는 1
출력
string 타입을 리턴해야 합니다.
주의사항
순회는 좌측 상단 (0,0)에서 시작합니다.배열의 모든 요소를 순서대로 이어붙인 문자열을 리턴해야 합니다.
오늘 문제는 수도 코드 작성도 어려웠습니다. 스택이나 큐, 길이만큼 먼저 움직이는 방향에 대해서 하드코딩 해놓고 코드를 구현해볼까도 했지만 쉽지 않았습니다. 구글링을 통해서 외곽을 먼저 돌게 되면, 내부에는 외곽이랑 동일한 모양의 matrix가 생기고, 이 부분도 재귀로 처리를 하면 된다는 것을 알게 되었습니다. 맨 윗 줄에서는 해당 배열의 끝까지 순회를 하지만, 오른쪽, 아래쪽을 순회할 때는, 전부를 도는 것이 아니라 하나씩 빼고 순회를 하게 된다면, 쉽게 구현할 수 있다는 것을 파악했습니다. 구글링한 자료를 토대로 구현을 해보았습니다. 출처
const spiralTraversal = function (matrix) {
// TODO: 여기에 코드를 작성합니다.
let result = '';
return cycle(matrix, result)
};
const cycle = function(matrix, result) {
if(matrix.length === 0) {
return result;
}
let x = matrix[0].length;
let y = matrix.length;
if ( y === 1) {
for( let n = 0; n < x; n++ ) {
result += matrix[0][n]
}
}
if ( y > 1 ) {
for (let n = 1; n < 5; n++ ) {
if( n === 1) {
for ( let j = 0; j < x; j++ ) {
result += matrix[0][j]
}
}
if ( n === 2) {
for (let j = 1; j < y - 1; j++ ) {
result += matrix[j][x - 1]
}
}
if ( n === 3 ) {
for ( let j = x - 1; j > 0; j-- ) {
result += matrix[y - 1][j]
}
}
if ( n === 4 ) {
for ( let j = y - 1; j > 0; j-- ) {
result += matrix[j][0]
}
}
}
}
let copied = [];
for ( let i = 1; i < y - 1; i++ ) {
copied.push(matrix[i].slice(1, -1))
}
return cycle(copied, result)
}Algorithm with Math - 순열 / 조합
문제: 카드 뽑기
[A, B, C, D, E]로 이뤄진 5장의 카드가 있습니다. 이 5장의 카드 중 3장을 선택하여 나열하려고 합니다. 이때, 다음의 조건을 각각 만족하는 경우를 찾아야 합니다.
- 순서를 생각하며 3장을 선택합니다.
- 순서를 생각하지 않고 선택합니다.
조건 1을 만족하는 모든 경우의 수
1번 조건에서 모든 경우의 수를 구할 때에는 모든 카드를 1장씩 나열하면서 나열된 카드가 3장에 도달하면 카드의 나열을 중지합니다.
1번의 조건을 만족하려면, 다음과 같은 방법으로 경우의 수를 구합니다.
- 첫번째 나열하는 카드를 선택하는 방법에는 다섯 가지가 있습니다.
- 첫번째 카드를 나열하고 난 다음, 두번째 카드를 선택하는 방법에는 네 가지가 있습니다.
- 두번째 카드를 나열하고 난 다음, 세번째 카드를 선택하는 방법에는 세 가지가 있습니다.
따라서 5 X 4 X 3 = 60 가지의 방법이 있습니다.
n 개 중에서 일부만을 선택하여 나열하는 것을 순열이라고 합니다. 순열은 순서를 지키며 나열해야 합니다. 예를 들어 카드를 3장 뽑을 때, [A, B, D]와 [A, D, B] 두 경우 모두 A, B, 그리고 D라는 같은 카드를 3장 선택했지만, 나열하는 순서가 다르므로 서로 다른 경우로 파악해야 합니다.
순열은 일반화 과정을 거쳐, Permutation의 약자 P로 표현합니다.
- 5장에서 3장을 선택하는 모든 순열의 수 = 5P3 = (5 X 4 X 3 X 2 X 1) / (2 X 1) = 60
조건 2를 만족하는 모든 경우의 수
2번 조건에서 모든 경우의 수를 구할 때는 3장을 하나의 그룹으로 선택해야 합니다. 2번의 조건을 만족하려면, 다음과 같은 방법으로 경우의 수를 구합니다.
- 순열로 구할 수 있는 경우를 찾습니다.
- 순열로 구할 수 있는 경우에서 중복된 경우의 수를 나눕니다.
먼저, 조합은 순열과 달리 순서를 고려하지 않습니다. 만약 순열처럼 순서를 생각하여 경우의 수를 센다면, 조합으로써 올바르지 않을 겁니다. 예를 들어 순열에서는 [A, B, C], [A, C, B], [B, A, C], [B, C, A], [C, A, B], [C, B, A]의 여섯 가지는 모두 다른 경우로 취급하지만, 조합에서는 이 여섯 가지를 하나의 경우로 취급합니다. 다시 말해 순열에서처럼 순서를 생각하여 선택하면, 중복된 경우가 6배 발생합니다.
조합은 일반화 과정을 거쳐, Combination의 약자 C로 표현합니다.
- 5장에서 3장을 무작위로 선택하는 조합에서 모든 경우의 수 = 5C3 = 5! / (3! * 2!) = 10
Algorithm with Math - GCD / LCM
최대 공약수(GCD. Greatest Common Divisor): 둘 이상의 공약수 중에서 최대인 수
문제: 조명 설치
코드스테이츠 라운지에 있는 가로 24cm, 세로 12cm인 직사각형 모양 조형물의 가장자리에 조명을 설치하려고 합니다. 네 모퉁이에는 조명을 반드시 설치해야하고, 나머지 조명은 일정한 간격으로 설치하려고 할 때, 필요한 최소한의 조명 개수는 몇 개일까요? 이때, 꼭지점을 제외한 직사각형의 모든 변에는 최소 하나 이상의 조명이 반드시 설치되어야 합니다. (단, 설치한 조명의 간격은 정수로 이루어진 cm 단위입니다.)
이 문제에서 필요한 전구의 개수를 구하려고 할 때, 최대 공약수를 떠올리면 빠르게 문제를 해결할 수 있습니다.
가로와 세로 각각 나누어서 나머지가 없이 떨어지는 수들을 나열한 뒤, 공통된 수만 모으면 공약수를 구할 수 있습니다. 그리고 공약수를 기준으로 조명을 설치하면, 길이가 다른 가로와 세로여도 일정한 간격으로 나누어 조명을 설치할 수 있습니다.
최소로 필요한 조명의 개수를 파악해야 하기 때문에 최대 공약수가 필요합니다. 따라서 GCD(12, 24)는 12이고 네 모퉁이는 반드시 설치해야 하므로 각 변의 길이를 최대 공약수 12로 나누어 최소로 필요한 조명의 개수를 구할 수 있습니다. (GCD; Greatest Common Divisor, 최대 공약수)
(12/12 + 24/12) X 2 = 3 X 2 = 6개
그러나 이 문제에서는 꼭지점을 제외한 직사각형의 모든 변에, 최소 하나 이상의 조명이 설치되어야 하므로 12를 제외한 최대 공약수로 문제를 해결해야 합니다.
(12/6 + 24/6) X 2 = 6 X 2 = 12개
최대공약수를 구하는 방법으로는 유클리드 호제법이 있습니다.
유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다.
출처 위키백과
2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 《원론》 제7권, 명제 1부터 3까지에 해당한다.
아래와 같이 코드로 구현할 수 있습니다.
const getGCD = (a, b) => {
if (b === 0) return a;
// 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
return gcd(b, a % b);
};최소 공배수(LCM. Least Common Multiple): 둘 이상의 공배수 중에서 최소인 수
문제: Mask States
방역용 마스크를 제작/판매하는 Mask States 사는 이례적인 전염성 독감 예방을 위해 기존 가격을 유지하며 약속된 물량의 방역용 마스크를 제공하고 있습니다. 이 회사는 사장을 포함하여 A, B, C 세 명뿐이고, 이들 모두 마스크를 제작합니다. 각각의 제작 속도는 다음과 같습니다. A는 55분마다 9개를, B는 70분마다 15개를, C는 85분마다 25개의 방역용 마스크를 만들 수 있습니다. 이 회사의 사람들은 05:00 시부터 동시에 마스크를 만들기 시작하여 각 55분, 70분, 85분 동안 연속으로 마스크를 제작한 후, 5분씩 휴식을 취합니다. 이들 세 명이 처음으로 동시에 쉬는 시점이 퇴근 시간이라면, 이날 하루에 제작한 마스크는 모두 몇 개인가요? (휴식시간과 퇴근시간이 겹치는 경우, 휴식을 취한 뒤 퇴근합니다.)
A, B, C의 작업 시간과 쉬는 시간 5분을 더하면 A, B, C는 각각 60분, 75분, 90분마다 마스크를 만듭니다.
세 명이 동시에 휴식을 취하는 시점은 세 명이 쉬고 난 직후가 같을 시점이 됩니다. 따라서 쉬고 난 직후가 처음으로 같을 시점을 구해야 하므로 공배수와 최소 공배수의 개념을 알아야 합니다.
결과적으로, LCM(60, 75, 90)은 900입니다. (LCM; Least Common Multiple, 최소 공배수)
따라서 A는 B, C와 휴식을 취한 직후가 처음으로 같을 시점까지 900/60 = 15 번 작업하고, 15번 X 9개 = 135개의 마스크를 만들어 냅니다.
B는 900/75 = 12번의 작업을 반복하고 12턴 X 15개 = 180개,
C는 900/90 = 10번의 작업을 반복하고 10턴 X 25개 = 250개의 마스크를 만들어 냅니다.
따라서, A, B, C가 하루에 제작한 마스크의 총 개수는 135개 + 180개 + 250개 = 565개가 됩니다.
최소공배수는 A와 B라는 두 개의 수가 주어졌을 때, A와 B를 곱한 수를 최대공약수로 나누면 구할 수 있습니다.
이 두가지를 한꺼번에 구하는 코드를 구현한다면 아래와 같습니다.
const getGCDandLCM = (n, m) => {
const getGCD = (a, b) => {
if (b === 0) return a;
return gcd(b, a % b);
};
const getLCM = (a, b) => (a * b) / gcd(a, b);
// 두 수를 곱한 수를 최대공약수로 나누면 최소공배수가 된다.
);
// 최대공약수는 GCD(m. n)
// 최소공배수는 LCM(m, n)
};정규표현식
정규표현식을 한 문장으로 정의하면 문자열에서 특정한 문자를 찾아내는 도구입니다.
정규표현식은 특정한 규칙을 갖는 문자열로 이루어진 표현식이며, 정규표현식에서 특수 문자는 각각의 고유한 규칙을 갖고 있습니다. 우리는 이러한 규칙들을 조합하여 원하는 패턴을 만들고, 특정 문자열에서 해당 패턴과 대응하는 문자를 찾을 수 있습니다.
사용자가 입력한 이메일이나 휴대전화 번호가 유효한지 확인하고자 할 때 사용하는 정규표현식입니다.
이메일 유효성 검사
let regExp = /^[0-9a-zA-Z]([-_.]?[0-9a-zA-Z])*@[0-9a-zA-Z]([-_.]?[0-9a-zA-Z])*.[a-zA-Z]{2,3}$/i;휴대전화 번호 유효성 검사
let regExp = /^01([0|1|6|7|8|9]?)-?([0-9]{3,4})-?([0-9]{4})$/;정규표현식 사용하기
정규표현식은 두 가지 방법으로 사용할 수 있습니다.
리터럴 패턴
정규표현식 규칙을 슬래시(/)로 감싸 사용합니다. 슬래시 안에 들어온 문자열이 찾고자 하는 문자열입니다.
let pattern = /c/;
// 'c 를 찾을 거야!' 라고 컴퓨터에게 명령을 내리는 것입니다.
// 찾고 싶은 c를 pattern 이라는 변수에 담아놨기 때문에 이 변수를 이용하여 c 를 찾을 수 있습니다.생성자 함수 호출 패턴
RegExp 객체의 생성자 함수를 호출하여 사용합니다.
let pattern = new RegExp('c');
// new 를 이용해서 정규 표현식 객체를 생성하고,
// 리터럴 패턴과 동일하게 'c 를 찾을 거야!' 라는 명령입니다.정규표현식 내장 메소드
JavaScript 에서 정규표현식은 객체로서 내장 메소드를 가지고 있으며, String 객체에서도 정규표현식을 사용할 수 있는 내장메소드를 가지고 있습니다.
내장 메소드를 이용하면 어떤 문자열 안에 원하는 정보를 찾거나 특정 패턴에 대응하는 문자열을 검색, 추출, 다른 문자열로 치환할 수 있습니다.
RegExp 객체의 메소드
exec() exec 는 execution 의 줄임말로, 원하는 정보를 뽑아내고자 할 때 사용합니다. 검색의 대상이 찾고자 하는 문자열에 대한 정보를 가지고 있다면 이를 배열로 반환하며, 찾는 문자열이 없다면 null을 반환합니다.
let pattern = /c/;
// 찾고자 하는 문자열
pattern.exec('codestates')
// 검색하려는 대상을 exec 메소드의 첫 번째 인자로 전달합니다.
// 즉, 'codestates' 가 'c' 를 포함하고 있는지를 확인합니다.
// 이 경우 'c' 가 포함되어 있으므로, ['c'] 를 반환합니다.test() 찾고자 하는 문자열이 대상 안에 있는지의 여부를 boolean 으로 리턴합니다.
let pattern = /c/;
pattern.test('codestates');
// 이 경우는 'codestates'가 'c'를 포함하고 있으므로 true 를 리턴합니다.String 객체의 메소드
match() RegExp.exec() 와 비슷한 기능을 하며, 정규 표현식을 인자로 받아 주어진 문자열과 일치된 결과를 배열로 반환합니다. 일치되는 결과가 없으면 null 을 리턴합니다.
let pattern = /c/;
let str = 'codestates';
str.match(pattern);
// str 안에 pattern 이 포함되어 있으므로, ['c'] 를 반환합니다.replace() '검색 후 바꾸기'를 수행합니다. 첫 번째 인자로는 정규표현식을 받고, 두 번째 인자로는 치환하려는 문자열을 받습니다. 문자열에서 찾고자 하는 대상을 검색해서 이를 치환하려는 문자열로 변경 후 변경된 값을 리턴합니다.
let pattern = /c/;
let str = 'codestates';
str.replace(pattern, 'C');
// str 안에서 pattern 을 검색한 후 'C' 로 변경하여 그 결과를 리턴합니다.
// 여기서는 'Codestates'가 반환됩니다.split() 주어진 인자를 구분자로 삼아, 문자열을 부분 문자열로 나누어 그 결과를 배열로 반환합니다.
"123,456,789".split(",")
// ["123", "456", "789"]
"12304560789".split("0")
// ["123", "456", "789"]search() 정규표현식을 인자로 받아 가장 처음 매칭되는 부분 문자열의 위치를 반환합니다. 매칭되는 문자열이 없으면 -1을 반환합니다.
"JavaScript".search(/script/);
// -1 대소문자를 구분합니다
"JavaScript".search(/Script/);
// 4
"codestates".search(/ode/);
// 1flag
정규표현식은 플래그를 설정해 줄 수 있으며, 플래그는 추가적인 검색 옵션의 역할을 해 줍니다. 이 플래그들은 각자 혹은 함께 사용하는 것이 모두 가능하며, 순서에 구분이 없습니다. 아래는 자주 사용되는 3가지 플래그입니다.
i i를 붙이면 대소문자를 구분하지 않습니다.
let withi = /c/i;
let withouti = /c/;
"Codestates".match(withi);
// ['C']
"Codestates".match(withouti);
// nullg global 의 약자로, g 를 붙이면 검색된 모든 결과를 리턴합니다.
let withg = /c/g;
let withoutg = /c/;
"coolcodestates".match(withg);
// ['c', 'c']
"coolcodestates".match(withoutg);
// ['c'] g 가 없으면 첫 번째 검색 결과만 반환합니다m m을 붙이면 다중행을 검색합니다.
let str = `1st : cool
2nd : code
3rd : states
`;
str.match(/c/gm)
// 3개의 행을 검색하여 모든 c 를 반환합니다.
// ['c', 'c']
str.match(/c/m)
// m은 다중행을 검색하게 해 주지만, g 를 빼고 검색하면 검색 대상을 찾는 순간 검색을 멈추기 때문에
// 첫 행의 ['c'] 만 리턴합니다.정규식 패턴(표현식)
정규표현식에 다양한 특수기호를 함께 사용하면 문자열을 다룰 때에 더 많은 옵션을 설정할 수 있습니다.
정규식 패턴설명
| ^ | 줄(Line)의 시작에서 일치 /^abc/ |
| $ | 줄(Line)의 끝에서 일치 /xyz$/ |
| . | (특수기호, 띄어쓰기를 포함한) 임의의 한 문자 |
| a|b | a or b 와 일치, 인덱스가 작은 것을 우선 반환 |
| * | 0회 이상 연속으로 반복되는 문자와 가능한 많이 일치. {0,} 와 동일 |
| *? | 0회 이상 연속으로 반복되는 문자와 가능한 적게 일치. {0} 와 동일 |
| + | 1회 이상 연속으로 반복되는 문자와 가능한 많이 일치. {1,} 와 동일 |
| +? | 1회 이상 연속으로 반복되는 문자와 가능한 적게 일치. {0} 와 동일 |
| {3} | 숫자 3개 연속 일치 |
| {3,} | 3개 이상 연속 일치 |
| {3, 5} | 3개 이상 5개 이하 연속 일치 |
| () | 캡쳐(capture)할 그룹 |
| [a-z] | a부터 z 사이의 문자 구간에 일치(영어 소문자) |
| [A-Z] | A부터 Z 사이의 문자 구간에 일치(영어 대문자) |
| [0-9] | 0부터 9 사이의 문자 구간에 일치(숫자) |
| \(역슬래쉬) | escape 문자. 특수 기호 앞에 \를 붙이면 정규식 패턴이 아닌, 기호 자체로 인식 |
| \d | 숫자를 검색함. /[0-9]/와 동일 |
| \D | 숫자가 아닌 문자를 검색함. /[^0-9]/와 동일 |
| \w | 영어대소문자, 숫자, (underscore)를 검색함. /[A-Za-z0-9]/ 와 동일 |
| \W | 영어대소문자, 숫자, (underscore)가 아닌 문자를 검색함. /[^A-Za-z0-9]/ 와 동일 |
| [^] | []안의 문자열 앞에 ^이 쓰이면, []안에 없는 문자를 검색함 |
Anchors - ^ and $
^ ^는 문자열의 처음을 의미하며, 문자열에서 ^뒤에 붙은 단어로 시작하는 부분을 찾습니다. 일치하는 부분이 있더라도, 그 부분이 문자열의 시작 부분이 아니면 null 을 리턴합니다.
"coding is fun".match(/^co/);
// ['co']
"coding is fun".match(/^fun/);
// null$ $는 문자열의 끝을 의미하며, 문자열에서 $앞의 표현식으로 끝나는 부분을 찾습니다. ^와 비슷하지만 ^는 문자열의 시작을 찾는 반면, $는 문자열의 마지막 부분을 찾습니다. 마찬가지로 일치하는 부분이 있더라도, 그 부분이 문자열의 끝부분이 아니면 null 을 리턴합니다.
"coding is fun".match(/un$/);
// ['un']
"coding is fun".match(/is$/);
// null
"coding is fun".match(/^coding is fun$/);
// 문자열을 ^ 와 $ 로 감싸주면 그 사이에 들어간 문자열과 정확하게 일치하는 부분을 찾습니다
// ["coding is fun"]Quantifiers — *, +, ? and {}
* *는 *바로 앞의 문자가 0번 이상 나타나는 경우를 검색합니다. 아래와 같은 문자열이 있을 때에 /ode*/g 을 사용하게 되면 "od" 가 들어가면서 그 뒤에 "e"가 0번 이상 포함된 모든 문자열을 리턴합니다.
"co cod code codee coding codeeeeee codingding".match(/ode*/g);
// ["od", "ode", "odee", "od", "odeeeeee", "od"]+
+ 도 * 와 같은 방식으로 작동하며, 다만 + 바로 앞의 문자가 1번 이상 나타나는 경우를 검색한다는 점이 *과 다를 뿐입니다.
"co cod code codee coding codeeeeee codingding".match(/ode+/g);
// ['ode', 'odee', 'odeeeeee']?
? 는 * 또는 + 와 비슷하지만, ? 앞의 문자가 0번 혹은 1번 나타나는 경우만 검색합니다. *? 또는 +? 와 같이 ?는 * 혹은 + 와 함께 쓰는 것도 가능합니다.
"co cod code codee coding codeeeeee codingding".match(/ode?/g);
// ["od", "ode", "ode", "od", "ode", "od"]
"co cod code codee coding codeeeeee codingding".match(/ode*?/g);
// ["od", "od", "od", "od", "od", "od"]
"co cod code codee coding codeeeeee codingding".match(/ode+?/g);
// ["ode", "ode", "ode"]{} {}는 *, *?, +, +? 의 확장판으로 생각할 수 있습니다. *, *?, +, +? 가 '0개 이상' 또는 '1개 이상' 검색이 전부였던 반면, {}는 직접 숫자를 넣어서 연속되는 개수를 설정할 수 있습니다. 아래 예시와 함께 위 표에서 {}와 *, *?, +, +? 의 차이를 다시 한 번 비교해 보세요.
"co cod code codee coding codeeeeee codingding".match(/ode{2}/g);
// 2개의 "e"를 포함한 문자열을 검색합니다.
// ["odee", "odee"]
"co cod code codee coding codeeeeee codingding".match(/ode{2,}/g);
// 2개 이상의 "e"를 포함한 문자열을 검색합니다.
// ["odee", "odeeeeee"]
"co cod code codee coding codeeeeee codingding".match(/ode{2,5}/g);
// 2개 이상 5개 이하의 "e"를 포함한 문자열을 검색합니다.
// ["odee", "odeeeee"]OR operator
| 는 or 조건으로 검색하여 | 의 왼쪽 또는 오른쪽의 검색 결과를 반환합니다.
"Cc Oo Dd Ee".match(/O|D/g);
// ["O", "D"]
"Cc Oo Dd Ee".match(/c|e/g);
// ["c", "e"]
"Cc Oo Dd Ee".match(/D|e/g);
// ["D", "e"]
"Ccc Ooo DDd EEeee".match(/D+|e+/g);
// + 는 1번 이상 반복을 의미하기 때문에
// ["DD", "eee"] 를 반환합니다.Bracket Operator - []
대괄호 [] 안에 명시된 값을 검색합니다.
[abc] // a or b or c 를 검색합니다. or(|) Operator 로 작성한 a|b|c 와 동일하게 작동합니다.
[a-c] // [abc] 와 동일합니다. - 로 검색 구간을 설정할 수 있습니다.
"Ccc Ooo DDd EEeee".match(/[CD]+/g); // [] 에 + 등의 기호를 함께 사용할 수도 있습니다.
// C or D 가 한 번 이상 반복된 문자열을 반복 검색하기 때문에
// ["C", "DD"] 가 반환됩니다.
"Ccc Ooo DDd EEeee".match(/[co]+/g); // ["cc", "oo"]
"Ccc Ooo DDd EEeee".match(/[c-o]+/g); // - 때문에 c ~ o 구간을 검색하여
// ["cc", "oo", "d", "eee"] 가 반환됩니다.
"AA 12 ZZ Ad %% Az !# dd 54 zz".match(/[A-Za-z]+/g);
// a~z 또는 A~Z 에서 한 번 이상 반복되는 문자열을 반복 검색하기 때문에
// ["AA", "ZZ", "Ad", "Az", "dd", "zz"] 를 반환합니다.
"AA 12 ZZ Ad %% Az !# dd 54 zz".match(/[A-Z]+/gi);
// flag i 는 대소문자를 구분하지 않기 때문에 위와 동일한 결과를 반환합니다.
// ["AA", "ZZ", "Ad", "Az", "dd", "zz"]
"AA 12 ZZ Ad %% Az !# dd 54 zz".match(/[0-9]+/g);
// 숫자도 검색 가능합니다.
// ["12", "54"]
"aAbB$#67Xz@9".match(/[^a-zA-Z]+/g);
// [] 안에 ^ 를 사용하면 anchor 로서의 문자열의 처음을 찾는것이 아닌
// 부정을 나타내기 때문에 [] 안에 없는 값을 검색합니다.
// ["$#67", "@9"]Character classes
\d & \D
\d 의 d 는 digit 을 의미하며 0 ~ 9 사이의 숫자 하나를 검색합니다. [0-9] 와 동일합니다.
\D 는 not Digit 을 의미하며, 숫자가 아닌 문자 하나를 검색합니다. [^0-9] 와 동일합니다.
"abc34".match(/\d/); // ["3"]
"abc34".match(/[0-9]/) // ["3"]
"abc34".match(/\d/g); // ["3", "4"]
"abc34".match(/[0-9]/g) // ["3", "4"]
"abc34".match(/\D/); // ["a"]
"abc34".match(/[^0-9]/); // ["a"]
"abc34".match(/\D/g); // ["a", "b", "c"]
"abc34".match(/[^0-9]/g); // ["a", "b", "c"]\w & \W
\w 는 알파벳 대소문자, 숫자, _(underbar) 중 하나를 검색합니다. [a-zA-Z0-9_]와 동일합니다.
\W 는 알파벳 대소문자, 숫자, _ (underbar)가 아닌 문자 하나를 검색합니다. [^a-zA-Z0-9_]와 동일합니다.
"ab3_@A.Kr".match(/\w/); //["a"]
"ab3_@A.Kr".match(/[a-zA-Z0-9_]/) // ["a"]
"ab3_@A.Kr".match(/\w/g); //["a", "b", "3", "_", "A", "K", "r"]
"ab3_@A.Kr".match(/[a-zA-Z0-9_]/g) // ["a", "b", "3", "_", "A", "K", "r"]
"ab3_@A.Kr".match(/\W/); // ["@"]
"ab3_@A.Kr".match(/[^a-zA-Z0-9_]/); // ["@"]
"ab3_@A.Kr".match(/\W/g); // ["@", "."]
"ab3_@A.Kr".match(/[^a-zA-Z0-9_]/g); // ["@", "."]Grouping and capturing
() ()는 그룹으로 묶는다는 의미 이외에도 다른 몇 가지 의미가 더 있습니다.
그룹화 표현식의 일부를 ()로 묶어주면 그 안의 내용을 하나로 그룹화할 수 있습니다. 아래 예시를 통해 그룹화와 그렇지 않은 결과의 차이를 비교해 봅시다.
let co = 'coco';
let cooo = 'cooocooo';
co.match(/co+/); // ["co", index: 0, input: "coco", groups: undefined]
cooo.match(/co+/); // ["cooo", index: 0, input: "cooocooo", groups: undefined]
co.match(/(co)+/); // ["coco", "co", index: 0, input: "coco", groups: undefined]
cooo.match(/(co)+/); // ["co", "co", index: 0, input: "cooocooo", groups: undefined]co+ 는 "c"를 검색하고 + 가 "o"를 1회 이상 연속으로 반복되는 문자를 검색해 주기 때문에 "cooo"가 반환되었습니다.
하지만 (co)+ 는 "c" 와 "o" 를 그룹화하여 "co"를 단위로 1회 이상 반복을 검색하기 때문에 "coco"가 반환되었습니다. 여기서 특이한 점은 일치하는 문자열로 반환된 결과가 2개입니다.
캡처 () 로 그룹화한다고 하였고, 이를 캡처한다 라고 합니다.
co.match(/(co)+/); // ["coco", "co", index: 0, input: "coco", groups: undefined]- () 로 "co"를 캡처
- 캡처한 "co" 는 일단 당장 사용하지 않고, + 가 "co"의 1회 이상 연속 반복을 검색
- 이렇게 캡처 이외 표현식이 모두 작동하고 나면, 캡처해 두었던 "co"를 검색
따라서 2번 과정에 의해 "coco" 가 반환되고, 3번에 의해 "co"가 반환되는 것입니다.
"2021code".match(/(\d+)(\w)/); // ["2021c", "2021", "c", index: 0, input: "2021code", groups: undefined]- () 안의 표현식을 순서대로 캡처 ⇒ \d+ 와 \w
- 캡처 후 남은 표현식으로 검색 ⇒ 이번 예시에는 남은 표현식은 없습니다.
- \d 로 숫자를 검색하되 + 로 1개 이상 연속되는 숫자를 검색 ⇒ 2021
- \w 로 문자를 검색 ⇒ c
- 3번과 4번이 조합되어 "2020c" 가 반환
- 첫 번째 캡처한 (\d+) 로 인해 2021 이 반환
- 두 번째 캡처한 (\w) 로 인해 "c" 가 반환
문자열 대체 시 캡처된 값 참조 캡처된 값은 replace() 메소드를 사용하여 문자 치환 시 참조 패턴으로 사용될 수 있습니다.
우선 첫 번째 (\w+) 가 code 를 캡처하고, 두 번째 (\w+) 가 states 를 캡처합니다.
(/(\w+)\ 와 (\w+)/\사이의 . 은 . 앞에 역슬래시가 사용되었기 때문에 '임의의 한 문자'가 아닌 기호로서의 온점 . 을 의미합니다.)
각 캡처된 값은 첫 번째는 $1 이 참조, 두 번째는 $2 이 참조하기 때문에 이 참조된 값을 "$2.$1" 이 대체하게 되어 code 와 states 가 뒤바뀐 "states.code" 가 반환됩니다.
"code.states".replace(/(\w+)\.(\w+)/, "$2.$1"); //states.codenon-capturing
() 를 사용하면 그룹화와 캡처를 한다고 하였습니다. 하지만 (?:)로 사용하면 그룹은 만들지만 캡처는 하지 않습니다.
let co = 'coco';
co.match(/(co)+/); // ["coco", "co", index: 0, input: "coco", groups: undefined]
co.match(/(?:co)+/);
// ["coco", index: 0, input: "coco", groups: undefined]
// 위 "캡처" 예시의 결괏값과 비교해 보시기 바랍니다.lookahead
(?=) 는 검색하려는 문자열에 (?=여기) 에 일치하는 문자가 있어야 (?=여기) 앞의 문자열을 반환합니다.
"abcde".match(/ab(?=c)/);
// ab 가 c 앞에 있기 때문에 ["ab"] 를 반환합니다.
"abcde".match(/ab(?=d)/);
// d 의 앞은 "abc" 이기 때문에 null 을 반환합니다.negated lookahead
(?!) 는 (?=) 의 부정입니다.
"abcde".match(/ab(?!c)/); // null "abcde".match(/ab(?!d)/); // ["ab"]rockPaperScissors
문제
가위바위보 게임은 2인 이상의 사람이 동시에 '가위, 바위, 보'를 외치고 동시에 가위, 바위 또는 보 중에서 한 가지를 의미하는 손 모양을 내밀어 승부를 결정짓는 게임입니다. 세 판의 가위바위보 게임을 할 경우, 한 사람은 세 번의 선택(예. 가위, 가위, 보)을 할 수 있습니다. 세 번의 선택으로 가능한 모든 경우의 수를 구하는 함수를 작성합니다.
출력
2차원 배열(arr[i])을 리턴해야 합니다.arr[i]는 전체 경우의 수 중 한 가지 경우(총 세 번의 선택)를 의미하는 배열입니다.
arr[i]는 'rock', 'paper', 'scissors' 중 한 가지 이상을 요소로 갖는 배열입니다.
arr[i].length는 3
주의사항
최종적으로 리턴되는 배열의 순서는 가중치 적용 정렬(Weighted Sort)을 따릅니다.
중요도는 'rock', 'paper', 'scissors' 순으로 높습니다.쉽게 생각해 올림픽 순위 결정 방식을 참고하면 됩니다.
금메달('rock')이 은메달('paper')보다 우선하고, 은메달('paper')이 동메달('scissors')보다 우선합니다.
function rockPaperScissors (num) {
let times;
if (num === undefined) {
times = 3
} else {
times = num
}
let way = ['rock', 'paper', 'scissors']
let result = [];
let getResult = (ind, arr) => {
if ( ind === times - 1 ) {
result.push(arr)
return;
}
for ( let n = 0; n < way.length; n++ ) {
getResult(ind + 1, arr.concat(way[n]))
}
}
for ( let j = 0; j < way.length; j++ ) {
getResult(0, [way[j]])
}
return result;
};새로운 치킨 소스 레시피
문제
개업 이래로 항상 승승장구하는 '승승장구 치킨집'의 비결은 소스에 있다. 수많은 타사 브랜드 치킨집들이 승승장구 치킨집의 소스 비결을 알아내려고 했으나 빈번히 포기했다. 그 이유는 5대째 내려오는 '비밀의 승승장구 치킨 소스 비율 레시피'는 70억 인구 중 사장님만 알고 있기 때문이다. 최근, 누리꾼 사이에서 이 레시피의 일부분을 발췌했다는 소문을 듣게 되었다. 그 소문은 다음과 같다.
N 가지의 재료 중에 단 M 가지만을 사용하여 조합한 모든 경우의 수 중 하나이다.재료는 0과 1로만 이루어진 숫자로 암호화가 되어 있고, 항상 1로 시작하며 복호화를 할 수 없다.단, 0이 3개 이상인 재료는 상한 재료이기 때문에 제외한다.재료의 순서에 따라 맛이 달라지기 때문에, 재료를 넣는 순서가 다르다면 다른 레시피이다.
이 소문을 참고하여 '비밀의 승승장구 치킨 소스'가 될 수 있는 경우의 수를 모두 반환하는 함수를 작성하세요.
인자 1: stuffArr
Number 타입의 재료를 담은 배열요소는 0과 1로만 이루어진 숫자이며, 항상 1로 시작합니다.요소는 중복될 수 없습니다.요소의 길이는 20 이하입니다.배열의 길이는 2 이상 10 이하입니다.ex) [111, 110, 1010, 10, 10110]
인자 2: choiceNum
Number 타입의 1 이상 stuffArr 길이 이하의 자연수재료를 선택할 수 있는 수를 뜻합니다.ex) 2
출력
Number 타입을 반환해야 합니다.stuffArr가 [1, 10, 11000, 1111] 이고, choiceNum은 2라면 사용 가능한 재료는 [1, 10, 1111] 입니다. 조합할 수 있는 경우의 수는 6 가지입니다.
주의사항
만약, 주어진 재료 모두 사용할 수 없다면 빈 배열[]을 반환해야 합니다.만약, 사용할 수 있는 재료가 choiceNum보다 작다면 빈 배열[] 을 반환해야 합니다.조합 및 요소는 작은 숫자 -> 큰 숫자로 정렬합니다.예시로 [1, 10, 11000, 1111]이 요소로 들어왔다면, 0이 세 개인 11000을 제외하고 [1, 10, 1111] 순서가 되어야 하며, [ [1, 10], [1, 1111], [10, 1], [10, 1111], [1111, 1], [1111, 10] ]을 반환해야 합니다.
function newChickenRecipe(stuffArr, choiceNum) {
// TODO: 여기에 코드를 작성하세요.
let filteredArr = stuffArr.filter((el) => {
let pattern = /000/;
return pattern.exec(el) === null
})
filteredArr = filteredArr.sort((a,b) => {
return a - b
})
let result = [];
if ( filteredArr.length < choiceNum ) return [];
let makeResult = function (idx, arr, list, num) {
if( idx === choiceNum - 1) {
result.push(list)
return;
}
let splicedArr = arr.slice();
splicedArr.splice(num, 1)
for ( let n = 0; n < splicedArr.length; n++ ) {
makeResult(idx + 1, splicedArr, list.concat(splicedArr[n]), n)
}
}
for ( let j = 0; j < filteredArr.length; j++ ) {
makeResult(0, filteredArr, [filteredArr[j]], j)
}
return result;
}블랙잭은 지겨워
문제
평범한 블랙잭 게임에서 수시로 패배하자 흥미가 떨어진 김코딩은 박타짜에게 게임룰을 변형하여 새로운 카드 놀이를 해 볼 것을 제안합니다. 새로운 룰은 다음과 같습니다.
1. 숫자로 이루어진 카드를 여러 장 받습니다. 2. 3장씩 카드를 고르고, 3장에 적힌 숫자들의 합이 소수인지 확인합니다. 3. 받아든 카드로 만들 수 있는 소수의 개수가 많은 사람이 이기게 됩니다.
예로, [1, 2, 3, 4]라는 카드를 받았을 때 만들 수 있는 숫자는 6, 7, 8, 9이고, 소수는 7 하나이기 때문에 가지고 있는 소수의 개수는 1개입니다. [2, 3, 4, 8, 13]라는 카드를 받았을 때 만들 수 있는 숫자는 9, 13, 18, 14, 19, 23, 15, 20, 24, 25이고, 소수는 13, 19, 23 총 3개이기 때문에 가지고 있는 소수의 개수는 3개입니다.
게임을 진행하기 전에 소수에 대해 아무런 지식이 없는 박타짜는 게임을 며칠 미룬 뒤, 게임의 룰을 따르는 함수를 만들기로 했습니다. 소수에 약한 박타짜를 도와 여러 장의 카드 중 세 장씩 조합해 소수가 되는 경우의 수를 리턴하는 함수를 완성해 주세요.
주의사항
cards 에는 중복된 숫자의 카드는 들어있지 않습니다.
각 카드에 적힌 수는 1이상 1,000이하의 자연수입니다.
function boringBlackjack(cards) {
let sum = [];
for ( let n = 0; n < cards.length; n++ ) {
for ( let j = n + 1; j < cards.length; j++ ) {
for (let x = j + 1; x < cards.length; x++ ) {
let result = cards[n] + cards[j] + cards[x]
if (isPrime(result)) {
sum.push(result)
}
}
}
}
return sum.length
}
function isPrime(num) {
if ( num === 1 ) {
return false;
}
else if ( num === 2 ) {
return true;
}
else if ( num % 2 === 0 ) {
return false;
}
for ( let n = 3; n < num; n = n + 2 ) {
if ( num % n === 0 ) {
return false;
}
}
return true;
}빼빼로 데이
문제
오늘은 빼빼로 데이입니다. 한 회사의 팀장은 출근길에 아몬드 빼빼로 M개와 누드 빼빼로 N개를 구매하여 아침 일찍 출근길에 나섰습니다.
팀장은 자신보다 먼저 출근해 있는 직원들에게 구매한 빼빼로를 전부 나누어 주려고 합니다. 단, 서로 질투하는 경우를 만들지 않기 위해 모든 직원들에게 공평하게 빼빼로를 나누어 주려고 합니다. 직원들은 각각의 빼빼로를 똑같은 개수만큼 받아야 합니다. 빼빼로를 쪼개서 줄 수는 없습니다.
하지만 회사에 도착하기 전이라 몇 명의 직원들이 있는지 모르는 상황입니다. 팀장이 아몬드 빼빼로를 4개, 누드 빼빼로를 8개를 구매 했다면, 다음과 같이 세 가지 방법으로 나누어 줄 수 있습니다.
출근한 직원이 1명이라면 아몬드 빼빼로 4개와 누드 빼빼로 8개를 줄 수 있습니다.출근한 직원이 2명이라면 아몬드 빼빼로 2개와 누드 빼빼로 4개를 각각 줄 수 있습니다.출근한 직원이 3명이라면 빼빼로를 남기지 않고 공평하게 주는 방법은 없습니다.출근한 직원이 4명이라면 아몬드 빼빼로 1개와 누드 빼빼로 2개를 각각 줄 수 있습니다.
팀장은 출근한 직원 수에 따라 어떻게 빼빼로를 나누어 줄지 고민하고 있습니다. 여러분이 직원 수에 따라 빼빼로를 나누어 주는 방법을 구하는 솔루션을 제공해 주세요.
출력
2차원 배열 output을 리턴해야 합니다.output[i]은 다음과 같은 순서를 가진 길이 3의 배열입니다.[빼빼로를 받게 되는 직원의 수, 나누어 주는 아몬드 빼빼로의 수, 나누어 주는 누드 빼빼로의 수]output은 output[i][0], 즉 '빼빼로를 받게 되는 직원의 수'를 기준으로 오름차순으로 정렬합니다.
function divideChocolateStick(M, N) {
// TODO: 여기에 코드를 작성합니다. 최대공약수
// [빼빼로를 받게 되는 직원의 수, 나누어 주는 아몬드 빼빼로의 수, 나누어 주는 누드 빼빼로의 수]
let gcd = makeGcd(M, N)
let result = divisor(gcd);
for (let n = 0; n < result.length; n++ ) {
result[n].push(M / result[n][0])
result[n].push(N / result[n][0])
}
return result;
}
function divisor(num) {
let result = [];
for (let n = 1; n <= num; n++ ) {
if(num % n === 0) result.push([n])
}
return result;
}
function makeGcd(a, b) {
if (b === 0) return a;
return makeGcd(b, a % b);
};=> 실행시간 초과로 인해서 큰 수가 인자로 들어오는 테스트 코드만 통과 못했습니다. 지금 구현한 코드에서 시간복잡도를 줄일 수 있는 방법에 대해 고민하고, 다음에 추가적으로 올리도록 하겠습니다.
집밥이 그리워
문제
김코딩은 몇 년의 해외 출장 끝에 본가에 내려왔습니다. 오랜만에 보는 김코딩의 얼굴에 반가웠던 부모님은 상다리가 부러질 정도로 음식을 만들었습니다. 감동의 재회도 잠시, 의자에 앉아 식사를 하려던 김코딩은 무엇부터 먹어야 될지 깊은 생각에 빠졌습니다. 정성스럽게 차려 주신 만큼, 최대한 많은 방법으로 다양하게 먹고 싶었기 때문입니다.
밥은 한 가지이며 반찬은 다수일 때, 밥과 함께 먹을 수 있는 반찬의 모든 경우의 수를 배열에 담아 리턴하세요.
주의사항
반찬은 영문으로 작성이 되어 있습니다.반찬은 중복되지 않습니다.반찬을 먹지 않는 것도 포함됩니다. (출력되는 2차원 배열은 빈 배열을 포함합니다.)반찬은 3개 이상 99개 이하입니다.출력되는 배열은 전부 사전식 순서(lexical order)로 정렬되어야 합니다.
function missHouseMeal(sideDishes) {
// TODO: 여기에 코드를 작성합니다.
let result = [];
sideDishes.sort()
let num = sideDishes.length
let makeResult = function(idx, element) {
if( idx === num) {
result.push(element)
return;
}
makeResult(idx + 1, element)
makeResult(idx + 1, element.concat(sideDishes[idx]))
}
makeResult(0, [])
return result.sort();
}금고를 털어라
문제
자신이 감옥에 간 사이 연인이었던 줄리아를 앤디에게 빼앗겨 화가 난 조지는 브레드, 맷과 함께 앤디 소유의 카지노 지하에 있는 금고를 털기로 합니다. 온갖 트랩을 뚫고 드디어 금고에 진입한 조지와 일행들. 조지는 이와중에 감옥에서 틈틈이 공부한 알고리즘을 이용해 target 금액을 훔칠 수 있는 방법의 경우의 수를 계산하기 시작합니다.
예를 들어 $50 을 훔칠 때 $10, $20, $50 이 있다면 다음과 같이 4 가지 방법으로 $50을 훔칠 수 있습니다.
$50 한 장을 훔친다$20 두 장, $10 한 장을 훔친다$20 한 장, $10 세 장을 훔친다$10 다섯 장을 훔친다
훔치고 싶은 target 금액과 금고에 있는 돈의 종류 type 을 입력받아, 조지가 target 을 훔칠 수 있는 방법의 수를 리턴하세요.
=> 이 문제는 냅색알고리즘으로, 어제 학습했던 DP방법을 사용하는 기본적인 문제로 알려져있습니다.
첫 번째 조건
큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다 (Overlapping Sub-problems)
=> 큰 문제로부터 나누어진 작은 문제는 큰 문제를 해결할 때 여러 번 반복해서 사용될 수 있어야 한다 는 말과 같습니다.
두 번째 조건
작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다(Optimal Substructure)
=> 이 조건에서 말하는 정답은 최적의 해결 방법(Optimal solution)을 의미합니다.
이러한 냅색 알고리즘에 대해서 어제 처음 알게 되었습니다. 이제 조금 이해가 된 거 같아 코드를 리뷰하면서 학습해보도록 하겠습니다.
먼저, 10원을 훔치려고 하는데 화폐가 1원 2원 5원이 있다고 가정을 하겠습니다.
1원으로 10원을 훔치기 위해서는 1원 5장을 가지고 나가는 한가지의 방법이 있습니다.
=> 즉, 1원으로는 어떠한 금액이든지, 한가지의 방법으로 훔칠 수 있습니다.
여기에서 냅색 알고리즘의 2번째 조건인 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 부분을 활용해서 진행을 해보겠습니다.
| 화폐 \ 훔칠 금액 | 1원 | 2원 | 3원 | 4원 | 5원 |
| 1원 | 1 | 1 | 1 | 1 | 1 |
| 2원 | |||||
| 5원 | |||||
| TOTAL | 1 | 1 | 1 | 1 | 1 |
이처럼 1원으로 1 ~ 5원을 훔칠 수 있는 방법은 1가지씩입니다.
이후 2원으로 훔칠 수 있는 방법에 대해서 알아보겠습니다. 먼저 2원 이하는 훔칠 수 없기 때문에 넘어가도록 하겠습니다.
| 화폐 \ 훔칠 금액 | 1원 | 2원 | 3원 | 4원 | 5원 |
| 1원 | 1 | 1 | 1 | 1 | 1 |
| 2원 | 0 | 1 | 1 | 2 | 2 |
| 5원 | |||||
| TOTAL | 1 | 2 | 2 | 3 | 3 |
2원으로 2원을 훔칠 수 있는 방법은 하나뿐입니다.
* 2원으로 3원을 훔칠 때에는, 3원 - 2원을 하면 1원이 남습니다. 이 때, 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 를 통해서 1원을 훔칠 수 있는 모든 방법(TOTAL)으로 대체가 될 수 있음을 알 수 있습니다.
=> 그래서 2원으로 3원을 훔치는 방법으로는, 1원으로 1원을 훔칠 수 있는 방법의 수(TOTAL)를 넣으면 됩니다.
=> 실제로 보게 된다면, 1원을 훔칠 수 있는 방법의 TOTAL이 1입니다.
=> 그리고 1원과 2원을 가지고 3원을 훔칠 수 있는 방법은 '1원 * 3 '||' 2원 * 1 + 1원 * 1' 로 총 TOTAL이 2가지임을 알 수 있습니다. => 3원 열을 보게 되면, TOTAL은 2입니다.
* 를 코드로 구현하는 방법은 따로 표시해놨습니다.
4원을 훔칠 때의 경우의 수를 통해서 한 번 더 알아보도록 하겠습니다.
실질적으로 1원과 2원으로 4원을 훔치는 방법은 '1원 * 4' || '2원 * 2' || '1원 * 2 + 2원 * 1' 로 3가지가 있습니다.
그렇다면, 표에도 적용되는 보겠습니다. 4원 - 2원은 2원입니다. 앞서 알아봤던 거처럼 적용을 한다면,
훔칠 금액 2원 열의 TOTAL이 2원으로 4원을 훔칠 수 있는 갯수가 됩니다. 2원을 훔치는 총 방법은 2로, 이 2를 2원으로 4원을 훔칠 수 있는 곳에 넣게 된다면, TOTAL은 테이블과 같이 3이 됩니다.
어떻게 풀리는 지에 대해서 알아봤으니, 해당 방법으로 나머지를 채우고 10원까지 알아보도록 하겠습니다.
| 화폐 \ 훔칠 금액 | 1원 | 2원 | 3원 | 4원 | 5원 |
| 1원 | 1 | 1 | 1 | 1 | 1 |
| 2원 | 0 | 1 | 1 | 2 | 2 |
| 5원 | 0 | 0 | 0 | 0 | 1 |
| TOTAL | 1 | 2 | 2 | 3 | 4 |
| 화폐 \ 훔칠 금액 | 6원 | 7원 | 8원 | 9원 | 10원 |
| 1원 | 1 | 1 | 1 | 1 | 1 |
| 2원 | 3 | 3 | 4 | 4 | 5 |
| 5원 | 1 | 2 | 2 | 3 | 4 |
| TOTAL | 5 | 6 | 7 | 8 | 10 |
이러한 방법을 코드로 구현해보도록 하겠습니다.
function ocean(target, type) { // target은 훔칠 금액, type은 훔칠 수 있는 화폐 종류
let bag = [1];
// 배열은 0부터 시작을 하는데, 계산하기 편리하도록 0은 1을 지정해서 넣어주고 시작하겠습니다.
for(let i = 1; i <= target; i++) {
bag[i] = 0;
} // target까지 0으로 채워서 배열을 만듭니다.
// ex) target = 5
// [1, 0, 0, 0 ,0 ,0]
for(let i = 0; i < type.length; i++) {
// 훔칠 수 있는 금액들을 순회
for(let j = 1; j <= target; j++) {
if(type[i] <= j) { // 훔칠 수 있는 화폐 종류 보다 낮은 값들은 살펴볼 필요가 없기 때문에
// 훔칠 수 있는 화폐의 금액보다 크거나 같은 숫자부터 확인을 합니다
// * 로 표시한 곳을 코드로 구현한 부분
bag[j] += bag[j-type[i]];
// 5원을 훔칠 때 1원으로 계산을 하게 된다면,
// bag[1] = bag[1] + bag[1-1]
// bag[1] = 0 + 1 이 됩니다.
// => 1원으로 5원을 훔칠 수 있는 방법은 1가지이다.
// [1, 1, 1, 1, 1, 1] 위에서 봤던 표의 1원 행과 동일하게 만들어 진다.
// 만약에 훔칠 수 있는 종류에 2원이 있다고 한다면
// 3원 부분을 보겠습니다.
// j = 3일때,
// bag[3] = bag[3] + bag[1] < 3원 - 2원 = 1원
// 1원을 훔치는 방법의 total은 1개 입니다.
// 그리고 기존의 1원으로 3원을 훔칠 수 있는 방법 1과 더하면 2가 됩니다.
// bag[3] = 1 + 1로 결국은 2가 된다.
// [1, 1, 2, 2, 1, 1]
=> bag 배열에는 훔칠 수 있는 화폐가 순회를 하면서 훔칠 수 있는 방법의 총 갯수,
위의 예시에서 TOTAL이 입력됨을 알 수 있다!
}
}
}
return bag[target];
}
'~2022 작성 글 > TIL' 카테고리의 다른 글
| TIL 35 관계형 데이터베이스 (2021.11.12) (0) | 2021.11.12 |
|---|---|
| TIL 34 (SQL % noSQL) (2021.11.11) (0) | 2021.11.11 |
| TIL 32 (시간복잡도) (2021.11.09) (0) | 2021.11.09 |
| TIL 31 (Linux 권한, 환경 변수, MySQL) (2021.11.08) (0) | 2021.11.08 |
| TIL 30 (React 에러 및 서버 구현 에러) (2021.11.05~2021.11.06) (0) | 2021.11.06 |
