문제 해결 접근법과 문제해결패턴

KoEunseo·2022년 9월 17일

algorithm

목록 보기

3/8

04 문제해결접근법

알고리즘?

특정 작업을 달성하기 위한 과정이나 일련의 단계를 의미한다.
문제해결 접근법을 계획
일반적인 문제 해결 방법을 마스터

문제를 이해
구체적 예시
문제 세분화
문제 해결, 단순화
문제 복습, 리팩토링

1단계: 문제를 이해한다.

내 방식으로 바꿔서 다시 생각할 수 있어야 한다.
문제가 어떤 input을 담고 있는가를 이해한다.
어떤 output이 나와야하는가
입력값이 출력값으로부터 결정되는가? 문제를 해결하기 위한 충분한 정보가 있는지.
문제의 일부인 데이터의 중요한 부분에 어떻게 label을 지정할 수 있을지(이 문제에서 제일 중요한 것이 무엇인지)

2단계: 구체적 예제들

입력값과 출력값의 순서대로 예시를 두세개 작성해본다.
처음에는 간단한 예시를 생각해보고 복잡한 예시로 발전시켜본다.
경곗값 분석을 해본다. (빈 입력값 + 유효하지 않은 입력값 등)

3단계: 세부 분석

문제를 세분화한다.
어떻게 문제를 풀어나갈것인지 면접관에게 이야기한다. 힌트를 줄지도 모른다ㅎ
기본적인 구성
수도코드를 써서 과정을 보여준다. 코드를 완성하지 않아도 괜찮다.

4단계: 해결, 단순화

모든 문제를 해결하려하기보다 단순화해서 문제를 해결하기 시작한다.
어려운 부분을 무시하고 단순한 해결책을 찾는다. 그다음에 가능하다면 어려운 부분을 통합시킨다.

5단계: 되돌아보고 리팩토링

결과를 다른방식으로 해결할수있는지
한눈에 보고 이해할 수 있는지? 직관적인지
다른 문제에도 사용할 수 있을까? 다른 문제와의 유사점을 생각해본다.
성능을 향상시킬 수 있는지? 시간복잡도/공간복잡도
다른사람들은 어떻게 문제를 푸는지?

for문은 숫자를 문자로 변환하는 불필요한 과정이 필요하다.
for of는 문자를 바로 반환하니까 먼가 더 효율적인듯. 사실 효율이라기보다 직관적으로 이해하기 좋다.
if와 else를 쓰기보다 ||를 사용하면 한줄에 끝낼수도 있다.
예를 들어

if(obj[char] > 0){
  obj[char]++;
} else {
  obj[char] = 1;
}
//을 아래 한줄로 바꿀 수있음
obj[char] = ++obj[char] || 1;
//true면 obj[char]++ 하고 false면 1값을 줌

05 문제해결패턴

frequncy counters : 객체 사용

중첩된 루프는 사용하지 않는 것이 좋다.

for(){
  for(){}
  //중첩된 루프를 사용하는 메서드 또한 마찬가지임
}

보다 :n^2

for(){}
for(){}

이 낫다!! :2n

애너그램

입력: 두개의 str을 받는다.
출력: 입력받은 str이 서로 애너그램 관계인지에 대한 여부를 출력한다.

내 코드
function validAnagram(str1, str2){
  // add whatever parameters you deem necessary - good luck!
  if(str1.length !== str2.length) return false;
  str1 = str1.split('').sort().join();
  str2 = str2.split('').sort().join();
  if(str1 !== str2) return false;
  return true;
}
아 제목이 카운터인데 카운터를 안썼닼ㅋㅋㅋㅋㅋ
마음이 급해가지구... 담에 다시 카운터로 써보자.
사실 카운터+객체를 써보려고 하긴 했는데, 객체가 너무 어렵다... 안써버릇해서
맨날 배열로 재가공해서 문제품...ㅠㅠ
객체에 익숙해질 수 있도록 최대한 사용해보는 쪽으로 데일리코딩을 풀어봐야지.

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

for문 중첩보다는
while문에 포인터 2개를 설정해서 사용하는 게 좋다.

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--;}
}

내 코드

function countUniqueValues(arr){
  let result = {};
  for(let el of arr){
    result[el] = el || 1;
  }
  return Object.keys(result).length;
}

function countUniqueValues(arr){
    if(arr.length === 0) return 0;
    var i = 0;
    for(var j = 1; j < arr.length; j++){
        if(arr[i] !== arr[j]){
            i++;
            arr[i] = arr[j]
        }
    }
    return i + 1;
}
countUniqueValues([1,2,2,5,7,7,99])