Algorithm/인프런(inflearn)86 [ 자바스크립트(JavaScript) ] section07 - 3 - Special Sort(구글 인터뷰) 📍 section07 - 3 - Special Sort(구글 인터뷰) 문제: 음의 정수는 앞쪽에 양의 정수는 뒤쪽에 있어야 한다. 이때, 양의 정수와 음의 정수의 순서는 변함이 없어야 한다. GeeksforGeeks에서 관련 문제를 가져왔다. 영어로 풀고 싶으면 사이트에 들어가서 푸는것을 권장한다. 이 문제를 풀때 2가지 방법이 떠올랐다. 한 개는 for문을 돌면서 음수 먼저 answer에 push하고 또 for문을 돌면서 양수를 answer에 push 하는 방법 버블 정렬 방식의 일부를 가져와서 j가 음수이고 j+1이 양수면 swap하는 방법 시간 복잡도는 1번(O(N))으로 더 빠르지만 만약, 코딩 인터뷰를 할 때 정렬을 이용해서 풀어보라고 할 때는 2번(O(N^2))을 이용하면 된다. // 1번 방.. 2021. 9. 8. [ 자바스크립트(JavaScript) ] section07 - 2 - 버블정렬 📍 section07 - 2 - 버블정렬 구현하기 쉬운 정렬 중 한 개다. 데이터가 정렬되는 모습이 버블 같아서 붙여진 이름이다. (데이터가 왼쪽으로 이동하는 모습이 거품이 올라오는 모습 같은가?) 버블 정렬은 다른 정렬에 비해 구현이 쉽다는 장점을 가지고 있다.(이중 반복문) 하지만, 시간 복잡도는 O(N^2)가 걸리므로 실제 많이 쓰이지는 않는다. (이미 정렬이 되어있는 최적화의 경우에는 O(N) 걸린다.) j가 돌 때마다 j+1과 매번 비교한다.(실행 횟수가 많다.) i가 한 바퀴 돌고 난 이후 다음 j번을 돌 때 i의 맨 마지막 값이 하나 줄어든 범위까지만 탐색한다. (1번을 거치면서 제일 큰 값은 맨 뒤로 가있다고 확정을 짓는다.) let n = 6; let arr = [13, 5, 11, 7,.. 2021. 9. 8. [ 자바스크립트(JavaScript) ] section07 - 1 - 선택정렬 📍 section07 - 1 - 선택정렬 이번 섹션은 정렬(sort), 그리디(greedy), 결정 알고리즘에 대해서 배운다. 블로그에 따로 게시하진 않았지만 이전에 종종 삽입정렬, 선택정렬, 병합정렬, 버블정렬, 퀵정렬 코드 구현까지 공부했는데, 항상 정렬 문제를 풀 때마다 알맞은 정렬 코드를 구현하려고 하면 까먹는다. 😅 😅 이번 섹션을 풀면서 언제 어떤 정렬을 사용해야 하는지 잘 알아둬야겠다. 선택 정렬에 관한 짧은 영상은 선택정렬 5분만에 이해하기 - 코딩하는거니 개인적으로 이 분 영상이 길지 않고 핵심만 가르쳐주는 영상이어서 좋았다. 선택 정렬은 가장 작은 숫자를 차례대로 탐색하여 가장 왼쪽 자리부터 swap 하는 정렬이다. 이중 반복문으로 전체 원소를 탐색하고 나보다 작은 값이 있으면 두 개의.. 2021. 9. 7. [ 자바스크립트(JavaScript) ] section06 - 7 - 교육과정 설계 📍 section06 - 7 - 교육과정 설계 현수가 짠 수업 설계도가 주어진 수업계획표와 맞는지 검증하는 문제다. 마찬가지로 queue 자료구조를 사용하면 되는데, 현수의 수업 설계도를 앞에서부터 하나씩 꺼내서 비교해야 한다. 그런데 while문 보다는 for문을 사용해야하는데 만약, 수업계획표가 수업 설계도에 하나도 포함이 되어있지 않으면 while문이 멈추지 않는다. 따라서 for문을 사용해 수업설계도에 하나씩 접근하면서 수업 계획표가 있는지 살펴보는 방법이 괜찮은 접근 방법일 것이다. 나는 이렇게 풀었다. 수업 설계도를 배열로 만든다.(split) 수업 계획표(target)를 하나씩 돌면서 수업 설계도(s)도 한 번씩 돈다. 수업 설계도의 맨 앞과 수업 계획표의 맨 앞이 똑같으면 cnt++하고 s.. 2021. 9. 2. [ 자바스크립트(JavaScript) ] section06 - 6 - 공주구하기 📍 section06 - 6 - 공주구하기 공주 구하기 문제는 이전에 풀었던 요세푸스 문제와 동일하다. 요세푸스 문제는 큐(queue) 자료구조를 사용하면 풀 수 있다. 선생님께서는 이렇게 설명해주셨다. arr에 length가 1개일 때까지 반복한다. for문을 사용해 k-1번 돌린다. arr[0]을 맨 뒤로 넣는다. k번째 사람이 제외되어야 하므로 다음 값은 shift()한다. // 강의 코드 let n = 8; let k = 3; console.log(solution(n, k)); function solution(n, k){ let arr = Array.from({length: n}, (v, i) => i+1); while(arr.length>=2){ for (let i=0; i idx + 1); l.. 2021. 9. 2. 이전 1 ··· 5 6 7 8 9 10 11 ··· 18 다음
