문제 해결 접근법

알고리즘이란?

• 알고리즘은 특정 작업을 달성하기 위한 과정이나 일련의 단계를 의미
• 알고리즘을 알아야 하는 이유?
  • 프로그래밍에서 수행하는 거의 모든 작업에는 아주 기본적이든, 복잡한 애플리케이션을 구축하든 일종의 알고리즘이 포함됨
  • 알고리즘은 성공적인 문제 해결 및 개발자가 되기 위한 기반
• 알고리즘을 잘 이해하려면?
  1. 문제 해결을 위한 계획을 수립하자!
  2. 일반적인 문제 해결 패턴을 파악하자!

문제 해결 절차

1. 문제를 이해하자!

• 시간적 제약이 있는 상황(코테, 면접)에서 대부분의 사람들은 문제를 해결하는 것에 초점을 둠
• 문제를 제대로 이해하지 못해도 진행은 할 수 있음
• but, 코드를 작성하기 이전에 한 걸음 물러서서 직면한 문제를 확실히 이해하는 것이 정말 중요!
• 문제를 확실히 이해하기 위해선?
  • 문제를 나만의 방식대로 새로 생각할 수 있는가?
  • 문제가 어떤 입력 값을 담고 있는가?
  • 어떠한 출력 값이 나와야 하는가?
  • 입력에서 출력을 결정할 수 있습니까? 즉, 문제를 해결할 수 있는 정보가 충분한가?
  • 문제에서 정말 중요한 부분이 무엇인가?
• 예시

  두 개의 숫자를 입력 받아 숫자의 합을 리턴하는 함수를 작성하라!

  1. 두 숫자를 더하자
  2. 두 개의 숫자가 입력 값(but, 두 숫자는 정수일 수도, 소수일 수도, 무한히 큰 숫자일 수도 있음)
  3. 두 숫자를 합한 값(but, 2번과 마찬가지로 리턴 값은 다양한 타입을 가질 수 있다!)
  4. 해당 문제에서는 두 숫자를 입력한다면 출력 값을 결정할 수 있겠지만, 만약 누군가가 하나의 값만 입력한다면? ➡︎ 상황에 따라 달라질 수 있음
  5. 두 입력 값과 출력 값이 이 문제에서 중요한 부분
     ➡︎ but, 문제가 복잡해질 수록 중요한 부분이 무엇인지 단계별로 생각하는 것이 차이를 만들 수 있다!

2. 구체적 예시를 탐색하자!

• 문제 해결에 대한 구체적 예시를 알고있다면 문제를 해결하는데 큰 도움이 될 수 있음

  • 예시를 알고 있으면 입력 값, 출력 값에 대해 알 수 있고 구현한 작업에 대해 확인을 해볼 수도 있음
  • User Stories(larger scale)
    • 개발자들은 어떤 값이 주어진 입력 값이고, 어떤 것이 출력 값인지, 사용자 작업인 입력 값을 제외하면 어떤 결과가 발생할 것인지를 고려함
    • 즉, User Story는 사용자 관점에서 작성한 소프트웨어의 일반적인 기능에 대한 명세
  • Unit Test(smaller scale)
    • 더 작은 기능에 대해 무언가가 어떻게 작동해야 하는지 그 틀을 잡는데 사용됨

• 구체적 예시를 탐색하려면?

  • 간단한 예시로 시작하자
    • 문제를 나만의 방식대로 새로 생각했다면, 입력 값과 출력 값의 순서대로 예시를 들어보자
  • 간단한 예시를 었다면 조금 더 복잡한 예시를 들어보자
  • 빈 입력 값과 같은 유효하지 않은 입력 값이 주어진 상황을 가정해보자

• 예시

  문자열을 입력받아 각 문자의 수를 리턴하는 함수를 작성하라!

  • 간단한 예시

    function charCount(str){
    		  return str의 각 문자의 수;
    }
    charCount('aaaa'); // -> {a: 4}
    charCount('hello'); // -> {h: 1, e: 1, l: 2, o: 1}

    • 위 코드에서 생각해봐야 할 점
      • 전달한 문자만 반환되어야 하나?
        • "aaaa"를 전달했을 때 {a: 4, b: 0, c: 0 ...} 이렇게 반환되면 안되는가? (이렇게 하면 코드가 더 쉬워질 것임)
  • 조금 더 복잡한 예시

    charCount("my phone number is 123456");
    charCount("Hello, Hi");

    • 입력 값이 위 코드와 같다면?
      • 공백은 어떻게 처리할 것인지, 문자와 다른 숫자나 기호 등은 어떻게 처리할 것인지, 대∙소문자를 구별할 것인지?
    • 복잡한 예시를 통해 문제를 보다 잘 이해할 수 있게 됨
  • 입력 값이 비어있거나 유효하지 않은 값이 들어간다면?

    charCount();
    charCount("");
    charCount(undefined);
    charCount({});

    - 면접과 코딩테스트와 같은 시간적 제약이 있는 상황에서는 위 상황을 고려하는 것은 크게 도움되지 X
    - 다만, 실무에서는 위와 같은 상황에 미리 대처하는 것이 중요!

    3. 문제를 세분화(break down)하자!

• 문제를 세분화한다는 것은 문제에 대한 단계들을 수립해서 실제로 수행하면서 작성을 하자는 의미

• 의사코드(psuedo code)를 꼭 작성할 필요도 없고 올바른 구문이 아니어도 상관 없음

• 문제를 해결하기 위한 단계를 작성할 때 역시 모든 라인을 작성할 필요도, 세세하게 작성할 필요도 X

  • 해결책의 기본 구성 요소만 작성하면 됨

• 문제를 세분화함으로써 코드를 실제로 작성하기 전에 난잡하게 코드를 대충 떠오르는대로 입력하는 것이 아니라 이해되지 않는 부분을 파악할 수 있게 해줌

• 예시

  2번과 마찬가지로 문자열을 입력받아 각 문자의 수를 리턴하는 함수를 작성하자

  • 입력 값과 리턴 값 판단

    function charCount(str){
      // do something
      // return -> 리턴할 때는 객체를 반환{key: 소문자, 숫자만 가능, value: 문자열에서 해당하는 문자의 수} 
    }

  • 원하는 리턴 값을 반환하기 위해 해야할 일 작성

    function charCount(str){
    // 리턴 할 객체 변수 생성
    // 문자열 길이만큼 루프를 돌면서 한 문자씩 처리
        // 문자열 내 문자가 숫자나 소문자이고 리턴 객체 내 key에 이미 들어있다면 count 1증가
        // 문자가 숫자나 소문자이고 리턴 객체 내 key에 들어있지 않다면 key를 추가하고 value를 1로 설정
        // 문자가 위에 해당하지 않는 다른 어떤 값(공백, 마침표 등)이라면 아무것도 하지 않음
    // 객체 리턴
    }

  • 위와 같이 문제를 해결하기 위한 주석을 잘 작성해두었다면 면접 시 주어진 문제를 코드로 작성하지 못하였더라도 문제에 대한 기본적인 방향, 개념은 잡을 수 있음
    4. 코드를 작성하거나 문제를 단순화하자

• 위 세 과정을 통해 문제를 해결했다면 바로 코드를 작성할 수 있음

• but, 아직 문제를 모두 해결하지 못했다면? 문제를 단순화 하자

• 단순화의 의미: 다른 중요한 부분에 집중하기 위해 시간이 많이 소요되는 부분을 무시하자

• 단순화를 하면 좋은점

  • 코드를 작성하기도 전에 문제를 한 곳에 집중해서 해결하려 하면 문제의 어려운 부분에 가로막혀 진도를 나가지 못함
  • 어려운 부분에 가로막힌다해도 이 부분을 결국에는 다른 부분과 통합해야한다는 것을 염두에 두고 가능한 작업을 먼저 수행하기 위해 코드를 작성하는 것이 훨씬 좋음
  • 문제를 단순화하는 과정에서 문제의 어려운 부분을 파악하고 점차 해결해 나갈 수도 있음

• 어떻게 문제를 단순화를 할까?

  • 문제의 핵심적인 어려운 부분 찾자
  • 일단은 어려운 부분을 무시하고 단순한 해결책을 찾자
  • 그런 다음 찾은 해결책과 어려운 부분을 통합시키자

• 예시

  또 다시 문자열을 입력받아 각 문자의 수를 리턴하는 함수를 작성해보자
  주석을 잘 작성해뒀으나, 소문자 대문자를 어떻게 처리하는지 기억이 나지 않는다면?
  또는, 객체를 사용해본 적이 없다면?
  반복문을 사용하는데 어려움이 있다면?

  • 위와 같은 상황이 실전에서 발생한다면 일단은 어려운 상황을 무시하고 기본 로직부터 시작해서 위 상황을 나중에 처리하자
  • 기본 로직

    function charCount(str){
      let result = {};
      for(let i = 0; i < str.length; i++){
        let char = str[i];
        if(result[char] > 0){ // 문자열이 리턴 객체에 있는지?
          // 있으면 value를 1 증가
          result[char]++;
        } else {
          // 없으면 key = char, value = 1로 설정
          result[char] = 1;
        }
      }
      // 객체 리턴
      return result;
    }

  • 위 로직에서 "문자열 내 문자가 소문자이고"를 통과하기 위해 문자열 내 문자를 소문자로 만들어 주자!

    function charCount(str){
      let result = {};
      for(let i = 0; i < str.length; i++){
        let char = str[i].toLowerCase(); // 문자를 소문자로 만들어주는 toLowerCase() 메소드 활용
        if(result[char] > 0){ // 문자열이 리턴 객체에 있는지?
          // 있으면 value를 1 증가
          result[char]++;
        } else {
          // 없으면 key = char, value = 1로 설정
          result[char] = 1;
        }
      }
      // 객체 리턴
      return result;
    }

• 위 과정을 통해 거의 문제의 90% 해결 but, 아직 해결 못한 부분이 존재

5. 되돌아보기 & 리팩토링

• 위 과정을 통해서 문제의 90% 이상을 해결해서 필요한 작업을 수행할 수 있다면 당장 노트북을 덮고 취미 생활을 하고싶을 것임
• 내가 작성한 코드가 지구상에서 가장 아름답고 효율적일 필요는 없지만, 목표를 달성하기 위해 노력하는 것은 정말 중요!
• 목표를 달성한다는 것은 작성한 코드가 얼마나 이해하기 쉬운지, 얼마나 효율적인지에 관해 논의하는 것을 의미
  • 즉, 효율성과 가독성 사이에서 균형을 잘 맞출 수록 목표를 더욱 가깝게 달성한 코드!
• 리팩토링 과정에서 자신에게 다음과 같은 질문을 물어볼 수 있음
  • 결과를 확인할 수 있는가?
  • 결과를 다른 방식으로 도출할 수 있는가?
  • 한 눈에 보고 이해할 수 있는가?
  • 결과나 방법을 다른 문제에도 적용할 수 있는가?
  • 문제 해결책의 성능을 향상시킬 수 있는가?
  • 다른 사람들은 이 문제를 어떻게 해결하는가?
• 예시

  위에서 아직 해결하지 못한 부분(숫자 판단)을 해결하자!

  function charCount(str){
    let obj = {};
    for(let i = 0; i < str.length; i++){
      let char = str[i].toLowerCase();
      if(/^[a-z0-9]$/.test(char)){ // 문자열 내 문자가 숫자나 소문자인지?
       	if(obj[char] > 0){ // 맞다면 리턴 객체 내 key에 이미 들어있는지?
  			// 리턴 객체 내 key에 이미 들어있다면 count 1증가
        	obj[char]++;
        }
       	else {
  	        // 없으면 key = char, value = 1로 설정
        	obj[char] = 1;
      	}
       // 문자가 위에 해당하지 않는 다른 어떤 값(공백, 마침표 등)이라면 아무것도 하지 않음
      }
    }
    // 객체 리턴
    return obj;
  }

  • 위 코드에서 개선 시킬 점
    • for loop ➡︎ 문제에서 원하는 것은 문자열 내 문자 but, for loop를 쓰면 숫자를 받아 개별 문자로 바꾸는 불필요한 단계가 추가됨
      - for loop ➡︎ for - of로 바꿀 수 있음

       function charCount(str){
         let obj = {};
         for(let char of str){
           char = char.toLowerCase();
           if(/^[a-z0-9]$/.test(char)){ // 문자열 내 문자가 숫자나 소문자인지?
             if(obj[char] > 0){ // 맞다면 리턴 객체 내 key에 이미 들어있는지?
               // 리턴 객체 내 key에 이미 들어있다면 count 1증가
               obj[char]++;
             }
           else {
             // 없으면 key = char, value = 1로 설정
             obj[char] = 1;
           }
         // 문자가 위에 해당하지 않는 다른 어떤 값(공백, 마침표 등)이라면 아무것도 하지 않음
        }
      }
       // 객체 리턴
       return obj;
      }

    • 객체에 있는 값을 1증가시키거나 초기화하는 것은 간단한 작업 조건문을 굳이 사용 할 필요 X

      //   if(obj[char] > 0){ // 맞다면 리턴 객체 내 key에 이미 들어있는지?
          // 리턴 객체 내 key에 이미 들어있다면 count 1증가
      //     obj[char]++;
      //   }
      //   else {
          // 없으면 key = char, value = 1로 설정
      //     obj[char] = 1;
      //   }
      obj[char] = ++obj[char] || 1; // obj[char]이 truely한 값이면 obj[char] 을 1증가 falsy 값이면 1로 초기화 

    • 자바스크립트에서는 정규 표현식이 수행 중인 작업과 사용 중인 브라우저에 따라 성능이 달라질 수 있음
      • but, 패턴을 찾기에 가장 쉬운 방법이므로 정규 표현식을 사용
      • 하지만 더 나은 방법이 존재 할 수 있음(ex) string.charCodeAt() 메소드)
        정규표현식과 charCodeAt 시간 비교
    • 영소문자로 바꾸는 위치
      • 입력 받는 모든 문자열을 소문자로 바꾸기보단, 영소문자와 소문자만 필터링 한 문자를 소문자로 바꾸는 것이 더 효율적!

문제 해결 패턴

1. Frequency Counter

• 이 패턴은 자바스크립트의 객체를 사용해서 다양한 값과 빈도를 수집하는 것을 목표로 함
• 서로 비슷한 값으로 구성되어있는지, 애너그램 관계인지, 어떤 값이 다른 값에 포함되어있는지 여부를 비교하거나, 데이터를 입력 값이나 두 개 이상의 빈도 혹은 특정하게 발생하는 빈도와 비교할 때 유용함
• 배열, 문자열을 사용해서 중첩 루프나 $O(N^2)$의 복잡도를 요구하는 작업을 피할 수 있음
• 예시

  첫 번째 배열의 모든 요소가 두 번째 배열의 제곱 값에 해당하는 경우 true를 반환하는
  same(arr1, arr2) 함수를 작성해라. (순서는 섞여도 상관X 단, 요소의 개수는 동일해야 함)
  ex) same([1, 2, 3], [4, 1, 9]) ⇒ true
  same([1, 2, 3], [1, 9]) ⇒ false
  same([1, 2, 1], [4, 4, 1]) ⇒ false

  • $O(N^2)$ solution

    function same(arr1, arr2){
      if(arr1.length !== arr2.length){
        return false;
      }
      
      arr1.forEach((ele, idx) => {
        let correctIdx = arr2.indexOf(ele * ele)){
           if(correctIdx < 0){
    					return false;
    			 }
           arr2.splice(arr2_idx, 1);
        }
      });
      return true;
    }

    • forEach문을 이용해 arr1의 요소를 하나씩 뽑아서 $요소^2$ 값이 arr2에 있는지 확인해서 있으면 splice 메소드를 사용해 해당 요소를 arr2에서 제거하고 없으면 false를 반환함
    • 루프를 다 돌았는데도 return이 안됐다면 true 반환
  • $O(N)$ solution(frequency counter)

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

    • 각 배열 요소들이 몇 번 나타났는지를 frequencyCounter에 저장
    • 루프를 통해서 arr1의 제곱 값이 arr2에 있는지, arr2에 있는 요소 각각의 개수와 arr1에 있는 요소 각각의 개수가 일치하는지

• 성능 평가
  • n = 1000(배열의 길이), 일 때, frequency counter를 쓴 코드는 3000번의 반복, counter를 쓰지 않은 코드는 최악의 경우 $1000^2$ 의 반복이 일어남
  • 이처럼 객체를 사용하여 프로파일을 구성하면 배열 간의 비교, 문자열 간의 비교를 빠르게 할 수 있음

2. 다중 포인터 패턴

• 인덱스나 위치에 해당하는 포인터나 값을 만든 다음 특정 조건에 따라 중간 지점에서부터 시작 지점이나 끝 지점이나 양쪽 지점을 향해 이동시키는 것을 목표로 함
• 배열이나 문자열과 같은 선형 구조에 단일 연결리스트, 이중 연결리스트와 같은 패턴을 만드는 것
• 한 쌍의 값이나 조건을 충족시키는 무언가를 찾을 때 유용함
• 예시 1

  두 숫자의 합이 0인 첫 번째 쌍을 리턴하고, 만약 합계가 0인 쌍을 찾지 못했다면
  undefined를 리턴하는 sumZero라는 함수를 작성하자

  제한사항: *단, 입력 값은 배열이며, 배열은 오름차순 정렬되어 있다.*

  • ex)

  sumZero([-3, -2, -1, 0, 1, 2, 3]); // [-3, 3]
  sumZero([-2, 0, 1, 3]); // undefined
  sumZero([1, 2, 3]); // undefined

  • $O(n^2)$ solution

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

    • 반복문을 통해 i 번째 인덱스 값이랑 i 다음 인덱스 값을 비교해가며 계속 반복하는 코드
    • 배열이 길어진다면 시간 소요 ↑
  • $O(n)$ solution

    function sumZero(arr) {
      let first = 0;
      let last = arr.length - 1;
      while(first < last){
        if(arr[first] + arr[last] < 0){
          first++;
        } else if(arr[first] + arr[last] > 0){
          last--;
        } else{
          console.log(arr[first], arr[last]);
          return [arr[first], arr[last]];
        }
      }
      
    }

    • 배열이 정렬되어있다는 점을 이용
      1. 배열의 처음과 끝 인덱스를 지정하고 두 값을 더해나가면서
         • 합한 값이 크다면 끝 인덱스를 -1
         • 합한 값이 작다면 앞 인덱스를 +1
         • 합한 값이 0이라면 두 값을 리턴
      2. 처음 인덱스가 끝 인덱스보다 작을 때까지만 반복
         • 만약 같아질 때 까지 반복 한다면 sumZero([-2, -1, 0 , 5 ,10]); 를 실행했을 때 리턴 값이 undefined가 아닌 [0, 0]이 리턴됨

• 예시 2

  배열에서 중복을 제외한 값의 개수를 계산하는 countUniqueValues 함수를 작성하자

  ***제한사항: 단, 입력 값은 배열이며, 배열은 오름차순 정렬되어 있다.***
  
  - ex)

  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]) // 4

  • my Solution

    /* 1. Set의 특성을 이용해서 중복 제거 */
    function countUniqueValues(arr){
      arr = [...new Set(arr)];
      return arr.length;
    }
    
    /* 2. 배열의 이전 요소와 다음 요소를 비교하면서 다른 값이면 count 증가 */
    function countUniqueValues(arr){
    	let count = 1;
    	let cmp = arr[0];
      if(!arr.length){
          return 0;
      }
      for(let i = 1; i < arr.length; i++){
          if(arr[i] !== cmp){
              cmp = arr[i];
              count++;
              console.log(`arr: ${arr[i]}, count: ${count}`);
          }
      }
      return count;
    }

  • 다중 포인터 사용

    function countUniqueValues(arr){
    	let i = 0;
    	if(!arr.length){
    		return 0;
    	}
    	for(let j = 1; j < arr.length; j++){
    		if(arr[i] !== arr[j]){
    			i++;
    			arr[i] = arr[j];
    		}
    	}
    	return i + 1;
    }

    • i 인덱스 = 고유 값 개수를 구하기 위한 인덱스
    • arr이 빈 배열이면 0을 리턴
    • 비어있지 않았다면, loop를 돌면서 i번째 요소와 j 번째 요소를 비교
      • 같지 않다면, i를 1 증가시키고 i번째 arr 요소를 j번째 arr 요소로 바꿈
    • loop가 완료되면 i 번째까지의 배열은 고유한 값을 갖는 배열이므로 배열의 길이인 i + 1을 리턴

3. 슬라이딩 윈도우 패턴

• 배열이나 문자열과 같은 일련의 데이터를 입력하거나 특정 방식으로 연속적인 해당 데이터의 하위 집합을 찾는 경우에 유용한 패턴
  • 예를 들어, "hellothere"에서 중복된 값을 가지지 않는 가장 긴 문자열을 만든다고 하면
    "lother"이 가장 긴 문자열이 됨
• 창문을 하나 만들고(창문은 단일 변수, 하위 배열 또는 다른 문자열이 될 수도 있음) 조건에 따라 창문을 이동시키자
• 창문은 보통 시작 위치에서 끝나는 위치로 이동함(반대가 될 수도, 가운데에서 끝날 수도 있음)
• 예시

  배열에 있는 $n$개의 연속된 요소들의 최댓값을 구하는 maxSubarraySum 함수를 작성해라

  ex)

   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) // null

  • solution 1.

    function maxSubarraySum(arr, num){
    	if(num > arr.length){
       	return null;
       }
       let 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;
    }

    • 이중 loop를 돌면서 내부 loop 에서는 num횟수 만큼 배열의 요소를 더하고
      max랑 비교해서 max보다 크다면 max를 더한 값으로 바꿔주는 코드
    • 문제점: 이중 loop를 돌기 때문에 arr의 길이가 길어지면 길어질 수록 효율성 ↓
  • Refactoring

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

    • 리팩토링한 코드는 위에서 처럼 이중 loop를 돌면서 값을 더하지 않음
    • 배열의 첫 요소부터 num - 1번째 인덱스 까지의 값을 더해둔 뒤, 더한 값의 가장
      앞 요소를 빼고 그 다음 요소를 차례대로 더해가면서 최댓값을 찾는 방식

4. 분할 정복 패턴

• 이 패턴은 데이터 셋을 더 작은 덩어리로 나눈 다음 데이터 하위 집합으로 프로세스를 반복하는 것을 의미
• 즉, 나눈 데이터 중 필요 없는 덩어리는 과감하게 버림
• 이 패턴은 시간 복잡성을 크게 줄일 수 있음
• 예시 1

  입력 값이 입력된 정수 배열에 있는지 확인하는 search 함수를 작성해라.
  값이 있다면 해당 값이 있는 배열의 인덱스를 리턴하고, 없다면 -1을 반환한다.

  제한사항: 입력 값은 정수이며, 입력된 배열은 정렬된 상태이다.

  ex)

      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

  • 일반적인 solution

     function search(arr, val){
       for(let i = 0; i < arr.length; i++){
         if(arr[i] === val){
            return i;
         }
       }
       return -1;
     }

    • 배열 첫번째 요소 부터 val과 비교하면서 값이 같다면 배열의 해당 인덱스 리턴,
      없다면 -1 리턴
  • refactor(binary search!)

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

    • 중간 값$((min + max)\ /\ 2)$을 찾은 다음 val과 비교 했을 때, 큰 값이면 중간 값보다 작은 값은 탐색하지 않아도 되므로 min을 중간 값 + 1, val보다 작으면 중간 값보다 큰 값은 탐색하지 않아도 되므로 max를 중간 값 - 1
    • 위 과정을 min이 max보다 작거나 같을 때까지만 반복
    • 반복문이 끝났는데도 리턴하지 않았다면 -1을 리턴