성능 평가, 문제 해결 접근법/패턴
배열과 객체의 성능 평가
슬라이드
문제 해결 접근법
슬라이드
Q. 알고리즘이란 무엇인가?
특정한 작업을 수행하기 위한 과정(process)이나 일련의 단계(set of steps)를 말한다.
Q. 왜 알아야 되는데요?
내가 하는 모든 프로그래밍 작업에는 알고리즘과 관련되어있다.
성공적인 문제해결을 이뤄낼 기초가 된다.
가장 중요한건, 인터뷰에 꼭 나온다(What the ...).
Q. 알고리즘 능력 어떻게 키워요?
1. 문제 해결 계획을 수정/재고 한다. <- 이번 챕터
2. 일반적인 문제 해결 패턴을 익힌다
Q. 문제 해결 전략
1. 문제 이해
Q. 문제, 다시 이해한 대로 말할 수 있나?
Q. 입력값은 뭘까?
Q. 솔루션(만든함수)에서 나오는 출력값은 뭐지?
Q. 출력값은 입력값으로 부터 결정 될 수 있나? 즉, 문제를 해결할 충분한 정보를 가지고 있나?
Q. 어떻게 중요한 데이터에 라벨을 달까?
2. 정확한 예시 탐색
예시문제1) 두 숫자를 인수로 받아 합계를 리턴하는 함수를 만드세요^_^.
- 예시 떠올리기, 예시가 적절해야함. -> User Stories! Unit Tests!
- 간단한 예시로 시작
- 더 복잡한 예시로 진보
- 빈 입력값 or 타당하지 않은 입력값으로 예시 탐색
3. 문제 박살내기(완전 이해)
예시문제 2) 문자열을 인수로 받아 문자열 길이를 리턴하는 함수를 만드세요^_^
- 문제 풀이 단계를 정확히 쓰기 -> 몰랐던 개념 이나 문제 오해를 바로 잡을 수 있다
4. 문제 풀기 / 간소화 시키기
- 핵심적으로 여려운 부분 찾기
- 그 어려움 잠시 무시하기
- 간단한 해결책 써보기
- 다시 어려웠던 해결책을 해결해보기
5. 회고 하기 / 리팩토링
- 결과 확인 했나?
- 결과가 다르게 도출되나?
- 문제가 한번에 이해가 되나?
- 솔루션을 다른 문제에 사용할 수 있나?
- 솔루션의 수행력을 향상시킬 수 있나?
- 리팩토링 하는 다른 방법 존재하나?
- 다른 사람들은 어떻게 풀지?
문제풀이 단계 정리!
문제 이해 -> 예시 탐색 -> 문제 완벽 이해 -> 풀기/간소화 -> 회고/리팩토링
문제 해결 패턴
Q. 다시, 알고리즘 능력 어떻게 키워요?
1. 문제 해결 계획을 수정/재고 한다.
2. 일반적인 문제 해결 패턴을 익힌다 <- 이번 챕터
몇 가지 패턴
- Frequency Counter
1. value 값/value 빈도 값을 모으기 위해 object나 set을 사용한다.
2. 중첩 루프 또는 배열이나 문자로 하는 O(n²) 작업이 필요하지 않다.
예시문제1) 두 배열을 인자로 받는 함수를 만드시오. boolean 값을 리턴 값으로 한다.
만약 첫번째 배열인자들의 제곱이 두번째 배열인자에 전부 존재 하면 true. 아니면 false를 리턴한다.
same([1,2,3], [4,1,9]) // true
same([1,2,3], [1,9]) // false
same([1,2,1], [4,4,1]) // false (must be same frequency)간단한 솔루션 (시간 복잡도 - N²) => BAD!
function same(arr1, arr2){
if(arr1.length !== arr2.length){
return false;
}
for(let i = 0; i < arr1.length; i++){
let correctIndex = arr2.indexOf(arr1[i] ** 2)
if(correctIndex === -1) {
return false;
}
arr2.splice(correctIndex,1)
}
return true
}리팩토링 - 시간복잡도 - O(n) => GREAT!
function same(arr1, arr2){
if(arr1.length !== arr2.length){
return false;
}
let frequencyCounter1 = {}
let frequencyCounter2 = {}
for(let val of arr1){
frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1
}
for(let val of arr2){
frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1
}
for(let key in frequencyCounter1){
if(!(key ** 2 in frequencyCounter2)){
return false
}
if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
return false
}
}
return true
}
예시문제2) 아나그램 - 두 문자열이 주어질 때, 두번째 문자열이 첫번 째 문자열과 아나그램인지 판별하는 함수를 만드시오. 아나그램이란 다른 글자를 재정렬하여 만든 단어, 구 또는 이름을 말한다. iceman -> cinema
validAnagram('', '') // true
validAnagram('aaz', 'zza') // false
validAnagram('anagram', 'nagaram') // true
validAnagram("rat","car") // false) // false
validAnagram('awesome', 'awesom') // false
validAnagram('qwerty', 'qeywrt') // true
validAnagram('texttwisttime', 'timetwisttext') // true풀이!
나의 풀이
// 문자열 2개를 인자로 받는다
//예외처리 - 두 문자열 길이가 다르면 false 리턴
//strObj1, strObj2 객체 2개를 생성
//str1 문자열을 반복순회
//문자 하나를 key로, 문자 개수를 value로 strObj1에 담음
//str2 문자열을 반복순회
//문자 하나를 key로, 문자 개수를 value로 strObj2에 담음
//strObj1를 반복순회
//key가 strObj2의 key로 존재하는지 체크 -> 존재안하면 false 리턴
//strObj2[key]인 value값이 strObj1[key]인 value값과 일치한지 체크 -> 일치 안하면 false 리턴
// true 리턴
function validAnagram(str1, str2){
if (str1.length !== str2.length) return false;
let strObj1 = {}, strObj2 = {};
for (let x of str1) {
strObj1[x] = (strObj1[x] || 0) + 1;
}
for (let x of str2) {
strObj2[x] = (strObj2[x] || 0) + 1;
}
console.log(strObj1, strObj2);
for (let x in strObj1) {
if (!(x in strObj2)) return false;
if ((strObj1[x] !== strObj2[x])) return false;
}
return true;
}
validAnagram('', '');// true
validAnagram('aaz', 'zza');// false
validAnagram('anagram', 'nagaram');// true
validAnagram("rat","car");// false) // false
validAnagram('awesome', 'awesom');// false
validAnagram('qwerty', 'qeywrt');// true
validAnagram('texttwisttime', 'timetwisttext');// trueInstructor의 풀이
function validAnagram(first, second) {
if (first.length !== second.length) {
return false;
}
const lookup = {};
for (let i = 0; i < first.length; i++) {
let letter = first[i];
// if letter exists, increment, otherwise set to 1
lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
}
console.log(lookup)
for (let i = 0; i < second.length; i++) {
let letter = second[i];
// can't find letter or letter is zero then it's not an anagram
if (!lookup[letter]) {
return false;
} else {
lookup[letter] -= 1;
}
}
return true;
}
// {a: 0, n: 0, g: 0, r: 0, m: 0,s:1}
validAnagram('anagrams', 'nagaramm')
- Multiple Pointers
1. 인덱스(위치)에 해당하고 특정 조건에 따라 시작, 끝 또는 중간으로 이동하는 포인터 또는 값 만들기
2. 최소 공간 복잡도를 가져서 매우 효율적이다.
예시문제1) 정렬된 배열을 인자로 받는 함수를 만드는데, 이 함수는 두 요소의 값이 처음 0이 되는 짝을 찾아야 한다. 두 요소의 합이 처음으로 0이 되면 두 요소를 리턴하고 0이 되는 합이 없다면 undefined를 리턴해야 한다.
sumZero([-3,-2,-1,0,1,2,3]) // [-3,3]
sumZero([-2,0,1,3]) // undefined
sumZero([1,2,3]) // undefined간단한 솔루션 - 시간복잡도- O(n²), 공간 복잡도 - O(1) => BAD!
function sumZero(arr){
for(let i = 0; i < arr.length; i++){
for(let j = i+1; j < arr.length; j++){
if(arr[i] + arr[j] === 0){
return [arr[i], arr[j]];
}
}
}
}리팩토링 - 시간복잡도-O(N), 공간복잡도-O(1) => GREAT!
function sumZero(arr){
let left = 0;
let right = arr.length - 1;
while(left < right){
let sum = arr[left] + arr[right];
if(sum === 0){
return [arr[left], arr[right]];
} else if(sum > 0){
right--;
} else {
left++;
}
}
}
문제예시2) countUniqueValues
정렬된 배열을 인자로 받고, unique한 값의 갯수를 리턴하는 함수를 만드시오.
배열에 음수가 들어 있을 수 있다. 하지만 항상 배열은 정렬된 상태이다.
countUniqueValues([1,1,1,1,1,2]) // 2
countUniqueValues([1,2,3,4,4,4,7,7,12,12,13]) // 7
countUniqueValues([]) // 0
countUniqueValues([-2,-1,-1,0,1]) // 4Self
function countUniqueValues(arr){
if(arr.length === 0) return 0;
let lt = 0;
for (let rt = lt+1; rt < arr.length; rt++) {
if (arr[lt] !== arr[rt]) {
lt++;
arr[lt] = arr[rt];
}
}
return lt+1
}상세풀이
i
1 1 2 2 3 3 4 5 가 있을때 arr[i] !== arr[j] 이면 arr[i+1] = arr[j]를 해준다
j
i
1 2 2 2 3 3 4 5
j
이제 j 값을 올리면서 다시 비교해준다.
i
1 2 2 2 3 3 4 5 여기서 arr[i] !== arr[j] 이므로 arr[i+1] = arr[j]
j j j
i
1 2 3 2 3 3 4 5
j
다시 j값을 올리면서 다시 비교
i
1 2 3 2 3 3 4 5 여기서도 arr[i] !== arr[j] 이므로 arr[i+1] = arr[j]
j j j
i
1 2 3 4 3 3 4 5
j
다시 j값을 올리면서 다시 비교
i
1 2 3 4 3 3 4 5 여기서도 arr[i] !== arr[j] 이므로 arr[i+1] = arr[j]
j j
i
1 2 3 4 5 3 4 5
j
다시 j값을 올리려는데 arr.length범위를 벗어난다. 반복문 종료.
i
1 2 3 4 5 3 4 5
j
i는 배열의 유일한 값만 있는 마지막 인덱스 이므로, 유일한 값의 개수를 구하려면 i+1 리턴한다.
- Sliding Window
1. 이 패턴은 한 위치에서 다른 위치로 이동하는 배열/숫자가 될 수 있는 창을 만드는 작업이다.
2. 특정 조건에 따라 창은 커지거나 닫혀진다. (그리고 새 창이 생성된다)
3. 배열/문자열 의 데이터 하위 집합(subset)을 추적하는데 매우 유용하다
예시문제1) 정수배열과 숫자(n)를 인자로 받는 함수를 만드는데, 이 함수는 배열에서 연속된 n개 요소의 최대 합계를 리턴한다. (최대 부분합 구하기)
maxSubarraySum([1,2,5,2,8,1,5],2) // 10
maxSubarraySum([1,2,5,2,8,1,5],4) // 17
maxSubarraySum([4,2,1,6],1) // 6
maxSubarraySum([4,2,1,6,2],4) // 13
maxSubarraySum([],4) // null
간단한 솔루션 - 시간 복잡도(O²)
function maxSubarraySum(arr, num) {
if ( num > arr.length){
return null;
}
var max = -Infinity;
for (let i = 0; i < arr.length - num + 1; i ++){
temp = 0;
for (let j = 0; j < num; j++){
temp += arr[i + j];
}
if (temp > max) {
max = temp;
}
}
return max;
}리팩토링 - 시간 복잡도- O(N)
function maxSubarraySum(arr, num){
let maxSum = 0;
let tempSum = 0;
if (arr.length < num) return null;
for (let i = 0; i < num; i++) {
maxSum += arr[i];
}
tempSum = maxSum;
for (let i = num; i < arr.length; i++) {
tempSum = tempSum - arr[i - num] + arr[i];
maxSum = Math.max(maxSum, tempSum);
}
return maxSum;
}
- Divide and Conquer
1. 이 패턴은 데이터 세트를 작은 덩어리로 나눈다음, 하위 집합을 이용해서 작업을 반복한다
2. 이 패턴은 시간 복잡도를 엄청나게 줄일 수 있다
예시문제1) 정렬된 배열인자와 정수를 인자로 받는데, 정수가 배열에서 위치하는 인덱스를 반환하는 함수를 만드시오. 정수가 배열에 존재하지 않다면 -1을 리턴한다.
search([1,2,3,4,5,6],4) // 3
search([1,2,3,4,5,6],6) // 5
search([1,2,3,4,5,6],11) // -1간단한 솔루션 - 선형 탐색 -> 시간복잡도 O(N)
function search(arr, val){
for(let i = 0; i < arr.length; i++){
if(arr[i] === val){
return i;
}
}
return -1;
}리팩토링 - 이진 탐색 - 시간복잡도 O(logN)
function search(array, val) {
let min = 0;
let max = array.length - 1;
while (min <= max) {
let middle = Math.floor((min + max) / 2);
let currentElement = array[middle];
if (array[middle] < val) {
min = middle + 1;
}
else if (array[middle] > val) {
max = middle - 1;
}
else {
return middle;
}
}
return -1;
}
- Dynamic Programming
- Greedy Algorithms
- Many more!
정리
1. 문제 해결 접근법 개발은 엄청 중요하다
2. 코드를 쓰기전에 먼저 생각하는것이 항상 문제를 빨리 풀 수 있게 만든다.
3. 문제 풀이 패턴을 항상 염두해 두자
4. frequency coutners, multiiple pointers, slding window, divide and conquer 패턴은 어려운 문제를 푸는데에 도움을 줄 뿐만 아니라 시간 복잡도와 공간 복잡도를 줄일 수 있다.