DS & Algorithm/basic

[기초 알고리즘] 최대공약수 최소공배수 찾기(유클리드 호제법) - 자바스크립트

유클리드 호제법 유클리드 호제법이란, 2개의 자연수의 최대공약수를 구하는 알고리즘 중 하나이다. 유클리드 호제법에 의하면 A와 B 두 수의 최대공약수를 구할 때, A = Bq+r의 식으로 만든 뒤 B와 r의 최대공약수를 구하는 문제로 바꿀 수 있다. 연속되는 B, r의 최대공약수에 대해서도 B = rq+r2 와 같이 재귀가 가능하다. 최대공약수는 A,B 모두 나누어 떨어뜨리는 최대의 약수이므로, r=0 일 때 B의 값이 최대공약수이다. 최대공약수 구하기 유클리드 호제법을 이용해 최대공약수를 구해보자. 반복문 사용하기 function gcd(a,b){ let c = 0; while(b !== 0){ c = a % b; a = b; b = c; } return a; } 재귀함수로 만들기 function gc..

[기초 알고리즘] 멘토링 - 자바스크립트

문제 현수네 반 선생님은 반 학생들의 수학점수를 향상시키기 위해 멘토링 시스템을 만드려 한다. 멘토링은 멘토(도와주는 학생)와 멘티(도움을 받는 학생)가 한 짝이 되어 멘토가 멘티의 수학공부를 도와주는 것이다.. 선생님은 M번의 수학테스트 등수를 가지고 멘토와 멘티를 정한다. 만약 A학생이 멘토이고, B학생이 멘티가 되는 짝이 되었다면, A학생은 M번의 수학테스트에서 모두 B학생보다 등수가 앞서야 한다.. M번의 수학성적이 주어지면 멘토와 멘티가 되는 짝을 만들 수 있는 경우가 총 몇 가지 인지 출력하는 프로그램을 작성하라. 입력 설명 M개의 줄에 걸쳐 수학테스트 결과가 학생번호로 주어진다. 학생번호가 제일 앞에서부터 1등, 2등, ...N등 순으로 표현된다. 만약 N=4이고, 테스트 결과가 3 4 1 ..

[기초 알고리즘] 가장 짧은 문자거리 - 자바스크립트

문제 한 개의 문자열 s와 문자 t가 주어지면 문자열 s의 각 문자가 문자 t와 떨어진 최소거리를 출력하는 프로그램을 작성하라. 문자열 s와 문자 t는 소문자로만 주어지며, 문자열의 길이는 100을 넘지 않는다. 입력 예제 teachermode, e 출력 예제 1 0 1 2 1 0 1 2 2 1 0 첫 풀이 우선 거리를 구해야 한다. e의 인덱스가 담긴 배열을 우선 구해보자. 문자열 s를 순회하면서, s의 각 인덱스를 가지고 e의 인덱스가 담긴 배열의 요소 중에서 어떤 것과 가장 차이가 적은지를 구하자. function solution(s, t) { let answer = ""; let index = 0; const indexE = []; while (true) { let findIndex = s.ind..

[기초 알고리즘] 봉우리 - 자바스크립트

문제 지도 정보가 N*N 격자판에 주어진다. 각 격자에는 그 지역의 높이가 쓰여 있다. 각 격자판의 숫자는, 자신의 상하좌우 숫자보다 큰 숫자를 가졌을 때 봉우리라고 불린다. N*N 격자판에서 봉우리가 몇 개 있는지 알아내보자. 격자의 가장자리는 0으로 초기화 되었다고 가정한다. 그러므로 N=5이고 격자판의 숫자가 아래와 같다면, 봉우리 개수는 10이 출력되어야 한다. 나의 풀이 각 격자를 조회하기 위해 2중 for문을 돌려야 한다. 5*5의 격자에서 가장자리에 있는 높이들을 평가할 때, 배열의 범위를 벗어나는 참조를 주의한다. function solution(arr){ const n = arr.length; let peakCount = 0; for(let i = 0; i < n; i++){ for(le..

[기초 알고리즘] 등수 구하기 - 자바스크립트

문제 N(1 1); //[1, 1, 1, 1, 1, 1] 다음과 같이 배열의 크기 정보를 가지고, 원하는 초기 값을 넣어줄 수 있다. 참고 : Array.from

[기초 알고리즘] 최솟값 구하기 - 자바스크립트

문제 배열로 7개의 수가 주어지면, 그 숫자 중 가장 작은 수를 출력하는 프로그램을 작성하라. (정렬을 사용하지 않고 실행해야한다.) 나의 풀이 function solution(arr) { let min = Number.MAX_SAFE_INTEGER; for (let i = 0; i arr[i]) min = arr[i]; } return min; } let arr = [5, 3, 7, 11, 22, 15, 17]; console.log(solution(arr)); 답은 간단하다. 배열의 요소를 순회하면서 가장 작은 값을 구해주면 된다. 여기서 min을 선언할 때, Number.MAX_SAFE_INTEGER 를 사용하였는데, 이건 자바스크립트에서 안전..