본문 바로가기

Algorithm272

[ 자바스크립트(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.
[ 논리적사고 ] - 누적 값이 point보다 높은지 낮은지 비교하고 추가하기 📍 누적 값이 point보다 높은지 낮은지 비교하고 추가하기 제목은 거창하게 작성했지만, 내용은 쉬운 글이다. 이진 탐색의 결정 알고리즘 문제를 풀면서 작은 skill(?)을 남겨 놓고 싶어 작성했다. 예를 들어, 현재까지 누적된 sum=6이고, 다음 x값을 누적할 때 point보다 높으면 continue하고, 높지 않으면 포함시키는 방법을 작성하고 싶다면 어떻게 작성할까? 다음과 같이 작성할 수 있다. let arr = [1, 3, 2, 5, 1, 1, 1]; let point = 10; let sum=0; for (let x of arr){ if(sum+x>point)continue else sum+=x; } 이를 응용해서 currentTime에 songTime값을 누적할 때 만약, 다음 songTi.. 2021. 9. 8.
[ 자바스크립트(JavaScript) ] section07 - 1 - 선택정렬 📍 section07 - 1 - 선택정렬 이번 섹션은 정렬(sort), 그리디(greedy), 결정 알고리즘에 대해서 배운다. 블로그에 따로 게시하진 않았지만 이전에 종종 삽입정렬, 선택정렬, 병합정렬, 버블정렬, 퀵정렬 코드 구현까지 공부했는데, 항상 정렬 문제를 풀 때마다 알맞은 정렬 코드를 구현하려고 하면 까먹는다. 😅 😅 이번 섹션을 풀면서 언제 어떤 정렬을 사용해야 하는지 잘 알아둬야겠다. 선택 정렬에 관한 짧은 영상은 선택정렬 5분만에 이해하기 - 코딩하는거니 개인적으로 이 분 영상이 길지 않고 핵심만 가르쳐주는 영상이어서 좋았다. 선택 정렬은 가장 작은 숫자를 차례대로 탐색하여 가장 왼쪽 자리부터 swap 하는 정렬이다. 이중 반복문으로 전체 원소를 탐색하고 나보다 작은 값이 있으면 두 개의.. 2021. 9. 7.
[ 논리적사고 ] - 배열 중간에 있는 값을 맨 앞으로 옮기기 📍 배열 중간에 있는 값을 맨 앞으로 옮기기 배열 중간에 있는 값을 맨 앞으로 옮길 때는 2가지의 방법이 있다. 한번 코드로 살펴보자. 1. temp로 target을 빼내는 방법: target이 몇 번째 index에 있는지 찾는다. -> temp에 저장한다. -> 한 칸씩 뒤로 미룬다. -> 맨 앞에 temp값을 넣는다. 2. splice방법: target이 몇 번째 index에 있는지 착는다 -> temp변수에 splice 값을 넣는다. -> 맨 앞에 unshift()한다. let arr = [2, 3, 1, 5, 6]; let target = 1; // target이 arr의 몇 번째 idx에 위치해있는지 찾기 let pos=-1; for (let i=0; i=1; i--){ arr[pos] = ar.. 2021. 9. 3.

티스토리툴바