알고리즘이란?
어떤 문제를 해결하기 위해서 일련의 절차를 정의하고, 공식화한 형태로 표현한 일종의 문제 풀이 방법
프로그래밍에선? = input값을 통해 output값을 얻기 위한 계산 과정
-
입력(Input)
알고리즘은 출력에 필요한 자료를 입력받을 수 있어야 합니다. (꼭 입력값이 없을 수도 있음)
-
출력(Output)
알고리즘은 실행이 되면 적어도 한 가지 이상의 결과를 반드시 출력해야 합니다.
-
유한성(Finiteness)
알고리즘은 유한한 명령어를 수행한 후, 유한한 시간 내에 종료해야 합니다.
-
명확성(Definiteness)
알고리즘의 각 단계는 단순하고 명확해야 하며, 모호해서는 안됩니다.
-
효율성(Efficiency)
알고리즘은 가능한 한 효율적이어야 합니다. (시간 복잡도와 공간 복잡도가 낮을수록 효율적인 알고리즘)
시간 복잡도 (Time Complexity)
입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘
Big-O 표기법
- Big-O(빅-오) → 최악의 경우 = 프로그램이 실행되는 과정에서 “이 정도 시간까지 걸릴 수 있다”를 고려해야 한다!
- Big-Ω(빅-오메가) → 최선의 경우
- Big-θ(빅-세타) → 중간(평균)의 경우
O(1)
=constant complexity (입력값이 증가하더라도 시간이 늘어나지 않는다)
입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다.
function O_1_algorithm(arr, index) {
return arr[index];
}
let arr = [1, 2, 3, 4, 5];
let index = 1;
let result = O_1_algorithm(arr, index);
console.log(result); // 2 (arr의 길이가 100이라도 즉시 index를 통해 값 반환 가능)O(n)
=linear complexity (입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것)
//입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을 때 1초의 100배인 100초가 걸리는 알고리즘
function O_n_algorithm(n) {
for (let i = 0; i < n; i++) {
// do something for 1 second
}
}
//입력값이 1 증가할때마다 코드의 실행 시간이 2초씩 증가 (O(2n)이지만, 같은 비율로 증가하고 있다면 2배,5배,10배 증가하더라도 그대로 O(n)으로 표기)
function another_O_n_algorithm(n) {
for (let i = 0; i < 2n; i++) {
// do something for 1 second
}
}O(log n)
=logarithmic complexity (O(1) 다음으로 빠른 시간 복잡도)
ex) BST에서 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다.
- 1~100 중 하나의 숫자를 플레이어1이 고른다 (30을 골랐다고 가정합니다).
- 50(가운데) 숫자를 제시하면 50보다 작으므로 down을 외친다.
- 1~50중의 하나의 숫자이므로 또다시 경우의 수를 절반으로 줄이기 위해 25를 제시한다.
- 25보다 크므로 up을 외친다.
- 경우의 수를 계속 절반으로 줄여나가며 정답을 찾는다. (최악의 경우에도 7번이면 답 찾기 가능)
O(n^2)
=quadratic complexity (입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가)
ex) 입력값이 1일때 1초가 걸리던 알고리즘에 5라는 값이 주어지면 25초가 걸림
function O_quadratic_algorithm(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
// do something for 1 second
}
}
}
//2n, 5n 을 모두 O(n)이라고 표현하는 것처럼, n^3과 n^5 도 모두 O(n^2)로 표기
function another_O_quadratic_algorithm(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
for (let k = 0; k < n; k++) {
// do something for 1 second
}
}
}
}O(2^n)
=exponential complexity (가장 느린 시간 복잡도)
function fibonacci(n) {
if (n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}데이터 크기에 따른 시간 복잡도
| 데이터 크기 제한 | 예상되는시간 복잡도 |
|---|---|
| n ≤ 1,000,000 | O(n) or O (logn) |
| n ≤ 10,000 | O(n^2) |
| n ≤ 500 | O(n^3) |
공간 복잡도 (Space Complexity)
알고리즘이 수행되는 데에 필요한 메모리의 총량
프로그램이 요구하는 공간 ⇒ 고정적인 공간 + 가변적인 공간
고정적인 공간은 처리할 데이터의 양에 무관하게 항상 요구되는 공간으로서, 프로그램의 성능에 큰 영향을 주지 않음
가변적인 공간은 처리할 테이터의 양에 따라 다르게 요구되는 공간으로서 프로그램의 성능에 큰 영향을 줌!
공간 복잡도 계산은 시간 복잡도 계산과 비슷하게 빅 오 (Big-O) 표기법으로 표현
-
예시
function factorial(n) { if(n === 1) { return n; } return n*factorial(n-1); }변수 n에 따라 변수 n이 n개가 만들어지게 되며, 해당 함수를 재귀함수로 1까지 호출할 경우 n부터 1까지 스택에 쌓이게 됩니다. 따라서 해당 함수의 공간 복잡도는 O(n)입니다.
-
보통 공간 복잡도는 시간 복잡도보다 중요성이 떨어진다.
WHY? 시간이 적으면서 메모리까지 지속적으로 증가하는 경우는 거의 없기 때문..
BUT! 동적 계획법(Dynamic Programming)과 같이 알고리즘이나 하드웨어 환경이 매우 한정되어 있는 경우, 공간 복잡도가 중요!!
알고리즘의 유형
Greedy Algorithm
선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법
Greedy Algorithm 문제 해결 단계
- 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택합니다.
- 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사합니다.
- 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복합니다.
탐욕 알고리즘의 특징
마시멜로 실험이란?
지금 마시멜로를 받겠다고 말하면 1개를 받을 수 있지만, 1분을 기다렸다가 받는다면 2개를 받을 수 있다.
greedy는 "현재"에 최선인 선택을 하기 때문에 마시멜로를 당장 받아내어 1개를 받게 되지만,
전체적으로 보게 되면 1분 뒤에 받는 2개가 최적의 선택이 된다.- 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않습니다.
- 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됩니다.
⇒ 이 두가지 조건을 만족하는 “특정한 상황”이 아니면 최적의 해를 보장할 수 없다.
탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있습니다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있습니다.
예제 (거스름돈)
문제: 타로는 자주 JOI 잡화접에서 물건을 산다. JOI 잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI 잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한 장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.
380엔을 타로가 지불을 해야 한다면 타로가 받아야 할 거스름돈은 620엔입니다. 그렇다면 500엔 1개, 100엔 1개, 10엔 2개로 총 4개의 동전을 거슬러 받는 것이 가장 적게 잔돈을 거슬러 받는 방법일 것입니다. 가장 적게 거슬러 받기 위한 로직을 작성해보도록 하겠습니다.
function keepTheChange(input) {
//1000엔짜리 지폐를 냈다는 가정이 있고, 입력 값으로는 지불해야 할 금액이 들어옵니다.
let change = Number(1000 - input);
//카운트하기 위해 변수 count에 0을 할당합니다.
let count = 0;
//입력 값에 배열이 들어오지 않으므로 직접 큰 잔돈 순서대로 배열을 만들어줍니다.
const joiCoins = [500, 100, 50, 10, 5, 1];
//만든 배열의 개수만큼만 돌려줘야 합니다.
for(let i = 0; i < joiCoins.length; i++){
//거스름돈이 0원이 되면 for문을 멈춥니다.
if(change === 0) break;
//거스름돈과 잔돈을 나눈 몫을 카운팅합니다.(쓰인 잔돈의 개수 카운팅)
count += Math.floor(Number(change/joiCoins[i]));
//거스름돈을 잔돈으로 나눈 나머지를 재할당합니다.
change %= joiCoins[i];
}
//count를 리턴합니다.
return count;
}Algorithm 구현
내가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환하여 코드로 구현한다는 것
본인이 선택한 프로그래밍 언어의 문법을 정확히 알고 있어야 하며, 문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것을 목표로 두는 것
완전 탐색
단순히 모든 경우의 수를 탐색하는 모든 경우를 통칭
- Brute Force (조건/반복을 사용하여 해결) = 시행착오 방법론 무차별 대입 방법 (모든 가능성을 시도, not 최적의 솔루션, but 답은 나옴!)
-
프로세스 속도를 높이는데
사용할 수 있는 다른 알고리즘이 없을 때 -
문제를 해결하는 여러 솔루션이 있고
각 솔루션을 확인해야 할 때예시 ⬇️
우리 집에는 세 명의 아이들이 있습니다. 아이들의 식성은 까다로워, 먹기 싫은 음식과 좋아하는 음식을 철저하게 구분합니다. 먹기 싫은 음식이 식탁에 올라왔을 땐 음식 냄새가 난다며 그 주변의 음식까지 전부 먹지 않고, 좋아하는 음식이 올라왔을 땐 해당 음식을 먹어야 합니다. 세 아이의 식성은 이렇습니다.
첫째: (싫어하는 음식 - 미역국, 카레) (좋아하는 음식 - 소고기, 된장국, 사과)
둘째: (싫어하는 음식 - 참치, 카레) (좋아하는 음식 - 미역국, 된장국, 바나나)
셋째: (싫어하는 음식 - 소고기) (좋아하는 음식 - 돼지고기, 된장국, 참치)
100 개의 반찬이 일렬로 랜덤하게 담긴 상이 차려지고, 한 명씩 전부 먹을 수 있다고 할 때, 가장 많이 먹게 되는 아이와 가장 적게 먹게 되는 아이는 누구일까요? (단, 그 주변의 음식은 반찬의 앞, 뒤로 한정합니다.)
for(let i = 0; i < 100; i++) { if(첫째 식성) { if(싫어하는 음식이 앞뒤로 있는가) { 그냥 넘어가자; } 좋아하는 음식 카운트; } if(둘째 식성) { if(싫어하는 음식이 앞뒤로 있는가) { 그냥 넘어가자; } 좋아하는 음식 카운트; } if(셋째 식성) { if(싫어하는 음식이 앞뒤로 있는가) { 그냥 넘어가자; } 좋아하는 음식 카운트; } } return 많이 먹은 아이;
-
- 재귀
- 순열
- DFS/BFS
예제 (Brute Force Algorithm)
-
순차 검색 알고리즘 (Sequential Search)
배열 안에 특정 값이 존재하는지 검색할 때 인덱스 0부터 마지막 인덱스까지 차례대로 검색
function SequentialSearch2(arr, k) { // 검색 키 K를 사용하여 순차 검색을 구현 // 입력: n개의 요소를 갖는 배열 A와 검색 키 K // 출력: K값과 같은 요소 인덱스 또는 요소가 없을 때 -1 let n = arr.length; // 현재의 배열 개수를 n에 할당합니다. arr[n] = k; // 검색 키를 arr n인덱스에 할당합니다. let i = 0; // while 반복문의 초기 값을 지정하고 while (arr[i] !== k) { // 배열의 값이 k와 같지 않을 때까지 반복합니다. i = i + 1; // k와 같지않을 때 i를 +1 합니다. } if (i < n) { // i가 k를 할당하기전의 배열개수보다 적다면(배열안에 k값이 있다면) return i; // i를 반환합니다. } else { return -1; // -1을 반환합니다. } } -
문자열 매칭 알고리즘 (Brute-Force String Matching)
길이가 n인 전체 문자열과 길이가 m인 문자열 패턴을 포함하는지를 검색
function BruteForceStringMatch(arr, patternArr) { // Brute Force 문자열 매칭을 구현합니다. // 입력: n개의 문자 텍스트를 나타내는 배열 T, m개의 문자 패턴을 나타내는 배열P // 출력: 일치하는 문자열이 있으면 첫번째 인덱스를 반환합니다. 검색에 실패한 경우 -1을 반환합니다. let n = arr.length; let m = patternArr.length; for (let i = 0; i <= n - m; i++) { // 전체 요소개수에서 패턴개수를 뺀 만큼만 반복합니다. 그 수가 마지막 비교요소이기 때문입니다. // i 반복문은 패턴과 비교의 위치를 잡는 반복문입니다. let j = 0; // j는 전체와 패턴의 요소 하나하나를 비교하는 반복문입니다. while (j < m && patternArr[j] === arr[i + j]) { // j가 패턴의 개수보다 커지면 안되기때문에 개수만큼만 반복합니다. // 패턴에서는 j인덱스와 전체에서는 i + j 인덱스의 값이 같은지 판단합니다. // 같을때 j에 +1 합니다. j = j + 1; } if (j === m) { // j와 패턴 수가 같다는 것은 패턴의 문자열과 완전히 같은 부분이 존재한다는 의미입니다. // 이 때의 비교했던 위치를 반환합니다. return i; } } return -1; } -
선택 정렬 알고리즘 (Selection Sort)
전체 배열을 검색하여 현재 요소와 비교하고 컬렉션이 완전히 정렬될 때까지 현재 요소보다 더 작거나 큰 요소(오름차순 또는 내림차순에 따라)를 교환하는 정렬 알고리즘
function SelectionSort(arr) { // 주어진 배열을 Selection Sort로 오름차순 정렬합니다. // 입력: 정렬 가능한 요소의 배열 A // 출력: 오름차순으로 정렬된 배열 for (let i = 0; i < arr.length - 1; i++) { // 배열의 0번째 인덱스부터 마지막인덱스까지 반복합니다. // 현재 값 위치에 가장 작은 값을 넣을 것입니다. let min = i; // 현재 인덱스를 최소값의 인덱스를 나타내는 변수에 할당합니다. for (let j = i + 1; j < arr.length; j++) { // 현재 i에 +1을 j로 반복문을 초기화하고 i 이후의 배열요소과 비교하는 반복문을 구성합니다. if (arr[j] < arr[min]) { // j인덱스의 배열 값이 현재 인덱스의 배열 값보다 작다면 min = j; // j 인덱스를 최소를 나타내는 인덱스로 할당합니다. } } // 반복문이 끝났을 때(모든 비교가 끝났을때) // min에는 최소값의 인덱스가 들어있습니다. // i값과 최소값을 바꿔서 할당합니다. let temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } // 모든 반복문이 끝나면 정렬된 배열을 반환합니다. return arr; } -
버블 정렬 알고리즘 - Bubble Sort
-
Tree 자료 구조의 완전탐색 알고리즘 - Exhausive Search (BFS, DFS)
-
동적 프로그래밍 - DP(Dynamic Programing)
시뮬레이션
모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 유형
예시 ⬇️
무엇을 위한 조직인지는 모르겠지만, 비밀스러운 비밀 조직 '시크릿 에이전시'는 소통의 흔적을 남기지 않기 위해 3 일에 한 번씩 사라지는 메신저 앱을 사용했습니다. 그러나 내부 스파이의 대화 유출로 인해 대화를 할 때 조건을 여러 개 붙이기로 했습니다. 해당 조건은 이렇습니다.
- 캐릭터는 아이디, 닉네임, 소속이 영문으로 담긴 배열로 구분합니다.
- 소속은 'true', 'false', 'null' 중 하나입니다.
- 소속이 셋 중 하나가 아니라면 아이디, 닉네임, 소속, 대화 내용의 문자열을 전부 X로 바꿉니다.
- 아이디와 닉네임은, 길이를 2진수로 바꾼 뒤, 바뀐 숫자를 더합니다.
- 캐릭터와 대화 내용을 구분할 땐
공백:공백으로 구분합니다: ['Blue', 'Green', 'null'] : hello.- 띄어쓰기 포함, 대화 내용이 10 글자가 넘을 때, 내용에
.,-+이 있다면 삭제합니다.- 띄어쓰기 포함, 대화 내용이 10 글자가 넘지 않을 때, 내용에
.,-+@#$%^&*?!이 있다면 삭제합니다.- 띄어쓰기를 기준으로 문자열을 반전합니다: 'abc' -> 'cba'
- 띄어쓰기를 기준으로 소문자와 대문자를 반전합니다: 'Abc' -> 'aBC'
시크릿 에이전시의 바뀌기 전 대화를 받아, 해당 조건들을 전부 수렴하여 수정한 대화를 객체에 키와 값으로 담아 반환하세요. 같은 캐릭터가 두 번 말했다면, 공백을 한 칸 둔 채로 대화 내용에 추가되어야 합니다. 대화는 문자열로 제공되며, 하이픈
-으로 구분됩니다.문자열은 전부 싱글 쿼터로 제공되며, 전체를 감싸는 문자열은 더블 쿼터로 제공됩니다.
예: "['Blue', 'Green', 'null'] : 'hello. im G.' - ['Black', 'red', 'true']: '? what? who are you?'"
"['Blue', 'Green', 'null'] : 'hello. im G.' - ['Black', 'red', 'true']: '? what? who are you?'"입력값으로 받은 문자열을 각 캐릭터와 대화에 맞게 문자열로 파싱을 하고, 파싱한 문자열을 상대로 캐릭터와 대화를 구분합니다.
- 첫 번째 파싱은 `
을 기준으로['Blue', 'Green', 'null'] : 'hello. im G.',['Black', 'red', 'true']: '? what? who are you?'` 두 부분으로 나눕니다.- 두 번째 파싱은
:을 기준으로\['Blue', 'Green', 'null'\]배열과'hello. im G.'문자열로 나눕니다.- 배열과 문자열을 사용해, 조건에 맞게 변형합니다.
- 소속이 셋 중 하나인지 판별합니다.
['Blue', 'Green', 'null']아이디와 닉네임의 길이를 2진수로 바꾼 뒤, 숫자를 더합니다:[1, 2, 'null']'hello. im G.'10 글자가 넘기 때문에,.,-+@#$%^&*를 삭제합니다:'hello im G''hello im G'띄어쓰기를 기준으로 문자열을 반전합니다:'olleh mi G''olleh mi G'소문자와 대문자를 반전합니다:'OLLEH MI g'- 변형한 배열과 문자열을 키와 값으로 받아 객체에 넣습니다.
{ "[1, 2, 'null']": 'OLLEH MI g' }
Dynamic Programming (동적 계획법)
greedy 알고리즘이 매 순간 최적의 선택을 찾는 방식이라면, DP는 모든 경우의 수를 조합해 최적의 해법을 찾습니다.
즉, 주어진 문제를 여러 개의 (작은) 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결합니다. 하위 문제를 계산한 뒤 그 해결책을 저장하고, 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄입니다. 다시 말해, 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이 바로 이 다이내믹 프로그래밍입니다.
두 가지 가정이 만족하는 조건에서 사용 가능! 🔽
- Overlapping Sub-problems : 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.
- Optimal Substructure : 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다.
Overlapping Sub-problems
큰 문제로부터 나누어진 작은 문제는 큰 문제를 해결할 때 여러 번 반복해서 사용될 수 있어야 합니다.
예시 ⬇️ 피보나치 수열
function fib(n) {
if(n <= 2) {
return 1;
};
return fib(n - 1) + fib(n - 2);
}
// 1, 1, 2, 3, 5, 8...
fib(7) = fib(6) + fib(5)
fib(7) = (fib(5) + fib(4)) + fib(5) // fib(6) = fib(5) + fib(4)
fib(7) = ((fib(4) + fib(3)) + fib(4)) + (fib(4) + fib(3)) // fib(5) = fib(4) + fib(3)
...피보나치 수열은 위 예시처럼 동일한 계산을 반복적으로 수행해야 합니다.
fib(5) 는 두 번, fib(4) 는 세 번, fib(3) 은 다섯 번의 동일한 계산을 반복합니다.
이렇게, 작은 문제의 결과를 큰 문제를 해결하기 위해 여러 번 반복하여 사용할 수 있을 때, 부분 문제의 반복(Overlapping Sub-problems)이라는 조건을 만족합니다.
그러나 이 조건을 만족하는지 확인하기 전에, 한 가지 주의해야 할 점이 있습니다. 주어진 문제를 단순히 반복 계산하여 해결하는 것이 아니라, 작은 문제의 결과가 큰 문제를 해결하는 데에 여러 번 사용될 수 있어야 합니다.
Optimal Substructure
이 조건에서 말하는 정답 = 최적의 해결 방법(Optimal solution)
주어진 문제에 대한 최적의 해법을 구할 때, 주어진 문제의 작은 문제들의 최적의 해법(Optimal solution of Sub-problems)을 찾아야 합니다. 그리고 작은 문제들의 최적의 해법을 결합하면, 결국 전체 문제의 최적의 해법(Optimal solution)을 구할 수 있습니다.
예시 ⬇️ 최단 경로 찾기
A → D로 가는 최단 경로 : A → B → C → D
A → C로 가는 최단 경로 : A → B → C (A → B → E → C 가 아닙니다.)
A → B로 가는 최단 경로 : A → B
정리해보면 A에서 D로 가는 최단 경로는 그것의 작은 문제인 A에서 C로 가는 최단 경로, 그리고 한 번 더 작은 문제인 A에서 B로 가는 최단 경로의 파악할 수 있습니다. 이렇게 Dynamic Programming을 적용하기 위해서는, 작은 문제의 최적 해법을 결합하여 최종 문제의 최적 해법을 구할 수 있어야 합니다.
예제 (피보나치 수열과 타일링)
DP를 이용하여 피보나치 수열을 해결하려고 할 때, 2가지의 방법!
-
Recursion + Memoization (메모이제이션을 적용)
Memoization - 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술
이런 풀이 과정이 마치, 위에서 아래로 내려가는 것과 같습니다. 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여, 이 방식을
Top-down방식이라 부르기도 합니다.function fibMemo(n, memo = []) { //이 빈 배열은 하위 문제의 결괏값을 저장하는 데에 사용 //n번째 인덱스에 해당하는 피보나치 값이 저장되어 있다면, 그 값 그대로 사용 if(memo[n] !== undefined) { return memo[n]; } if(n <= 2) { return 1; } // 없다면 재귀로 결괏값을 도출하여 res 에 할당 let res = fibMemo(n-1, memo) + fibMemo(n-2, memo); // 추후 동일한 문제를 만났을 때 사용하기 위해 리턴 전에 memo 에 저장 memo[n] = res; return res; }
-
Iteration + Tabulation (반복문과 다이내믹 프로그래밍)
Tabulation = 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 제일 작은 값부터 구해 리스트(도표)에 작성함으로써 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술
재귀 함수를 이용한 방법이 문제를 해결하기 위해 큰 문제부터 시작하여 작은 문제로 옮아가며 문제를 해결하였다면, 반복문을 이용한 방법은, 작은 문제에서부터 시작하여 큰 문제를 해결해 나가는 방법입니다. 따라서 이 방식을 Bottom-up 방식이라 부르기도 합니다.
function fibTab(n) { if(n <= 2) { return 1; } // n 이 1 & 2일 때의 값을 미리 배열에 저장해 놓는다 let fibNum = [0, 1, 1]; for(let i = 3; i <= n; i++) { fibNum[i] = fibNum[i-1] + fibNum[i-2]; // n >= 3 부터는 앞서 배열에 저장해 놓은 값들을 이용하여 // n번째 피보나치 수를 구한 뒤 배열에 저장 후 리턴한다 } return fibNum[n]; } -
2X1 타일링
2xn 크기의 타일이 주어진다면, 2x1과 1x2 크기의 타일로 채울 수 있는 경우의 수를 모두 구해야 합니다.
2개의 타일로 빈 공간을 어떻게 채우든 상관없이,
맨 마지막 타일은세로 타일 1개이거나가로 타일 2개인, 2 가지 경우밖에 없습니다. 맨 마지막 타일의 경우의 수를 제외했을 때 남는 공간의 마지막 타일도 세로 타일 1개, 혹은 가로 타일 2개인 2가지 경우밖에 없습니다. 이렇게, DP 문제는 문제 속의 규칙성을 찾는 것이 키 포인트입니다.
function tiling2x1(n) { let memo = [0, 1, 2]; for (let i = 3; i <= n; i++) { memo[i] = memo[i - 1] + memo[i - 2]; } return memo[n]; };
코플릿
[Greedy] 짐 나르기
문제:
박스를 최대한 적게 사용하여 모든 짐을 옮기려고 합니다.
짐의 무게를 담은 배열 stuff와 박스의 무게 제한 limit가 매개변수로 주어질 때, 모든 짐을 옮기기 위해 필요한 박스 개수의 최소값을 return 하도록 movingStuff 함수를 작성하세요.
입력:
인자 1: stuff
Number타입의 40 이상 240 이하의 자연수를 담은 배열- ex)
[70, 50, 80, 50]
- ex)
인자 2: limited
Number타입의 40 이상 240 이하의 자연수
출력:
Number타입을 리턴해야 합니다.- 모든 짐을 옮기기 위해 필요한 박스 개수의 최솟값을 숫자로 반환합니다.
주의 사항:
- 옮겨야 할 짐의 개수는 1개 이상 50,000개 이하입니다.
- 박스의 무게 제한은 항상 짐의 무게 중 최대값보다 크게 주어지므로 짐을 나르지 못하는 경우는 없습니다.
let output = movingStuff([70, 50, 80, 50], 100);
console.log(output); // 3
let output = movingStuff([60, 80, 120, 90, 130], 140);
console.log(output); // 4function movingStuff(stuff, limit) {
//여러 요소를 합쳤을 때, limit보다 작을 경우를 세야된다.
//오름차순으로 stuff 배열을 정렬한 뒤, 가장 큰 값과 가장 작은 값의 합과 limit를 비교
let sortedArr=stuff.sort((a,b)=>a-b);
//가장 작은값+ 가장 큰 값이 limit를 넘기지 않으면 계속 비교해준다 => limit에 가장 가깝게 가기위한 greedy 알고리즘 탐색방법
let count =0; //박스의 개수 카운팅 위한 변수 선언
let min=0; //가장 작은 값의 인덱스
let max=stuff.length-1; //가장 큰 값의 인덱스
for(let i=0;min<=max;i++){ //모든 배열의 요소를 다 돌때까지 반복
if(sortedArr[min]+sortedArr[max]<=limit){ //무게 제한 이하인 경우,
min++;
max--;
count++;
} else if(sortedArr[min]+sortedArr[max]>limit){ //무게 제한을 초과한다면,
count++; //max값 하나만 박스에 담기게 되니까 count증가
max--; //더 작은값과 비교
}
}
//반복 종료되면 박스 개수 반환
return count;
}function movingStuff(stuff, limit) {
//1. 배열을정렬해준다 (오름차순)
let sortedArr=stuff.sort((a,b)=>a-b)
//2. 배열의가장왼쪽요소와배열의가장오른쪽요소를더한다
let min=0;
let max=sortedArr.length-1;
let count=0;
//5. 박스가모두사라질때 까지 2~4를 반복한다
while(min<=max){
//3. 더한값이 limit보다클 경우가장오른쪽요소를제거해주고(박스에 담고) 카운트를 센다
if(sortedArr[min]+sortedArr[max]>limit){
count++;
max--;
//4. 더한값이 limit보다작을경우두 요소모두제거하고카운트를센다
} else if(sortedArr[min]+sortedArr[max]<=limit){
min++;
max--;
count++
}
}
return count;
}[Greedy] 편의점 알바
문제: 현재 가지고 있는 동전은 1원,5원,10원,50원,100원,500원으로 오름차순으로 정렬되어 있고, 각 동전들은 서로 배수 관계에 있습니다.
동전 개수를 최소화하여 거스름돈 K를 만들어야 합니다. 이때, 필요한 동전 개수의 최솟값을 구하는 함수를 작성해 주세요.
입력:
인자: k
number타입의 k- 1 <= k <= 100,000,000
출력: number 타입의 거스름돈 K원을 만드는데 필요한 동전 개수의 최솟값을 반환해야 합니다.
// 4000원을 받았을 때 500원짜리 동전 8개를 반환합니다.
const output1 = partTimeJob(4000);
console.log(output1); // --> 8
// 4972원을 받았을 때 500원짜리 동전 9개, 100원짜리 동전 4개, 50원짜리 동전 1개, 10원짜리 동전 2개, 1원짜리 동전 2개, 총 18개를 반환합니다.
const output2 = partTimeJob(4972);
console.log(output2); // --> 18function partTimeJob(k) {
//각 동전들이 서로 배수관계이기 때문에 greedy 알고리즘 이용 가능
let count = 0; //동전의 개수를 카운트하기 위한 변수
let counter=[500,100,50,10,5,1]; //거스름돈 배열 만들기
for(let i=0;i<counter.length;i++){
count=count+Math.floor(k/counter[i]); //동전의 개수는 k원을 받았을때 k/동전금액 (4972원을 받았을 때, 4972/500원짜리 하면 9개 count)
k=k-counter[i]*Math.floor(k/counter[i]); //이때 k는 4972원에서 500원짜리 * 9개한 4500원을 뺀 나머지 금액
}
//반복문 끝나면 동전 개수 반환
return count;
}function partTimeJob(k) {
//거스름돈 횟수 세기 위한 카운트
let count=0;
while(k-500>=0){
k=k-500;
count++;
}
while(k-100>=0){
k=k-100;
count++;
}
while(k-50>=0){
k=k-50;
count++;
}
while(k-10>=0){
k=k-10;
count++;
}
while(k-5>=0){
k=k-5;
count++;
}
while(k-1>=0){
k=k-1;
count++;
}
return count;
}[구현] 보드 게임
문제:
N * N의 크기를 가진 보드판 위에서 게임을 하려고 합니다. 게임의 룰은 다음과 같습니다.
- 좌표 왼쪽 상단(0, 0)에 말을 놓는다.
- 말은 상, 하, 좌, 우로 이동할 수 있고, 플레이어가 조작할 수 있다.
- 조작의 기회는 딱 한 번 주어진다.
- 조작할 때 U, D, L, R은 각각 상, 하, 좌, 우를 의미하며 한 줄에 띄어쓰기 없이 써야 한다.
- 예시:
UDDLLRRDRR,RRRRR
- 예시:
- 한 번 움직일 때마다 한 칸씩 움직이게 되며, 그 칸 안의 요소인 숫자를 획득할 수 있다.
- 방문한 곳을 또 방문해도 숫자를 획득할 수 있다.
- 보드 밖을 나간 말은 OUT 처리가 된다.
- 칸 안의 숫자는 0 또는 1이다.
- 단, 좌표 왼쪽 상단(0, 0)은 항상 0이다.
- 획득한 숫자를 합산하여 숫자가 제일 큰 사람이 이기게 된다.
보드판이 담긴 board와 조작하려고 하는 문자열 operation이 주어질 때, 말이 해당 칸을 지나가면서 획득한 숫자의 합을 구하는 함수를 작성하세요.
입력:
인자 1: board
number타입의 2차원 배열- 2 <= board.length <= 1,000
- 예:
[ [0, 0, 1], [1, 0, 1], [1, 1, 1] ]
인자 2: operation
string타입의 대문자 영어가 쓰여진 문자열- 1 <= operation.length <= board.length * 2
- U, L, D, R 이외의 문자열은 없습니다.
출력:
Number타입을 반환해야 합니다.- board와 operation이 입력값의 예시 (
[ [0, 0, 1], [1, 0, 1], [1, 1, 1] ],DDR)일 때, (0, 0) -> (1, 0) -> (2, 0) -> (2, 1) 순서로 이동하게 되고, 각 0, 1, 1, 1을 얻어3을 반환합니다.
- board와 operation이 입력값의 예시 (
const board1 = [
[0, 0, 0, 1],
[1, 1, 1, 0],
[1, 1, 0, 0],
[0, 0, 0, 0]
]
const output1 = boardGame(board1, 'RRDLLD');
console.log(output1); // 4function boardGame(board, operation) {
let score=0; //점수
let cur=board[0][0]; //시작점
let x=0; //가로
let y=0; //세로
for(let i=0;i<operation.length;i++){ //문자열 길이만큼만 움직이면 됨
if(operation[i]==="U"){
y--; //세로축은 위로가니까 숫자 -1
} else if(operation[i]==="D"){
y++;
} else if(operation[i]==="R"){
x++; //가로축으로 숫자 +1
} else if(operation[i]==="L"){
x--;
}
if(y<0||x<0||board.length<y||board.length<x){
return "OUT"
}
score=score+board[y][x];
}
return score;
};[DP] 금고를 털어라
문제:
예를 들어 $50 을 훔칠 때 $10, $20, $50 이 있다면 다음과 같이 4 가지 방법으로 $50을 훔칠 수 있습니다.
- $50 한 장을 훔친다
- $20 두 장, $10 한 장을 훔친다
- $20 한 장, $10 세 장을 훔친다
- $10 다섯 장을 훔친다
훔치고 싶은 target 금액과 금고에 있는 돈의 종류 type 을 입력받아, 조지가 target 을 훔칠 수 있는 방법의 수를 리턴하세요.
입력:
인자 1: target
Number타입의 100,000 이하의 자연수
인자 2: type
Number타입을 요소로 갖는 100 이하의 자연수를 담은 배열
출력:
Number타입을 리턴해야 합니다.- 조지가 target을 훔칠 수 있는 방법의 수를 숫자로 반환합니다.
주의 사항: 모든 화폐는 무한하게 있다고 가정합니다.
let output = ocean(50, [10, 20, 50]);
console.log(output); // 4
let output = ocean(100, [10, 20, 50]);
console.log(output); // 10function ocean(target, type) {
//1. target+1 길이의배열을만들어준다.(bag)
//2. bag의 0번째요소는 1로, 나머지요소는 0으로채워준다.
let bag=[1]; //0원을 만들 수 있는 경우의 수=아무것도 선택해주지 않으면 되므로 1로 초기값 고정
for(let i=1;i<=target;i++){
bag[i]=0;
}
//3. type의 종류별로 bag을 순회하면서(이중 for 문)
for(let i=0;i<type.length;i++){ //target금액이 순차적으로 1씩 증가하면서
for(let j=0;j<bag.length;j++){
//4. j가 type[i]보다크거나같을경우, bag[j]의 값을 (작은구간은 type[i]로 만들 수 없는 금액이기 때문에)
if(j>=type[i]){
//“bag[j]+bag[j-type[i]]”로 바꿔준다. (기존 경우의 수에 더해주는 식)
bag[j]=bag[j]+bag[j-type[i]]
}
}
}
//5. for문이끝난후 bag[target]을 리턴해준다. (target 인덱스에 타켓 금액을 훔칠수 있는 경우의 수가 쌓이므로)
return bag[target];
}