안녕하세요 최근에 알게된 코딜리티 사이트에서 가입하고 나면 하는 튜토리얼 알고리즘이 있는 것 같아


기록 차 남깁니다!! 



** 문제의 경우는 사이트에 들어가시면 좀 더 자세히 확인이 가능 합니다!!


// 코딜리티 사이트 

https://app.codility.com


1 Binary Gap


정수인 N에 대하여 바이너리 갭을 구하는 1번째 튜토리얼 입니다. 제로 (0) 의 값이 제일 많은 수를 구하면됩니다.

1과 1사이에 대해서만 


만약에 10000100 이라면  10000100 이 부분이 더 많으니까 리턴 은 4가 되어야 합니다.


하지만 1000000000 으로 된다면 다음 1이 없기 때문에 사이값을 지정할수 없어 리턴은 0이 됩니다.


또 다른 케이스를 볼까요?


11111111 와같이 되어도 0이 개수가 없기 때문에 리턴은 0이 됩니다.


실행 가능한 N의 정수는


  • N is an integer within the range [1..2,147,483,647].


와 같습니다. (사실 이부분 때문에 어떻게 풀어야 하나 고민 된 부분이 하나 있습니다. : -> 2진수 변환시 )


예시로 준 값에 대해서는 샘플 결과는


1041 -> 5


32 -> 0 


등등이 있습니다.


** 참고로 해야 할 점 

JavaScript 에서는 Number.prototype.toString을 통해서 2진수로 변환할 수 있습니다.


var numberValue = 1041;

numberValue.toString(2); // "10000010001"


이 방법을 쓰기 위해서 알고리즘을 하는 건 아니니까 최대한 지양 하도록 합시다 !



[풀이]

2진수 변환 을 우선 먼저 해주어야 하는데 일단 단순하게 생각해보았을 경우는

/2 로 나누면서 몫과 나머지를 계산 하는 방식입니다. 


단순 반복문


  while(N>=1){
      // share Check
      let share = N%2;
      binArr.push(share);
      
      // rest Check and Integer
      N = Math.floor(N/2);
      
  }
binArr = binArr.reverse();


우선 N 의 값은 1까지 나누어야 하기 때문에 1보다 낮아질 경우 까지 무한반복을 합니다.

나머지 값(share) 을 찾아서 배열에 추가


JS에서는 /2를 하게되면 실수형 연산이 되기때문에 Math.floor 로 소수점을 버립니다.


위와같이 계산하게되면 2진수는 반대이기 때문에 reverse를 호출하여 이진수 형태를 만듭니다.

(** 문제점이 있다면 아래의 조건이 없었을 경우 아래조건보다 더 커지게 되면

  • N is an integer within the range [1..2,147,483,647].
12831273127382173912739012739821739081273980213 // 1.2831273127382173e+46

위와같이 나타나서 2진수 계산이 되지 않습니다. (하지만 조건이 있기에 위와같이 단순계산하는게 속도상 제일 빠릅니다.)

재귀 함수


function s(d,v){
  const share = Math.floor(v / d);
  const rest = v % d;
  
  if(d > share){
    return '' + share + rest;
}else {
    return '' + s(d,share) + rest;
}
}

s(2,1041); // "10000010001"


재귀로 하게되면 위의 N의조건이 없었을시에는 계속 가능합니다. 마지막 콜스택에서

찾아 올라오기 때문에 reverse도 할 필요 없구요 (하지만 속도가 좀더 느리더군요)




갭 구하기 


갭을 구해야 합니다. 조건을 나름 정해 보았습니다.

- 1 다음부터 카운트를 해야 하고 다시 1을 만났을때 그사이에 0 의 값에 대한 카운트는 Fixed가 된다.

(Fixed시 기존에 카운트 값이 있다면 크기 비교 후 더 큰 쪽을 Fixed한다.)

- 1 다음부터 카운트를 하였는데 1이 다시 안나온다면 값을 0으로 Fixed 된다.

- 1 만 나왔을 경우 값은 계속 0을 유지한다. 

- 1이 나오게 되면 진행 중이라는 플래그 값이 필요 할 것 같다.(running)


Binary Gap 은 간단하기에 위와같은 풀이식을 적용한 솔루션 적어 놓겠습니다.



// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(N) {
  // write your code in JavaScript (Node.js 8.9.4)
  let binArr = [];
  
  while(N>=1){
      // share Check
      let share = N%2;
      binArr.push(share);
      
      // rest Check and Integer
      N = Math.floor(N/2);
      
  }
  // binary Reverse
  binArr = binArr.reverse();
  // gap Max Value
  let currGapMax = 0 ;
  let running = false;
  
  // 1 1 0 0 0 0 0 0
  binArr.reduce(function(prev,curr,index,arr){
      // check Starting
      if(curr===1 && running ===true){
          currGapMax = currGapMax < prev ? prev : currGapMax;
          prev = 0 ;
          return prev;
      }
      // check Counting
      else if(running === true && curr===0){
          prev+=1;
          return prev;
      }
      else if(curr===1){
          running = true;
          return prev;
      }
  },0);
  
  
  return currGapMax;
  
}


조건이 단순 양수 값이였다면 재귀 형태를 사용 했을 것 같습니다.

(JS의 toString(2) 도 그런 것으로 보입니다.)

N의 조건을 두었기 때문에 위와같이 단순 계산을 사용하였습니다.


감사합니다.



안녕하세요 알고리즘 공부를 시작하려고 합니다.

물론


자바스크립트를 기준으로 하려고합니다.  관련 서적으로 Introduction to algorithms 를 사긴 했는데 너무 수준이? 높다고 해야될까요 갑자기 사놓고 동공지진...이 왔네요  그래서 책은 가끔 눈으로만 읽고 


책을 읽기전에 기본적으로 볼려고 하는 To do List 를 뽑아봤어요  해당 To do list 는 어느 한 포스팅을 참고 하였구요


미디엄이라는 곳에서 사람들이 포스팅 하는 내용중 


// 자바스크립트에서의 알고리즘 

https://medium.com/siliconwat/algorithms-in-javascript-b0bed68f4038


에서 포스팅에 대한 내용을 하나씩 이해 하면서 적어 볼려고 해요 


유명한 알고리즘 문제에 대한 설명이 잘되어있어서 이부분에 대한 이해를 할거고 그 아래에 다른 내용들은


제가 따로 조사해서 포스팅 하려고합니다. 


회사일이 많아 빠르게 되진 않겠지만 시작이 반이잖아요 해보겠습니다.


유명한 알고리즘 문제 22선 


1. 문자열 반전(String Reversal)


2. 팰린드롬(Palindrome)


3. 정수 반전(Integer Reversal)


4. 피즈버즈 (Fizz Buzz)


5. 최대 문자(Max Character)


6. 철자 바꾸기(Anagrams)


7. 모음체크(Vowels)


8. 배열 묶음(Array Chunking)


9. 배열 반전(Reverse Array)


10. 문자 뒤집기(Reverse Words)


11. 문자비교 (Capitalization)


12. ?Caesar Cipher


13. 랜덤 노트 (Random Note)


14. Mean ,Median,and Mode 


15. Two Sum


16. Max Profit


17. Sieve of Eratosthenes


18. 피보나치(Fibonacci)


19. 메모이제이션 피보나치 (Memoized Fibonacci)


20. Staircase


21. Pyramid (피라미드)


22. Matrix Spiral 


자료구조 알고리즘 

( 도전 -> 1. MidPoint  2. Circular 3. From Tail 4. Trees)


1. 큐    2. 스택     3. 링크드리스트


정렬 알고리즘


1. 버블 정렬 2. 삽입정렬 3. 선택정렬 4. 퀵정렬 5. 합병 정렬 6. 카운팅 정렬


검색 알고리즘


1. 이진 검색 2. 이진 검색 트리


/ 분할 정복기법 , 동적프로그래밍, 그리디알고리즘


+ Recent posts