자바 스크립트 알고리즘 기초 - jaba seukeulibteu algolijeum gicho

누구나 알고리즘으로
문제 해결 능력을 키울 수 있다!

준비 | 학습에 필요한 내용 준비하기
알고리즘이 무엇인지 정의와 개념을 살펴보고 범용성, 정당성 등 알고리즘이 만족해야 하는 기본 조건을 알아봅니다.

기초 | 기초 알고리즘 배우기
나눗셈, 원주율 계산, 웹 검색, 길 찾기, 음성 조작, 정렬, 문자열 압축 및 해제, 문자열 암호화, 디지털 인증서 살펴보기 등 다양한 실습을 통해 일상 속에서 찾아볼 수 있는 알고리즘을 배웁니다. 마당별로 핵심 정리와 연습 문제까지 준비되어 있어 기초 핵심 알고리즘을 완벽하게 공부할 수 있습니다.

심화 | 이미지 처리 알고리즘부터 머신 러닝, 신경망까지
기초 알고리즘에서 더 나아가 이미지 처리 알고리즘, 최근 주목받고 있는 머신 러닝, 신경망까지 살펴봅니다.

다음 분에게 추천합니다!
- 알고리즘을 처음 배우는 분
- 알고리즘을 통해 사고력과 문제 해결력을 키우고 싶은 분
- 세상에 넘쳐나는 IT 기술 속에 숨겨진 알고리즘을 알고 싶은 분
- 알고리즘 입문서를 읽었는데 어려워서 이해할 수 없는 분

문제

현수네 반 선생님은 반 학생들의 수학점수를 향상시키기 위해 멘토링 시스템을 만드려 한다.
멘토링은 멘토(도와주는 학생)와 멘티(도움을 받는 학생)가 한 짝이 되어 멘토가 멘티의 수학공부를 도와주는 것이다..
선생님은 M번의 수학테스트 등수를 가지고 멘토와 멘티를 정한다.
만약 A학생이 멘토이고, B학생이 멘티가 되는 짝이 되었다면, A학생은 M번의 수학테스트에서 모두 B학생보다 등수가 앞서야 한다..
M번의 수학성적이 주어지면 멘토와 멘티가 되는 짝을 만들 수 있는 경우가 총 몇 가지 인지 출력하는 프로그램을 작성하라.

입력 설명

M개의 줄에 걸쳐 수학테스트 결과가 학생번호로 주어진다. 학생번호가 제일 앞에서부터 1등, 2등, ...N등 순으로 표현된다.
만약 N=4이고, 테스트 결과가 3 4 1 2로 입력되었다면 3번 학생이 1등, 4번 학생이 2등, 1번 학생이 3등, 2번 학생이 4등을 의미한다.

3 4 1 2
4 3 2 1
3 1 4 2

데이터가 다음과 같은 형태로 주어진다.

출력 설명

짝을 만들 수 있는 총 경우의 수를 출력하시오.

내 풀이

1. A학생이 B학생보다 주어진 M가지 테스트 모두 등수가 높아야 한다.
   • 0번 인덱스가 1등을 의미하므로, 멘토가 되는 A학생의 인덱스가 더 작은 값을 가진다.
   • 1번 멘토와 2번 멘티의 관계를 (1, 2)로 표현하면, (N, N)만큼 즉 N * N 횟수를 순회하고,
     한번 순회할 때 그 안에서 M가지 테스트에 대해 모두 조사하고 모두 조건을 만족할 때만 멘토-멘티 관계가 성립한다.

function solution(test){
  let answer = [];
  const m = test.length;
  const n = test[0].length;

  for(let i = 1; i<=n; i++){
    for(let j = 1; j<=n; j++){
      if(i===j) continue;
      let cnt = 0;
      for(let k = 0; k<m; k++){
        let gi = gj = 0;
        for(let s = 0; s<n; s++){
          if(test[k][s] === i) gi=s;
          if(test[k][s] === j) gj=s;
        }
        if(gi < gj) cnt++;
      }
    if(cnt === m) answer.push([i, j]);
    }
  }
  return answer;
}

let arr = [[3,4,1,2], [4,3,2,1], [3,1,4,2]];
console.log(solution(arr));

• m, n은 각각 테스트 횟수, 학생 수를 의미한다.
• i학생과 j학생의 멘토-멘티 관계를 알기 위해 2중 for문을 사용한다.
  • i학생은 j학생의 멘토-멘티 관계가 될 수 없기 때문에 i=j일 때는 넘어간다.
  • (i,j)의 멘토-멘티 관계를 조사할 때 m개의 테스트를 모두 조사해야 하므로 m회 반복을 해준다.
    • 그리고 각 테스트의 i,j 학생의 위치를 찾고, 찾은 인덱스를 gi, gj 변수에 넣어준다.
    • 이 때 gi, gj에 배정된 인덱스 값이 작을수록 더 등수가 높으므로(0번 인덱스는 1등, 1번 인덱스는 2등을 의미하므로)
      gi의 인덱스 값이 gj의 인덱스 값보다 m번 작으면 된다.
  • 이 조건을 만족하는 (i, j)의 관계만 정답 배열에 넣어준다.

결과적으로 (3, 1), (3, 2), (4, 2) 의 3가지 경우의 수가 멘토-멘티 관계를 만족한다.

Array.indexOf를 이용해보자.

위와 같이 2중 for문을 사용하는 것은 어쩔 수 없다고 하더라도, 그 내부에서 for(k), for(s)까지 쓰는 것이 싫다면
배열에서 제공하는 메서드를 사용해 볼 수 있다.

Mozilla Docs에 따르면 indexOf는 배열 내에서 찾고싶은 값의 인덱스를 찾아준다.

위의 코드를 가져와 해당 메서드만 적용해보면,

function solution(test){
  let answer = [];
  const m = test.length;
  const n = test[0].length;

  for(let i = 1; i<=n; i++){
    for(let j = 1; j<=n; j++){
      if(i===j) continue;
      let cnt = 0;
      for(let k = 0; k<m; k++){
        const gi = test[k].indexOf(i)
        const gj = test[k].indexOf(j)
        if(gi < gj) cnt++;
      }
    if(cnt === m) answer.push([i, j]);
    }
  }
  return answer;
}

let arr = [[3,4,1,2], [4,3,2,1], [3,1,4,2]];
console.log(solution(arr));

다음과 같이 사용하면 된다.

유의할 점

indexOf 메서드는 2번째 인자로 fromIndex를 받는데, 이 인자 값을 설정하지 않으면 기본값 0을 가진다.
그렇게 되면 배열의 처음부터 찾고자하는 값을 찾아나가는데, 처음으로 값이 발견되면 그 즉시 인덱스를 반환하고 종료된다.
만약 [1,2,3,1,1,3] 등과 같이 두번째 1을 찾고 싶다면?
fromIndex의 값을 부여해서, 찾는 시작점을 설정해주면 된다.

만약 indexOf만을 고집해서 모든 1의 인덱스를 사용하고 싶다면

const arr = [1,2,3,1,1,3];
const indexArr = [];
let idx = 0;

while(true){
  idx = arr.indexOf(1, idx);
  if(idx === -1) break;
  indexArr.push(idx++);
}

다음과 같이 배열의 처음부터 1의 index를 찾는다.
그 값을 idx 변수에 저장한다.
만약 idx가 -1일 때 (indexOf 메서드는 찾고자 하는 값이 존재하지 않을 때 -1을 반환한다) while문을 탈출한다.
idx가 -1이 아니라면, indexArr 배열에 idx값을 넣어주고, idx를 1 증가시키면 된다.
- 발견한 인덱스 그 다음 인덱스부터 찾아야한다.

느낀점

사실 문제를 처음 봤을 때 indexOf 메서드에 대한 생각이 먼저 났던 것이 사실이다.

그러나 만약 "메서드를 쓰지 말고 반복문으로만 구현해 보세요." 라는 추가적인 조건이 달린다면?
사실 메서드를 쓰지 않고 구현한 첫번째 코드를 보면 생각보다 간단하지만, 또 생각보다 어렵기도 하다.
간편한 방법을 알고, 상황이 허락하면 사용하는 것이 최선이지만 더 어떻게 구현할지를 이해하고 있어야 한다.

최신의 문법인 spread operator(...) 등의 화려한 스킬을 사용할 수 있으나,
정작 배열을 순회하는 방법도 잘 모른다면, 곱하기를 모르는 슈퍼 주인이 계산기가 알려주는데 왜 곱셈을 배워? 하는 것과 다를바가 없다.

예쁜 메서드를 이용해서 예쁘게 푸는 것도 좋다.
하지만 메서드 없이 구현이 가능해 보이는 문제에 대해서는 코드가 길어지더라도 일을 수행해보면,
기본을 더 단단하게 하는 데 도움이 많이 될 것 같다.

공유하기

게시글 관리

저작자표시

'DS & Algorithm > basic' 카테고리의 다른 글