이정훈

이정훈

기록을 습관화하자

0726 - 0801

0726

11일 차 자료구조 / 알고리즘 정리

오늘부터 새로운 국면으로 들어섰다.
이제는 실제로 학원을 통학하여 자료구조 알고리즘을 듣기 시작했고, 처음으로 사람들도 만났다. 통학을 하는 건 장단점이 있는데, 왔다갔다 하는 데 시간과 체력이 많이 소요되고, 점심 저녁을 밖에서 해결해야 한다는 점이 골치거리다. 하지만 그만큼 수업을 듣는 데에 있어서 집중이 되었고, 자체적으로 쉬는 시간을 갖는 시간이 많이 줄어들었다. 처음 수업을 듣고 느낀 점은 정말 진도가 빠르고, 한 번이라도 집중력을 잃거나 복습 예습을 꼼꼼히 하지 않으면 그대로 뒤쳐지겠다는 것이었다.
하지만 또 다른 점으로는 생각보다 내가 공부한 거에 비해 (비록 쉬운 난이도기는 했지만) 코딩테스트를 수월하게 해결하고, 문제를 해결하는 사고력이 있다고 느꼈기 때문에 재미있었다. 이번주와 다음주를 정말 이악물고 예습, 복습을 철저히 해서 이번 수업을 기반으로 코딩테스트 능력을 쭉 길러가야겠다고 생각했다.

알고리즘

숫자통일

0과 1로 구성된 문자열이 주어지면 현수는 연속된 1이상의 구간을 뒤집어 전체를 하나의 숫자로 통일하려고 합니다.
여기서 뒤집는다는 0을 1로 또는 1을 0으로 바꾸는 것을 의미합니다.
만약 문자열이 100001111이 주어지면 현수는 2번째부터 5번째까지는 뒤집어 111111111로 통일할 수 있습니다.
문자열이 주어지면 현수가 최소 몇 번만에 숫자을 통일할 수 있는지 찾아주세요.

function solution(s) {
  let answer;
  let zero = 0;
  let one = 0;

  s[0] === "0" ? zero++ : one++;

  for (let i = 1; i < s.length; i++) {
    if (s[i] !== s[i - 1]) {
      if (s[i] === "1") {
        one++;
      } else {
        zero++;
      }
    }
  }
  answer = zero > one ? one : zero;

  return answer;
}

console.log(solution("100001111"));
console.log(solution("10010111100"));
  • zero와 one이라는 카운트 변수를 선언하고 문자열의 첫 번째가 0인지 1인지를 먼저 확인해서 카운트를 증가시켰다.
    • 여기서 실수한 게 있는데, 문자열에서 인덱스로 꺼내온 것은 당연히 문자열임을 주의하자!
  • 내가 기존에 푼 방법과 개념은 비슷하다. 하지만 나는 객체를 선언해서 문제를 해결하였고, 배운 방법은 변수로 카운트를 세서 문제를 해결했다.

상태변화

0과 1로 구성된 문자열이 주어지면 현수는 자신이 목표한 상태로 바꾸려고 합니다. 현수가 목표한 상태로 바꾸기 위해 할 수 있는 동작은 2가지입니다.

  1. 문자열에서 임의로 0과 1 두 개를 선택해 서로 위치를 교환한다.
  2. 문자열에서 임의로 0또는 1 한 개를 선택해 뒤집는다. 여기서 뒤집는다는 것은 0은 1로 1 은 0으로 바꾸는 것을 의미합니다.

만약 초기상태가 11000111문자열이 주어지고, 목표상태가 11100110인 문자열이 주어지면 초기상태의 3번째 0과 8번째 1을 서로 위치 교환하면 1번만에 목표상태가 됩니다.
문자열의 초기상태와 목표상태가 주어지면 현수가 목표상태를 이루는데 최소횟수를 구하는 프로그램을 작성하세요.

function solution(s1, s2) {
  let answer;
  let zero = 0;
  let one = 0;

  for (let i = 0; i < s1.length; i++) {
    if (s1[i] !== s2[i]) {
      s1[i] === "0" ? zero++ : one++;
    }
  }

  answer = zero > one ? zero : one;

  return answer;
}

console.log(solution("11000111", "11100110"));
console.log(solution("11000111", "11111110"));
  • 1번 문제와 마찬가지로 배운 방법에서는 카운트 변수를 선언해서 문제를 해결했고, 내가 푼 방법은 객체를 사용해서 문제를 해결했다.
  • 다만 내가 풀 때는 문자의 인덱스로 접근을 문자열.charAt(index) 방식으로 했는데, 확실히 문자열[index] 방법이 보기도 좋고 쓰기에도 쉬워보인다. 이 방법으로 문자에 접근해야겠다.

접미사 정렬

문자열 s가 주어지면 s문자열의 모든 접미사를 구하고 사전순으로 출력하는 프로그램을 작성하세요.

function solution(s) {
  let answer = [];

  for (let i = 0; i < s.length; i++) {
    answer.push(s.substring(i, s.length));
  }

  answer.sort();

  return answer;
}

console.log(solution("kseaedu"));
  • 문자열의 접미사에 접근해서 빈 배열에 push하는 방법으로 모든 접미사를 구했다.
    • 여기서 substring()은 문자열에서 특정 인덱스에 위치한 문자열을 꺼내올 때 유용한 메서드이다.
    • 첫 번째 매개변수에는 시작하는 인덱스, 두 번째 매개변수에는 끝나는 인덱스(해당 인덱스는 포함 안함)를 설정한다.
    • 두 번째 매개변수를 설정하지 않으면 시작하는 인덱스부터 끝까지 자른다.
  • 그리고 배열을 sort()하여 사전 순으로 정렬하였다.

공통문자가 없는 단어

N개의 문자열이 주어지면 서로 공통문자가 없는 두 문자열을 선택해 두 문자열의 길이를 곱했 을 때 최댓값을 출력하는 프로그램을 작성하세요.

function isUnique(short, long) {
  for (let x of short) {
    if (long.indexOf(x) !== -1) {
      return false;
    }
  }
  return true;
}

function solution(words) {
  let answer = 0;

  for (let i = 0; i < words.length - 1; i++) {
    for (let j = i + 1; j < words.length; j++) {
      if (isUnique(words[i], words[j])) {
        let result = words[i].length * words[j].length;
        answer = Math.max(answer, result);
      }
    }
  }

  return answer;
}

console.log(solution(["skudy", "kstue", "time", "back", "good"]));
console.log(solution(["kk", "k", "kkk", "kkkkk", "kkkk"]));
  • 같은 개념으로 문제를 풀었지만, 나는 4중 반복문을 이용해서 문제를 해결했는데 따로 isUnique() 함수를 구현해서 코드를 짜니 훨씬 가독성이 좋았다.
  • 두 값 중 큰 값이나 작은 값을 비교할 때, Math.max(값1, 값2)를 사용하면 더 깔끔하게 코드를 구현할 수 있을 것 같다.

회문문자열 2

문자열 s가 주어지면 s가 최대 문자 1개까지 지워서 회문문자열이 되면 “YES”를 출력하고, 그렇지 않으면 ”NO”를 출력하는 프로그램을 작성하세요.

function solution(s) {
  let answer = "YES";
  let lt = 0;
  let rt = s.length - 1;

  while (lt < rt) {
    if (s[lt] !== s[rt]) {
      let s1 = s.substring(lt, rt);
      let s2 = s.substring(lt + 1, rt + 1);
      if (
        s1.split("").reverse().join("") !== s1 &&
        s2.split("").reverse().join("") !== s2
      ) {
        answer = "NO";
      }
      break;
    } else {
      lt++;
      rt--;
    }
  }

  return answer;
}
console.log(solution("abcbdcba"));
console.log(solution("abcabbakcba"));
console.log(solution("abcacbakcba"));
  • 투포인터 방법을 사용해서 문제를 해결했다.
  • 각 양쪽 끝의 인덱스를 지정하는 lt, rt 변수를 초기화해서, rt가 lt보다 큰 동안 반복문을 실행시켰다.
  • 회문 문자열은 뒤집었을 때 같은 문자가 되어야 하므로, lt와 rt에 있는 문자를 비교하여 같다면 lt를 1증가시키고 rt를 1감소시켜서 회문 문자열일 경우 그대로 반복문을 빠져나와 기본값인 YES가 반환된다.
  • lt에 있는 문자와 rt에 있는 문자가 다를 때, lt에 있는 값을 제외하고 substring한 값과 rt에 있는 값을 제외하고 substring한 값을 구해서 둘다 회문 문자열이 아니라면 answer에 NO를 삽입하여 반환한다.

학급 회장

학급 회장을 뽑는데 후보로 기호 A, B, C, D, E 후보가 등록을 했습니다.
투표용지에는 반 학생들이 자기가 선택한 후보의 기호(알파벳)가 쓰여져 있으며 선생님은 그 기호를 발표하고 있습니다.
선생님의 발표가 끝난 후 어떤 기호의 후보가 학급 회장이 되었는지 출력하는 프로그램을 작성하세요. 반드시 한 명의 학급회장이 선출되도록 투표결과가 나왔다고 가정합니다.

function solution(s) {
  let answer;
  let sh = new Map();

  for (let i = 0; i < s.length; i++) {
    // 카운팅은 맵으로..
    sh.set(s[i], sh.get(s[i]) + 1 || 1);
  }

  let max = Number.MIN_SAFE_INTEGER;
  for (let [key, val] of sh) {
    if (val > max) {
      max = val;
      answer = key;
    }
  }

  return answer;
}

console.log(solution("BACBACCACCBDEDE"));
  • 내가 풀었던 방식과 이론은 똑같지만, 방식이 많이 달랐고 많이 배웠다.
  • 지금까지 카운팅 관련된 것들을 객체로 처리했는데, 맵을 사용하는 것이 좋다고 했다.
  • sh라는 새로운 맵 객체를 생성하여, 문자열의 각 문자를 키로 한 카운트를 세는 반복문을 실행했다.
  • sh.get(s[i])가 undefined인 경우에 연산을 하면 NaN이 결과가 되므로, 단축 평가 논리 계산법을 활용해 기본값을 설정해줬다.
  • Number.MIN_SAFE_INTEGER는 안전한 최소값이라는 상수이다.
  • for ... of 문법으로 맵을 반복하면, [key, val]로 키와 값을 쉽게 받을 수 있다.

Map 객체

  • let sh = new Map();: 새로운 맵 객체 생성
  • sh.set(키, 값): sh 맵에 키와 값을 삽입
  • sh.get(키): 키로 값을 조회해서 반환
  • sh.delete(키): 키로 값을 조회해서 삭제
  • sh.has(키): 키로 값을 조회해서 값을 가졌다면 true, 없다면 false 반환
  • sh.size: 맵에 존재하는 키 개수 반환

아나그램

Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아나그램이라고 합니다.
예를 들면 AbaAeCe 와 baeeACA 는 알파벳을 나열 순서는 다르지만 그 구성을 살펴보면 A(2), a(1), b(1), C(1), e(2)로 알파벳과 그 개수가 모두 일치합니다. 즉 어느 한 단어를 재배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 합니다.
길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세요. 아나그램 판별시 대소문자가 구분됩니다.

function solution(s1, s2) {
  if (s1.length !== s2.length) {
    return "NO";
  }

  let answer = "YES";
  let sh = new Map();

  for (let x of s1) {
    sh.set(x, sh.get(x) + 1 || 1);
  }

  for (let x of s2) {
    if (!sh.has(x) || sh.get(x) === 0) answer = "NO";
    sh.set(x, sh.get(x) - 1);
  }

  return answer;
}

console.log(solution("AbaAeCe", "baeeACA"));
console.log(solution("abaCC", "Caaab"));
  • 두 문자열을 구성하는 문자의 종류와 개수가 같은지를 비교해서 반환하면 되니, map을 활용해서 쉽게 해결할 수 있다.
  • 맵을 생성하고 s1의 문자 종류와 개수를 맵에 저장한다.
  • 그리고 s2를 반복해서 s2의 문자가 맵 sh에 없거나, 키에 해당하는 값이 0이면 answer를 NO로 저장하고, 조건문에 해당하지 않는다면 해당하는 키에 값을 1 빼서 저장한다.
  • 그러면 구성이 정확하게 일치할 때 YES를 반환하고, 일치하지 않으면 NO를 반환한다.

문자열 구분하기

N개의 문자열이 주어지면 모든 문자열을 구분할 수 있는 최소길이 접두어를 찾는 프로그램을 작성하세요.

function solution(words) {
  let answer;
  let i;
  let sh = new Map();

  for (i = 0; i < words[0].length; i++) {
    let flag = true;
    for (let j = 0; j < words.length; j++) {
      let x = words[j].substring(0, i + 1);
      if (sh.has(x)) {
        flag = false;
        break;
      }
      sh.set(x, 1);
    }
    if (flag) break;
  }
  answer = i + 1;

  return answer;
}

console.log(solution(["seeasue", "sesseysu", "semeas"]));
console.log(solution(["ackky", "kabck", "yokkcs"]));
console.log(solution(["longlong", "longtong", "longbig"]));
  • 각 문자열들의 접두어를 비교해야 하므로, 임의로 첫번째 문자열의 길이만큼 반복문을 돌리고, 그 안에서 문자열의 개수만큼 반복문을 돌렸다.
  • 플래그를 사용해서 반복문을 제어하기 위해 기본값이 true인 플래그를 첫번째 반복문 안에 선언했다.
  • 접두어를 잘라내서 비교해야 하므로, substring으로 앞 글자부터 접두어를 잘라내고 그 값이 맵 sh에 있는지 확인하여 없다면 맵에 접두어를 키로하고 값을 1로한 것을 저장하였다.
  • 값이 맵 sh에 있다면 각 단어가 모두 다르지 않기 때문에 플래그를 false로 만들고, break로 가장 안쪽 반복문을 빠져나갔다.
  • 그리고 안쪽 반복문이 끝날 때마다 플래그 값을 확인했는데, 값이 true라면 맵 sh에서 키에 대한 값이 모두 다른 것이라는 뜻이기 때문에 전체 반복문을 빠져나갔다.

0727

12일 차 자료구조 / 알고리즘

알고리즘

수열 축소

길이가 N인 수열이 주어지면 인접한 두 수의 차이를 이용해 길이가 N-1인 수열을 만듭니다.
만약 수열이 [5, 3, 7, 9, -2]라면 [(3-5), (7-3), (9-7), (-2-9)] => [-2, 4, 2, -11]로 수열의 길이를 줄일 수 있습니다. 이런 과정을 길이축소작업이라 하겠습니다.
N길이의 수열이 주어지면 M번의 길이축소작업을 한 결과를 구하는 프로그램을 작성하세요.

function solution(nums, m) {
  let answer;
  let n = nums.length;

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      nums[j] = nums[j + 1] - nums[j];
    }
  }
  answer = nums.slice(0, n - m); // 퀴즈
  return answer;
}

console.log(solution([5, 3, 7, 9, -2], 1));
console.log(solution([5, 3, 7, 9, -2], 2));
  • 첫 번째 반복문은 길이 축소 작업을 수행해야 하는 횟수만큼 반복하고, 두 번째 반복문은 n - 1 - i 번 만큼 반복한다.
    • n + 1번째 위치하는 요소에서 n 번째 위치하는 요소를 빼는 작업을 하기 때문에 n - 1번 반복하고, i가 증가함에 따라 배열의 크기가 줄어들게 되어 n - 1 - i번 반복한다.
  • 반복문 내부에서 nums 배열의 j 번째 요소를 nums[j+1]-nums[j]로 대체하였다.
  • 반복문이 모두 끝나고, n-m까지의 배열을 잘라서 반환하였다.

가장 높은 증가수열

길이가 N인 수열이 주어지면 이 수열에서 연속된 부분 증가수열을 찾습니다.
각 부분증가수열은 높이가 있습니다. 증가수열의 높이란 증가수열의 첫항과 마지막항의 차를 의미합니다.
수열이 주어지면 여러 증가수열 중 가장 높은 부분증가수열을 찾는 프로그램을 작성하세요.
만약 수열이 [5, 2, 4, 7, 7, 3, 9, 10, 11]이 주어지면 가장 높은 부분증가수열은 [3, 9, 10, 11]이고, 높이는 8입니다.

function solution(nums) {
  let answer = 0;
  let sum = 0;

  for (let i = 1; i < nums.length; i++) {
    if (nums[i - 1] < nums[i]) {
      sum += nums[i] - nums[i - 1];
    } else {
      answer = Math.max(sum, answer);
      sum = 0;
    }
  }
  answer = Math.max(answer, sum);

  return answer;
}

console.log(solution([5, 2, 4, 7, 7, 3, 9, 10, 11]));
console.log(solution([8, 12, 2, 3, 7, 6, 20, 3]));
  • i를 1부터 배열의 길이까지 반복하여 nums[i - 1] < num[i]라면 숫자가 증가중이므로 변수 sum에 증가한 숫자만큼 더하였고, 그렇지 않다면 증가하지 않은 상황이므로 answer에 담긴 값과 비교해 더 큰 값을 answer에 담았다.
  • 그리고 계속 반복문을 돌아야해서 sum을 0으로 초기화시키고 반복문을 진행했다.
  • 반복문이 모두 끝난 후에는 끝까지 수열이 증가하다 끝나서 answer에 현재 sum이 담기지 못했을 수 있으므로, sum과 answer를 비교해서 큰 값을 답에 넣어주는 작업을 한 번 더 수행한다.

가장 긴 수열

길이가 N인 수열이 주어지면 이 수열에서 연속으로 증가하거나, 또는 연속으로 작아지는 부분 수열 중 가장 길이가 긴 수열을 찾는 프로그램을 작성하세요.
만약 [5, 3, 6, 7, 9, 8, 5, 3, 1, 2]이 주어지면 우리가 찾는 가장 긴 수열은 [9, 8, 5, 3, 1] 입니다.
수열 [1, 2, 3, 3, 4, 5, 6]과 같이 같은 값이 연속으로 있는 것은 증가 또는 감소로 보지 않기 때문에 가장 긴 수열은 [3, 4, 5, 6]이 됩니다.

  • 매개변수 형식 2는 답이 잘못되었다. 8 -> 4
function solution(nums) {
  let answer;
  let up = 1;
  let down = 1;
  let maxUp = 0;
  let maxDown = 0;

  for (let i = 1; i < nums.length; i++) {
    if (nums[i - 1] < nums[i]) {
      up++;
    } else {
      maxUp = Math.max(up, maxUp);
      up = 1;
    }

    if (nums[i - 1] > nums[i]) {
      down++;
    } else {
      maxDown = Math.max(down, maxDown);
      down = 1;
    }
  }
  maxUp = Math.max(up, maxUp);
  maxDown = Math.max(down, maxDown);

  answer = Math.max(maxUp, maxDown);

  return answer;
}

console.log(solution([5, 3, 6, 7, 9, 8, 5, 3, 1, 2]));
console.log(solution([5, 2, 4, 7, 6, 3, 9, 10, 11]));
console.log(solution([1, 2, 3, 3, 4, 5, 6, 7, 7]));
  • 나는 변수에 증가 상황일 때와, 감소 상황일 때의 값을 지정하고 문제를 해결했었다.
  • 하지만 if else문을 두 번 사용해서 좀 더 가독성 좋게 문제를 해결할 수 있는 방법도 있었다.
  • 증가한 횟수를 저장하는 up 변수, 내려간 횟수를 저장하는 down 변수를 선언하고 기본 값을 1로 설정하였다.
  • nums[i - 1] < nums[i]인 경우라면 up 변수를 1 증가시켰고, 그렇지 않다면 최대 증가 횟수를 저장하는 maxUp 변수에 현재 maxUp 변수에 담긴 값과 up 변수에 담긴 값을 비교해서 큰 값을 저장했다. 그리고 up 변수를 1로 초기화했다.
  • nums[i - 1] < nums[i]도 반대의 경우로 마찬가지로 진행했다.
  • 반복문이 끝나고, 마지막까지 증가하거나 감소한 경우의 값도 비교해서 저장하기 위해서 maxUp 변수와 up 변수, maxDown 변수와 down 변수를 비교해서 큰 값을 저장하는 작업을 한 번 더 진행했다.
  • 마지막으로 maxDown 변수와 maxUp 변수 중에 큰 값을 결과로 반환했다.

바이토닉 수열

바이토닉 수열이란 수열이 증가했다가 감소하는 수열을 의미합니다.
길이가 N인 수열이 주어지면 이 수열이 바이토닉 수열인지 판별하는 프로그램을 작성하세요. 만약 [1, 2, 3, 4, 2, 1]이면 바이토닉 수열입니다. 하지만 [1, 2, 2, 3, 2, 1]과 같이 같은 값이 연속으로 있으면 바아토닉이 수열이라 하지 않습니다.

function solution(nums) {
  let n = nums.length;
  let answer = "YES";
  let i = 0;

  while (i < n - 1 && nums[i] < nums[i + 1]) {
    // 증가수열
    i++;
  }
  if (i === 0 || i === n - 1) answer = "NO";

  while (i < n - 1 && nums[i] > nums[i + 1]) {
    // 감소수열
    i++;
  }
  if (i !== n - 1) answer = "NO";

  return answer;
}

console.log(solution([1, 2, 3, 4, 5, 3, 1]));
console.log(solution([1, 3, 4, 5, 5, 6, 4, 3]));
console.log(solution([1, 2, 3, 4, 5]));
  • 기존에는 이 문제를 증가 및 감소를 허용하는지에 대한 boolean 값으로 정해서, 허용하지 않는 경우에 값을 증가하거나 감소하려하면 바로 answer를 NO로 반환해주는 방식으로 해결하였다.
  • 하지만 while문을 잘 활용해서 문제를 해결하는 방법이 있었다.
  • while문에서 사용할 변수 i를 선언하고, i가 n - 1 보다 작으면서 증가할 동안 i를 계속 증가시켰다.
    • 조건의 위치 중요! i < n - 1이 뒤에 있으면 nums[i + 1]이 undefined를 가리킬 수도 있다.
    • 반복문을 빠져나오면 i가 0이거나 n-1이면 NO를 반환했다.
    • 0이라는 것은 처음부터 감소했다거나, 끝까지 증가하기만 했다는 것이기 때문
  • 그 밑에 while문을 하나 더 사용해서 i가 n - 1보다 작으면서 감소할 동안 i를 증가시켰다.
    • 반복문을 빠져나오면 i가 n - 1이 아니면 NO를 반환했다.
    • 반복문이 끝나기 전에 증가하거나 같은 구간이 발생했기 때문
  • 반복문을 무사히 마치면 기본 값인 YES를 반환한다.
  • while문을 활용하는 것을 두려워하는 것 같다. 생각해보면 코딩테스트를 하면서 while문을 사용해서 문제를 해결한 적이 없다. 이번 기회에 while문을 사용할 수 있는 문제에서는 사용해봐야겠다.

거리 두기

현수는 영화관에 도착했습니다. 영화상영 시간보다 약간 늦은 현수는 남은 좌석을 빨리 선택하고 영화를 보려고 합니다.
현수에게 일렬로된 좌석정보가 주어지면, 이미 앉아 있는 사람들 중 가장 가까운 사람과 최대한 멀리 떨어져 앉을 자석을 선택해야 합니다. 여러분이 도와주세요.

function solution(nums) {
  let answer = 0;
  let d = 1000;
  let distance = [];

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === 1) {
      distance[i] = 0;
      d = 0;
    } else {
      d++;
      distance[i] = d;
    }
  }

  d = 1000;
  for (let i = nums.length - 1; i >= 0; i--) {
    if (nums[i] === 1) {
      distance[i] = 0;
      d = 0;
    } else {
      d++;
      distance[i] = Math.min(d, distance[i]);
    }
  }
  answer = Math.max(...distance);

  return answer;
}

console.log(solution([1, 0, 0, 0, 1, 0, 0, 1, 0, 1]));
  • 이 문제의 풀이법은 상당히 흥미로웠다. 나는 for문 안에 If문을 사용해서 상황을 나눠서 구현했는데, 왼쪽에서의 떨어진 거리를 구하고 오른쪽에서 떨어진 거리를 구해서 더 작은 값을 반환한다는 접근법이 신기했다.
  • 우선 끝에 벽이 있을 경우에는 임의로 큰 값을 지정했다.
  • 변수 d를 1000으로 지정하고, 거리를 담는 배열인 distance를 선언했다.
  • 배열을 왼쪽에서부터 오른쪽으로 탐색해서, 해당 요소가 1이면 사람이 있는 경우이므로 distance에 0을 넣고, d를 0으로 초기화한다.
  • 그렇지 않다면 d를 증가시키고, distance배열에 d를 저장한다.
  • 반복문이 끝나면 다시 d를 1000으로 초기화하고 이번에는 뒤에서부터 요소가 1이라면 distance에 0을 넣고, d를 0으로 초기화한다.
  • 그렇지 않다면 d를 증가시키고, distance에 d와, distance[i] 중 작은 값을 저장한다.
  • 그러면 요소 기준 양쪽에서 1이 들어있는 거리중 짧은 거리가 담기게 된다.
  • Math.max(...distance)를 사용해서 distance에 담긴 요소 중 가장 큰 값을 반환한다.
    • Math.max() 메서드의 인자로 스프레드 연산자 배열을 사용하면, 해당 배열 요소 중 가장 큰 값을 반환할 수 있다.

2차원 배열 1의 개수

0과 1로 구성된 2차원 배열이 주어지면 각 행의 1이 개수를 세어 개수가 가장 작은 행번호부터 출력하는 프로그램을 작성하세요.
1의 개수가 같은 행은 여러개이면 행번호가 작은 것부터 출력합니다. 이차원배열의 행크기가 N이면 행번호는 0번부터 N-1번까지입니다.

function solution(nums) {
  let answer = nums
    .map((row, i) => ({ i, cnt: row.reduce((a, b) => a + b, 0) }))
    .sort((a, b) => a.cnt - b.cnt)
    .map((ob) => ob.i);

  return answer;
}

console.log(
  solution([
    [1, 0, 0, 1],
    [0, 0, 0, 1],
    [1, 1, 0, 1],
    [0, 1, 0, 1],
  ])
);
  • 행의 값을 모두 더해서 값이 큰 순서대로 행의 순서 배열을 반환하는 문제인대, 쉬운 문제이지만 js의 내장함수를 사용해서 정말 짧고 간결하게 해결하는 방법이 있었다.
  • 우선 map함수를 이용해서 객체 배열을 반환했는데, i는 인덱스이고 cnt는 reduce를 사용해서 각 행의 1의 개수를 더한 값이 들어있다.
    • 즉, 각 행의 인덱스와 행에서의 1의 개수가 담긴 객체 배열을 반환했다.
  • 그리고 바로 이어서 sort 함수를 사용해 cnt를 기준으로 오름차순 정렬했다.
  • 그리고 바로 map을 사용해서 객체의 인덱스를 반환했다.
  • 이 문제를 보고, 자바스크립트에서 내장함수를 이런 식으로 사용하는 거구나 하고 이해했다.

행과 열의 최솟값

자연수로 채워져 있는 2차원 배열이 주어지면 행과열의 최솟값들을 구하는 프로그램을 작성하세요.
행과열의 최솟값이란 2차원 배열의 숫자가 자신이 속한 행과 자신이 속한 열에서 모두 가장 작은 숫자를 의미합니다.
2차원 배열에 존재하는 모든 행과열의 최솟값들을 찾아주는 프로그램을 작성하세요.

function solution(nums) {
  let answer = [];
  let n = nums.length;

  for (let i = 0; i < n; i++) {
    let min = nums[i][0];
    let pos = 0;
    for (let j = 0; j < n; j++) {
      if (nums[i][j] < min) {
        min = nums[i][j];
        pos = j;
      }
    }

    let row;
    for (row = 0; row < n; row++) {
      if (nums[row][pos] < min) break;
    }
    if (row == n) answer.push(min);
  }

  answer.sort((a, b) => a - b);
  return answer;
}

console.log(
  solution([
    [4, 6, 22, 1],
    [9, 3, 10, 12],
    [30, 7, 20, 2],
    [15, 8, 5, 13],
  ])
);
  • 기존에는 각 숫자를 받아와서, 숫자가 행과 열에서 최솟값인지 boolean 값을 반환하는 함수를 추가 작성해서 문제를 해결했다.
  • 하지만 그럴 필요 없이 2중 for문을 돌려서 첫 번째 반복문에서 변수 min에 각 행의 첫 번째 요소를 삽입하고 각 열의 최솟값을 가진 요소의 열 정보를 저장할 변수 pos를 선언했다.
  • 두 번째 반복문에서 열의 최솟값을 구한 뒤, 해당 열의 정보를 j에 저장했다.
  • 그리고 밑에 또 다른 두 번째 반복문을 선언하고, 열을 고정한 채 반복문을 돌려서 min보다 더 작은 값이 있다면 해당 반복문을 break했다.
  • 해당 반복문이 끝까지 돌았는지를 조건으로, 끝까지 돌았다면 min이 최솟값이므로 정답 배열에 min을 push한다.
  • 정답 배열을 오름차순 정렬해서 반환하였다.

봉우리

지도 정보가 N*N 격자판에 주어집니다. 각 격자에는 그 지역의 높이가 쓰여있습니다.
각 격자판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역입니다. 봉우리 지역이 몇 개 있는 지 알아내는 프로그램을 작성하세요.
격자의 가장자리는 0으로 초기화 되었다고 가정한다.
만약 N=5 이고, 격자판의 숫자가 다음과 같다면 봉우리의 개수는 10개입니다.

function solution(arr) {
  let answer = 0;
  let n = arr.length;
  let dx = [-1, 0, 1, 0];
  let dy = [0, 1, 0, -1];

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      let flag = true;
      for (let k = 0; k < 4; k++) {
        let nx = i + dx[k];
        let ny = j + dy[k];
        if (
          nx >= 0 &&
          nx < n &&
          ny >= 0 &&
          ny < n &&
          arr[nx][ny] >= arr[i][j]
        ) {
          flag = false;
          break;
        }
      }
      if (flag) answer++;
    }
  }

  return answer;
}

console.log(
  solution([
    [5, 3, 7, 2, 3],
    [3, 7, 1, 6, 1],
    [7, 2, 5, 3, 4],
    [4, 3, 6, 4, 1],
    [8, 7, 3, 5, 2],
  ])
);
  • 나는 0이 포함된 배열을 선언해서, 해당 배열에서 반복문과 if문을 사용해서 문제를 해결했다.
    • 이 문제의 경우 내가 푼 방법도 좋은 거 같았지만, 좀 더 난이도 있는 문제에서도 활용할만한 개념을 알게 되었다.
  • 이 문제 풀이의 핵심은 위치 배열의 선언이다. 변수 dx는 행, dy는 열을 기준으로 12시, 3시, 6시, 9시 시계 방향으로 돌 때마다 이동하는 값을 배열로 선언했다.
    • 처음에 조금 헷갈렸던 것은 dx의 경우 수학 함수 그래프를 생각하고 왜 12시 방향이 1이 아니고 -1이지 생각했다.
    • 하지만 배열로 생각을 하니 쉽게 이해가 되었다.
  • 2중 반복문으로 각 요소에 접근했고, flag를 true로 초기화했다.
  • 그 안에서 위치 배열의 길이만큼 반복문을 돌려서 nx에는 현재 행 정보 + dx[k]를, ny에는 현재 열 정보 + dy[k] 값을 할당했다.
    • 이렇게 하면 nx, ny에는 해당 요소를 기준으로 위, 아래, 좌, 우 요소의 인덱스 값이 저장된다.
  • nx와 ny가 0보다 크거나 같으면서, n보다는 작으면서, arr[i][j]보다 arr[nx][ny]가 크거나 같다를 조건으로 걸고, 이 안에 하나라도 해당된다면 flag를 false로 바꾸고 break로 반복문을 빠져나갔다.
    • 여기서 nx와 ny가 0보다 크거나 같으면서, n보다는 작으면서 조건을 먼저 써 줘야 한다.
    • nx, ny가 유효하지 않는 값일 때 비교하는 일이 없도록 하기 위해서!!
    • &&를 사용할 때 값을 어디에 위치시킬지 잘 생각하자
  • 위치 배열을 모두 적용했을 때 flag가 true로 유지된다면 정답을 1 증가시키고, 반복문이 모두 끝나고 나서 정답을 반환했다.

0728

13일 차 자료구조 / 알고리즘

알고리즘

올바른 괄호

괄호가 입력되면 올바른 괄호이면 “YES”, 올바르지 않으면 ”NO”를 출력합니다.
(())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다.

function solution(s) {
  let answer = "YES";
  let stack = [];

  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(") {
      stack.push(s[i]);
    } else {
      if (stack.length === 0) return "NO";
      stack.pop();
    }
  }

  if (stack.length > 0) answer = "NO";

  return answer;
}

console.log(solution("(()(()))(()"));
console.log(solution("(())()"));
console.log(solution("(()()))"));
  • 배열을 하나 만들고, 여는 괄호를 만나면 배열에 push한다.
  • 닫는 괄호를 만나면 pop 시킨다. 닫는 괄호를 만났는데 스택이 비어있으면 올바른 괄호가 아니므로 return “NO”
  • 다 돌았는데 스택이 남아있으면 answer를 NO로 한다.
  • 괄호가 문제에 나오면 바로 스택을 떠올리자!

스택

  • 자료가 들어가는 곳과 나오는 곳이 같은 자료구조
  • Last In First Out
  • 자바스크립트에서 큐와 스택, 덱은 지원
  • 자바스크립트는 힙 구조가 없어서 구현해야 한다.

괄호문자 제거

입력된 문자열에서 소괄호 ( ) 사이에 존재하는 모든 문자를 제거하고 남은 문자만 출력하는 프로그램을 작성하세요.

function solution(s) {
  let answer;
  let stack = [];

  for (let i = 0; i < s.length; i++) {
    if (s[i] === ")") {
      while (stack.pop() !== "(");
    } else {
      stack.push(s[i]);
    }
  }

  answer = stack.join("");
  return answer;
}

console.log(solution("(A(BC)D)EF(G(H)(IJ)K)LM(N)"));
  • 여는 괄호거나 숫자면 push
  • 닫는 괄호를 만나면, pop 결과가 여는 괄호가 나올 때까지 반복

후위식 연산

후위연산식이 주어지면 연산한 결과를 출력하는 프로그램을 작성하세요.
만약 3(5+2)-9 을 후위연산식으로 표현하면 352+9- 로 표현되며 그 결과는 12입니다.

function solution(s) {
  let answer;
  let stack = [];

  for (x of s) {
    if (!isNaN(x)) {
      stack.push(Number(x));
    } else {
      let rt = stack.pop();
      let lt = stack.pop();
      if (x === "+") stack.push(lt + rt);
      else if (x === "-") stack.push(lt - rt);
      else if (x === "*") stack.push(lt * rt);
      else if (x === "/") stack.push(lt / rt);
    }
    console.log(stack);
  }
  answer = stack[0];

  return answer;
}
  • 후위식을 값을 구하는 프로세스는 다음과 같다.
    1. 요소가 숫자면 스택에 push한다.
    2. 요소가 연산자면 연산을 진행하는데, 스택에서 pop을 두 번 해서 처음 나오는 것을 오른쪽에, 나중에 나오는 것을 왼쪽에 두고 연산을 한다.
    3. 연산 결과를 스택에 push한다.
    4. 이 과정을 식이 끝날 때까지 반복하면 스택에 남아있는 하나의 요소가 식의 결과가 된다.
  • isNaN(x)는 x가 숫자이면 false, 숫자가 아니면 true를 반환하는 함수이다.

전위, 중위, 후위

  • 이진트리는 부모, 왼쪽 자식, 오른쪽 자식이 기본 구조
  • 전위 순회는 방문하는 순서가 부모 -> 왼쪽 자식 -> 오른쪽 자식
  • 중위 순회는 방문하는 순서가 왼쪽 자식 -> 부모 -> 오른쪽 자식
  • 후위 순회는 방문하는 순서가 왼쪽 자식 -> 오른쪽 자식 -> 부모
  • 예를 들어, 1, 2, 3, 4, 5, 6, 7이 이진트리로 구성되어 있다면,
    • 전위 : 1, 2, 4, 5, 3, 6, 7
    • 중위 : 4, 2, 5, 1, 6, 3, 7
    • 후위 : 4, 5, 2, 6, 7, 3, 1

중위식을 후위식으로 바꾸는 법

  • 맨 나중에 연산되는 연산자를 찾는다.
  • 해당 연산자를 루트노드로, 연산자를 기준으로 왼쪽 값은 왼쪽 자식 노드로, 오른쪽 값은 오른쪽 자식 노드로 보내서 이 행위를 반복한다.
  • 중위식을 이진트리화 시킨다.
  • 이진트리를 후위식으로 바꾼다.

연속된 문자 지우기

문자열 s가 주어지면 이웃한 두 개의 문자가 같으면 두 문자를 제거합니다.
이 과정을 반복해 서 최종적으로 남는 문자만으로 이루어진 문자열을 출력하는 프로그램을 작성하세요.
만약 “acbbcaa”라는 문자열이 주어진다면 최초 bb가 연속되어 있어 제거하고 나면 “accaa”가 되고, 다시 cc가 연속되어 제거하면 ”aaa”가 되고 “aa”연속되어 제거하면 ”a”가 최종적으로 남습니다.

function solution(s) {
  let answer;
  let stack = [];

  for (x of s) {
    if (stack.length === 0 || stack[stack.length - 1] !== x) {
      stack.push(x);
    } else {
      stack.pop();
    }
  }

  answer = stack.join("");

  return answer;
}
  • 스택이 비었을 때는 그냥 push한다.
  • 스택의 최상단과 비교해서 값이 다르면 push한다.
  • 값이 같으면 pop한다.
  • 반복문을 마치면 스택을 문자열로 바꿔서 출력한다.

공주 구하기

정보 왕국의 이웃 나라 외동딸 공주가 숲속의 괴물에게 잡혀갔습니다.
정보 왕국에는 왕자가 N명이 있는데 서로 공주를 구하러 가겠다고 합니다. 정보왕국의 왕은 다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 했습니다.
왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매긴다. 그리고 1번 왕자부터 N 번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다.
그리고 1번 왕자부터 시 계방향으로 돌아가며 1부터 시작하여 번호를 외치게 한다.
한 왕자가 K(특정숫자)를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 된다.
그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외친다.
이렇게 해서 마지막까지 남은 왕자가 공주를 구하러 갈 수 있다.

예를 들어 총 8명의 왕자가 있고, 3을 외친 왕자가 제외된다고 하자. 처음에는 3번 왕자가 3 을 외쳐 제외된다. 이어 6, 1, 5, 2, 8, 4번 왕자가 차례대로 제외되고 마지막까지 남게 된 7 번 왕자에게 공주를 구하러갑니다.
N과 K가 주어질 때 공주를 구하러 갈 왕자의 번호를 출력하는 프로그램을 작성하시오.

function solution(n, k) {
  let answer;
  let queue = Array.from({ length: n }, (v, i) => i + 1);

  while (queue.length > 1) {
    for (i = 1; i < k; i++) {
      let tmp = queue.shift();
      queue.push(tmp);
    }
    queue.shift();
  }

  answer = queue.join("");

  return answer;
}

console.log(solution(8, 3));
  • queue를 활용하는 문제이다.
  • 우선 queue를 Array.from 문법을 사용해서 초기화한다.
  • queue의 길이가 1보다 클 때까지, k - 1번만큼 반복문을 앞에서 빼서, 뒤로 넣는다.
  • 그리고 맨 앞에서 뺀걸 버리고, 이 행위를 while문 조건이 만족하지 않을 때까지 반복한다.

Array.from

  • 첫번째 매개변수로 {length: 원하는길이} 객체를, 두번째 매개변수로 원하는 값을 반환하는 콜백함수를 넘겨준다.
  • 콜백함수에서는 첫번째 매개변수를 넘겨줘야, 두번째 매개변수로 인덱스를 불러올 수 있다.

교육과정 설계

현수는 1년 과정의 수업계획을 짜야 합니다.
수업중에는 필수과목이 있습니다. 이 필수과목은 반드시 이수해야 하며, 그 순서도 정해져 있습니다.
만약 총 과목이 A, B, C, D, E, F, G가 있고, 여기서 필수과목이 CBA로 주어지면 필수과목은 C, B, A과목이며 이 순서대로 꼭 수업계획을 짜야 합니다.
여기서 순서란 B과목은 C과목을 이수한 후에 들어야 하고, A과목은 C와 B를 이수한 후에 들어야 한다는 것입니다.
현수가 C, B, D, A, G, E로 수업계획을 짜면 제대로 된 설계이지만
C, G, E, A, D, B 순서로 짰다면 잘 못 설계된 수업계획이 됩니다.
수업계획은 그 순서대로 앞에 수업이 이수되면 다음 수업을 시작하다는 것으로 해석합니다. 수업계획서상의 각 과목은 무조건 이수된다고 가정합니다. 필수과목순서가 주어지면 현수가 짠 N개의 수업설계가 잘된 것이면 “YES”, 잘못된 것이면 ”NO“를 출력하는 프로그램을 작성하세요.

function solution(need, plan) {
  let answer;
  let queue = need.split("");

  for (let x of plan) {
    if (queue.includes(x)) {
      if (x != queue.shift()) return "NO";
    }
  }

  answer = queue.length === 0 ? "YES" : "NO";

  return answer;
}

console.log(solution("CBA", "CBDAGE"));
console.log(solution("CBA", "CBDBAGE"));
  • 문제를 제대로 읽지 않고 코드를 짰다가 낭패를 본 문제이다.
  • 필수 과목만 순서대로 들어가면 된다고 생각해서 코드를 구현했는데, 선행되는 필수과목을 듣기 전까지는 그 뒤의 필수과목을 들어서는 안된다는 점을 간과했다.
  • 이를 해결하기 위해서는 수업계획상의 요소가 필수과목 배열에 있는지를 확인해서, 있다면 맨 앞에 것을 꺼내서 비교한 결과가 같지 않다면 바로 return NO를 해버리고, 이를 끝까지 반복하고 큐에 과목이 남아있다면 NO를 반환하도록 한다.

최소 매출

현수의 아빠는 제과점을 운영합니다. 현수아빠는 현수에게 N일 동안의 매출기록을 주고 연속 된 K일 동안의 최소 매출액을 차례로 구하라고 했습니다.
만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면
11 12 15 20 25 10 20 13 15 19
연속된 3일간의 매출액을 차례로 구해보면 [11, 12, 15] 중에서 11, [12, 15, 20] 중에서 12, [15, 20, 25] 중에서 15와 같이 계속 구하면 결과는 [11, 12, 15, 10, 10, 10, 13, 13]입니다.

function solution(nums, k) {
  let answer = [];
  let deque = [];

  for (let i = 0; i < k - 1; i++) {
    while (deque.length > 0 && deque[deque.length - 1][0] > nums[i]) {
      deque.pop();
    }
    deque.push([nums[i], i]);
  }

  for (let i = k - 1; i < nums.length; i++) {
    while (deque.length > 0 && deque[deque.length - 1][0] > nums[i]) {
      deque.pop();
    }
    deque.push([nums[i], i]);
    answer.push(deque[0][0]);
    if (deque[0][1] === i - k + 1) deque.shift();
  }

  return answer;
}

console.log(solution([11, 12, 15, 20, 25, 10, 20, 13, 15, 19], 3));
  • deque를 활용해서 문제를 해결해야 했다.
  • for문을 두 번으로 나눠서 문제를 해결하는데, 첫 번째 for문에는 k - 1개까지의 deque를 만들어두고, deque가 k개가 될 때부터의 로직을 두 번째 for문에 작성했다.
  • 첫 번째 for문에서는 deque가 비어있지 않으면서, 새로 들어온 요소가 deque 맨 뒤에 있는 요소보다 작은 경우에는 계속 pop()을 시켜주고, 새로 들어온 요소는 push했다.
  • 그러면 deque 맨 앞의 값은 항상 최솟값으로 유지된다.
  • index를 사용해서 값을 deque에서 빼줘야 할 지 계산하는 로직을 뒤에 작성해야 하므로, push할 때 인덱스를 포함하여 배열 형태로 push했다.
  • 두 번째 for문에서는 k - 1부터 시작해서 반복문을 돌린다.
  • deque의 길이가 0보다 크면서 새로 들어온 요소가 deque의 맨 뒤에 있는 요소보다 작은 경우에는 계속 pop()을 시켜주고, 새로 들어온 요소는 push했다.
  • 그러면 deque 맨 앞의 값은 최솟값이므로, 맨 앞의 값을 answer로 push했다.
  • 결과값에는 3개씩 그룹을 지어서 그 중 가장 작은 값만 출력해줘야하므로, deque의 인덱스가 i - k + 1이 되면 shift()로 해당 요소를 빼주어서 최종 결과를 출력했다.

재귀 함수

  • 재귀함수는 스택 프레임을 이용한다.
  • 스택 프레임 최상단에 있다는 뜻은 현재 작동중이다라는 뜻이다.
  • 스택이용 -> 백트래킹의 기본
  • 재귀, dfs 사용할 때는 무조건 if else 사용할 것
    • if문에는 끝날 조건을 지정한다.
    • else문에는 그 외에 동작을 구현한다.

스택 프레임 주 정보

  1. 매개변수 정보
  2. 지역변수 정보
  3. 복귀 주소

0729

14일 차 슬라이딩 윈도우, two pointers Algorithm

최대 매출

현수의 아빠는 제과점을 운영합니다. 현수아빠는 현수에게 N일 동안의 매출기록을 주고 연속 된 K일 동안의 매출액의 합 중에서 최대값이 얼마인지 구하라고 했습니다.
만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면
12 15 11 20 25 10 20 19 13 15
연속된 3일간의 최대 매출액은 11+20+25=56만원입니다. 여러분이 현수를 도와주세요.

function solution(nums, k) {
  let answer = 0;
  let n = nums.length;
  let sum = 0;

  for (let i = 0; i < k; i++) {
    sum += nums[i];
  }
  answer = sum;

  for (let i = k; i < n; i++) {
    sum += nums[i] - nums[i - k];
    answer = Math.max(sum, answer);
  }

  return answer;
}
  • 슬라이딩 윈도우 기법을 사용해서 문제를 해결한다.
  • 예를 들어, 이 문제에서 연속된 K일이라는 말이 나왔으니 K개를 창이라 생각하고 옆으로 밀고 가면서 값을 구한다.
    • 연속된..과 개수가 지정된 경우가 있으면 이 기법을 떠올려보자.
  • sum에는 윈도우의 값들의 합을 누적한다.
  • 한 칸 이동할 때마다 새로운 요소는 더해주고 창에 있던 맨 앞 요소는 빼준다.

매출액의 종류

현수의 아빠는 제과점을 운영합니다. 현수아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 매출액의 종류를 각 구간별로 구하라고 했습니다.
만약 N=7이고 7일 간의 매출기록이
20 12 20 10 23 17 10
각 연속 4일간의 구간의 매출종류는
첫 번째 구간은 [20, 12, 20, 10]는 매출액의 종류가 20, 12, 10으로 3이다.
두 번째 구간은 [12, 20, 10, 23]는 매출액의 종류가 4이다.
세 번째 구간은 [20, 10, 23, 17]는 매출액의 종류가 4이다.
네 번째 구간은 [10, 23, 17, 10]는 매출액의 종류가 3이다.
N일간의 매출기록과 연속구간의 길이 K가 주어지면 첫 번째 구간부터 각 구간별 매출액의 종류를 출력하는 프로그램을 작성하세요.

function solution(nums, k) {
  let answer = [];
  let sh = new Map();

  for (let i = 0; i < k - 1; i++) {
    sh.set(nums[i], sh.get(nums[i]) + 1 || 1);
  }

  let lt = 0;

  for (let rt = k - 1; rt < nums.length; rt++) {
    sh.set(nums[rt], sh.get(nums[rt]) + 1 || 1);
    answer.push(sh.size);
    sh.set(nums[lt], sh.get(nums[lt]) - 1);
    if (sh.get(nums[lt]) === 0) sh.delete(nums[lt]);
    lt++;
  }

  return answer;
}
  • 슬라이딩 윈도우 기법을 사용할 때, 먼저 기본 창을 세팅해놓고 시작하는 것을 기억하자
  • 종류를 구해야 하니, map을 사용해서 풀면 좋다.
  • 값이 0일 때는, 삭제를 해줘야 종류의 개수를 구할 때 포함되지 않는다.
  • lt를 변수로 선언해서 삭제해야 하는 값의 인덱스를 편하게 지정했다.

연속 부분수열 1

N개의 수로 이루어진 수열이 주어집니다.
이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.
만약 N=8, M=6이고 수열이 다음과 같다면
12131112
합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다.

function solution(nums, m) {
  let answer = 0;
  let lt = 0;
  let sum = 0;

  for (let rt = 0; rt < nums.length; rt++) {
    sum += nums[rt];

    while (sum > m) {
      sum -= nums[lt++];
    }

    if (sum === m) {
      answer++;
    }
  }

  return answer;
}
  • lt는 0으로 초기화하고, rt는 for문에서의 인덱스로 증가시키며 반복문을 구성한다.
  • for문 안에서는 값이 목표 값인지를 확인한다. 목표 값이면 answer를 증가시킨다.
  • sum이 목표 값보다 커지면 lt가 쫒아오면서 lt에 있는 값을 sum에서 빼 준다.
  • lt가 빼도 목표 값보다 큰 경우가 있을 수 있기 때문에, while문으로 처리해야 한다.

연속 부분수열 2

N개의 수로 이루어진 수열이 주어집니다.
이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.
만약 주어진 수열이 [1, 2, 3, -3, 1, 2]이고, M값이 3이라면
합이 3이 되는 연속부분수열은 [1, 2], [1, 2, 3, -3], [2, 3, -3, 1], [3], [3, -3, 1, 2], [1, 2]로 총 6가지입니다.

function solution(nums, m) {
  let answer = 0;
  let sum = 0;
  let nH = new Map();

  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    if (sum === m) answer++;
    if (nH.has(sum - m)) answer += nH.get(sum - m);

    nH.set(sum, nH.get(sum) + 1 || 1);
  }

  return answer;
}
  • 코딩테스트를 공부하면서 느끼는 점 중 하나는, 코드를 이해하는 것이 중요한 게 아니라 어떻게 하면 비슷한 유형의 문제를 만났을 때 저렇게 코드를 구현할 생각을 할 수 있을지 깨닫는 것이 중요하다는 것이다.
  • 처음 문제를 접했을 때는 sum - m이라는 수식 때문에 머리를 싸매고 고민했다.
  • 그리고 왜 맵을 사용했을까에 대한 깊은 고민을 했다.
  • 이 문제는 음수가 있기 때문에 어떤 값이 있을지 모른다. 그래서 우선 sum이라는 변수를 반복문을 돌면서 쭉 누적했다.
  • 처음부터 i까지의 합에서 처음부터 일정 구간 까지의 합을 뺀다는 것은, 일정 구간에서 i까지의 합과 같은 결과이다.
  • 이 문제는 이 원리를 활용해서 푸는 문제였고, 그 횟수를 answer에 더해주기 위해서 저장하는 용도로 map을 사용했다.

연속 부분수열 3

N개의 수로 이루어진 수열이 주어집니다.
이 수열에서 연속부분수열의 합이 특정숫자 M이하가 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.
만약 N=5, M=5이고 수열이 다음과 같다면
13123
합이 5이하가 되는 연속부분수열은 {1}, {3}, {1}, {2}, {3}, {1, 3}, {3, 1}, {1, 2}, {2, 3}, {1, 3, 1}로 총 10가지입니다.

function solution(nums, m) {
  let answer = 0;
  let lt = 0;
  let sum = 0;

  for (let rt = 0; rt < nums.length; rt++) {
    sum += nums[rt];

    while (sum > m) {
      sum -= nums[lt++];
    }

    answer += rt - lt + 1;
  }

  return answer;
}
  • lt랑 rt 사용해서 해결
  • rt가 증가하면 계속해서 sum에 rt부터 lt까지의 합을 더해준다.
  • sum이 목표 값보다 커지면 lt를 증가시킨다. (while문 사용)
  • 반복문이 끝나기 전에 rt인덱스에서 lt인덱스를 빼고, 1을 더하면 그 구간까지의 부분수열의 개수가 된다.

연속된 자연수의 합

N입력으로 양의 정수 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법의 가짓수를 출력하는 프로그램을 작성하세요.
만약 N=15이면
7+8=15
4+5+6=15
1+2+3+4+5=15
와 같이 총 3가지의 경우가 존재한다.

function solution(n) {
  let answer = 0;
  let lt = 1;
  let sum = 0;

  for (let rt = 1; rt < n; rt++) {
    sum += rt;

    while (sum > n) {
      sum -= lt++;
    }

    if (sum === n) answer++;
  }

  return answer;
}
  • rt를 1부터 시작하여 sum에 더한다.
  • sum이 목표값보다 커지면 sum에서 lt를 빼고 lt를 1 증가시킨다. (while문으로 구현)
  • sum이 목표값과 같아지면 answer를 증가시킨다.
function solution(n) {
  let answer = 0;
  let cnt = 1;
  n--;

  while (n > 0) {
    cnt++;
    n -= cnt;
    if (n % cnt === 0) answer++;
  }
  return answer;
}
  • 기발한 방법으로 이런 방법도 있다.
  • 두 개의 연속된 수 1, 2를 n에서 뺀다.
  • 남은 n을 연속된 수의 개수로 나눈다.
  • 나누어 떨어지면 연속된 자연수가 있다는 뜻이다.
  • 이 동작을 n이 0보다 클 때까지 반복한다.

모든 아나그램 찾기

S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하세요.
아나그램 판별시 대소문자가 구분됩니다. 부분문자열은 연속된 문자열이어야 합니다.

function solution(s, t) {
  let answer = 0;
  let n = t.length;
  let sH = new Map();

  for (let i = 0; i < n; i++) {
    sH.set(t[i], sH.get(t[i]) - 1 || -1);
  }

  for (let i = 0; i < n - 1; i++) {
    if (sH.get(s[i]) === -1) sH.delete(s[i]);
    else sH.set(s[i], sH.get(s[i]) + 1 || 1);
  }

  let lt = 0;
  for (let rt = n - 1; rt < s.length; rt++) {
    if (sH.get(s[rt]) === -1) sH.delete(s[rt]);
    else sH.set(s[rt], sH.get(s[rt]) + 1 || 1);

    if (sH.size === 0) answer++;

    if (sH.get(s[lt]) === 1) sH.delete(s[lt]);
    else sH.set(s[lt], sH.get(s[lt]) - 1 || -1);
    lt++;
    console.log(sH);
  }

  return answer;
}

console.log(solution("bacaAacba", "abc"));
  • t문자열을 맵에 -1로 저장하고, s문자열을 순차적으로 조회한다.
  • s문자열을 키로 맵에서 조회해서 1을 더한다.
  • 반복문을 돌 때마다 맵을 조회해서 사이즈가 0이되면 아나그램이라고 판단한다.

0730

15일 차 그리디, 우선순위 큐 문제

동전교환

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환 해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.

function solution(nums, m) {
  let answer = 0;
  let n = nums.length;

  for (let i = n - 1; i >= 0; i--) {
    answer += parseInt(m / nums[i]);
    m = m % nums[i];
  }

  return answer;
}

console.log(solution([1, 5, 10], 15));
  • 그리디 - 그 단계에서 제일 좋은 것을 선택하는 알고리즘
  • 가장 큰 단위의 동전을 돈에서 나눈 값을 answer에 더한다.
  • 나머지 값을 m에 다시 저장한다.
  • 동전의 단위가 배수여야지 그리디 알고리즘을 적용 가능한다.

침몰하는 타이타닉

유럽에서 가장 유명했던 유람선 타이타닉이 침몰하고 있습니다. 유람선에는 N명의 승객이 타고 있습니다.
구명보트를 타고 탈출해야 하는데 타이타닉에 있는 구명보트는 2명 이하로만 탈 수 있으며, 보트 한 개에 탈 수 있는 총 무게도 Mkg 이하로 제한되어 있습니다.
N명의 승객 몸무게가 주어졌을 때 승객 모두가 탈출하기 위한 구명보트의 최소개수를 출력하는 프로그램을 작성하세요.

function solution(nums, m) {
  let answer = 0;
  let n = nums.length;
  let lt = 0;

  nums.sort((a, b) => a - b);

  for (let rt = n - 1; rt >= lt; rt--) {
    if (nums[lt] + nums[rt] <= m) lt++;

    answer++;
  }

  return answer;
}

console.log(solution([90, 50, 70, 100, 60], 140));
  • 배열을 오름차순으로 정렬하고, lt와 rt를 처음과 끝 인덱스로 지정한다.
  • rt가 lt보다 같거나 커질때까지 rt를 감소시키고, 두 인덱스에 위치하는 값들 합이 m보다 작거나 같으면 lt를 증가시켰다.
  • 반복문이 반복되는 횟수만큼 answer를 증가시켰다.

회의실 배정

한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다.
각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라.
단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

function solution(meeting) {
  let answer = 0;

  meeting.sort((a, b) => {
    if (a[1] === b[1]) return a[0] - b[0];
    else return a[1] - b[1];
  });

  let tmp = 0;

  for (let x of meeting) {
    if (tmp > x[0]) continue;

    tmp = x[1];
    answer++;
  }

  return answer;
}
  • 제일 먼저 끝나는 회의를 선택하는 것이 최적
  • 그리디를 사용하는 이유는 n^2를 만들지 않기 위해서이다. 시간복잡도를 nlgn으로 바꾸기 위함

수열의 높이 조정

N길이의 수열이 주어집니다. 수열의 높이 조정은 수열의 원소값 중 가장 큰 원소에서 1을 빼 가장 작은 원소에 더해주는 것을 말합니다. 가장 큰 원소와 가장 작은 원소가 여러개면 그 중 아무거나 선택하면 됩니다.
만약 수열이 [2, 1, 3, 7, 5]라면 1회의 높이조정을 거치면 [2, 2, 3, 6, 5]가 됩니다. N길이의 수열이 주어지면 높이조정을 m회 한 후 가장 큰 값과 가장 작은 값을 차을 출력하는 프로그램을 작성하세요.

function solution(nums) {
  let answer;
  let h = new maxHeap();

  for (let x of nums) {
    h.insert(x);
  }
  while (h.size() > 1) {
    let a = h.get();
    let b = h.get();

    if (a !== b) h.insert(a - b);
  }
  answer = h.get() || 0;

  return answer;
}

console.log(solution([5, 2, 4, 3, 1]));
console.log(solution([7, 6, 3, 2, 4, 5, 1]));
  • maxheap을 사용해서 풀어야 하는 문제이다.
  • 힙을 생성해서 배열의 요소를 모두 삽입하였다.
  • 그 중 큰 수 두개를 꺼내고, 두 개가 다른 경우에만 insert하였다.
  • 이 행위를 힙 사이즈가 1보다 클 때까지 반복해서, 요소가 하나만 남게 하여 그 수를 반환하였다.

maxheap

  • 0번 인덱스에는 큰 숫자를 넣는다.
  • 1번 인덱스가 트리의 루트
  • 왼쪽 자식 인덱스 - 부모 인덱스 * 2
  • 오른쪽 자식 인덱스 - 부모 인덱스 * 2 + 1
  • 자식 인덱스 = 부모 인덱스 / 2 (parseInt 사용)
  • maxheap은 부모의 값이 항상 자식보다 크거나 같다.
class maxHeap {
  constructor() {
    this.heap = [];
    this.heap.push(Number.MAX_SAFE_INTEGER);
  }
  insert(val) {
    this.heap.push(val);
    this.upheap(this.heap.length - 1);
  }
  upheap(pos) {
    let tmp = this.heap[pos];

    while (tmp > this.heap[parseInt(pos / 2)]) {
      this.heap[pos] = this.heap[parseInt(pos / 2)];
      pos = parseInt(pos / 2);
    }
    this.heap[pos] = tmp;
  }
  get() {
    if (this.heap.length === 2) {
      return this.heap.pop();
    }
    let res = this.heap[1];
    this.heap[1] = this.heap.pop();
    this.downheap(1, this.heap.length - 1); // 루트로 올라간 값이 내려가면서 자기 자신을 찾아가는 과정
    return res;
  }
  downheap(pos, len) {
    let tmp = this.heap[pos];
    let child;
    while (pos <= parseInt(len / 2)) {
      child = pos * 2;
      if (child < len && this.heap[child] < this.heap[child + 1]) child++;
      if (tmp >= this.heap[child]) break;
      this.heap[pos] = this.heap[child];
      pos = child;
    }
    this.heap[pos] = tmp;
  }
  size() {
    return this.heap.length - 1;
  }
  show() {
    for (let i = 1; i <= this.size(); i++) {
      console.log(this.heap[i]);
    }
    return true;
  }
}

최대 수입 스케쥴

현수는 유명한 강연자이다. N개이 기업에서 강연 요청을 해왔다. 각 기업은 D일 안에 와서 강연을 해 주면 M만큼의 강연료를 주기로 했다.
각 기업이 요청한 D와 M의 정보를 바탕으로 가장 많을 돈을 벌 수 있도록 강연 스케쥴을 짜야 한다.
단 강연의 특성상 현수는 하루에 하나의 기업에서만 강연을 할 수 있다.

function solution(nums) {
  let answer = 0;
  let h = new maxHeap();

  nums.sort((a, b) => b[1] - a[1]);

  let n = nums[0][1];
  let j = 0;
  for (let i = n; i >= 1; i--) {
    for (; j < nums.length; j++) {
      if (nums[j][1] === i) h.insert(nums[j][0]);
      else break;
    }
    if (h.size() > 0) {
      answer += h.get();
    }
  }

  return answer;
}

console.log(
  solution([
    [50, 2],
    [20, 1],
    [40, 2],
    [60, 3],
    [30, 3],
    [30, 1],
  ])
);
console.log(
  solution([
    [50, 2],
    [40, 2],
    [20, 1],
    [10, 1],
  ])
);
  • 우선 매개변수로 받은 배열을 많이 남은 날짜 순서로 내림차순 한다.
  • 반복문을 돌려서 최대 날짜부터 하루씩 줄여가며 반복하고, 해당하는 날에 있는 스케쥴을 힙에 insert하여 최대 요소만 꺼내 정답에 더한다.

0731

최솟값을 반환하는 minHeap 구현을 했다.

minheap

class minHeap {
  constructor() {
    this.heap = [];
    this.heap.push(Number.MIN_SAFE_INTEGER);
  }
  insert(val) {
    this.heap.push(val);
    this.upheap(this.heap.length - 1);
  }
  upheap(pos) {
    let tmp = this.heap[pos];

    while (tmp < this.heap[parseInt(pos / 2)]) {
      this.heap[pos] = this.heap[parseInt(pos / 2)];
      pos = parseInt(pos / 2);
    }

    this.heap[pos] = tmp;
  }
  get() {
    if (this.heap.length === 2) {
      return this.heap.pop();
    }

    let res = this.heap[1];
    this.heap[1] = this.heap.pop();
    this.downheap(1, this.heap.length - 1);
    return res;
  }
  downheap(pos, len) {
    let tmp = this.heap[pos];
    let child;

    while (pos <= parseInt(len / 2)) {
      child = pos * 2;
      if (child < len && this.heap[child] > this.heap[child + 1]) child++;
      if (tmp <= this.heap[child]) break;
      this.heap[pos] = this.heap[child];
      pos = child;
    }
    this.heap[pos] = tmp;
  }
  size() {
    return this.heap.length - 1;
  }
  show() {
    for (let i = 1; i <= this.size(); i++) {
      console.log(this.heap[i]);
    }
    return true;
  }
}
  • maxheap 구현을 복습하면서 구현했다.
  • maxheap과 반대로 최소의 값을 반환하는 힙 자료구조이다.

0801

교육 과정을 통학하기 시작한 지 1주일이 흘렀다.
정말 많이 공부한거 같은데 고작 5일밖에 안됐다는게 믿기지가 않는다.
혼자 공부했을 때보다 최소 5배이상 빠른 속도로 성장중이다.
코딩테스트에 대한 자신감이 많이 붙은 것 같다.

DFS 예습 문제풀이

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요.

function solution(n) {
  let answer = [];
  let part = [];

  function DFS(L) {
    if (L === n + 1) {
      if (part.length !== 0) answer.push(part.slice());
    } else {
      part.push(L);
      DFS(L + 1);
      part.pop(L);
      DFS(L + 1);
    }
  }
  DFS(1);

  return answer;
}
console.log(solution(3));
  • 코드를 곱씹으면서 스택을 그리고, 어떤 식으로 동작하고 동작시킬지에 대해 고민해봤다.
  • 트리를 그려보고 각 숫자를 선택하고, 선택하지 않고로 나누어서 코딩하면 좀 더 쉽게 접근할 수 있을 것 같다.
  • 우선 코드를 이해했으니 수업을 듣고, 어떻게 하면 생각을 코드로 구현할지에 대해 고민해봐야겠다.

태그:

카테고리:

업데이트:

참고