inflearn78 [ 자바스크립트(JavaScript) ] section07 - 4 - 삽입정렬 📍 section07 - 4 - 삽입 정렬 삽입 정렬은 선택정렬과 비슷하지만 조금은 다른 방식이다. 삽입 정렬의 간략한 소개는 삽입 정렬 5분 만에 이해하기 - Gunny의 영상을 확인하자. 삽입 정렬은 선택 정렬보다 시간 복잡도면에서 효과적인 알고리즘인데 만약, 데이터가 거의 정렬되어있다고 가정하면 while문을 거의 수행하지 않으므로 O(N)의 시간복잡도를 보여준다. 하지만 데이터가 역 정렬(반대로 정렬)되어있다면 index 끝까지 while문을 수행하므로 최악의 경우인 O(N^2)을 나타낸다. 1. i가 1부터 시작하여 n까지 탐색한다. (left 인덱스 사용으로 인해 0부터 시작을 하지 않음) 2. temp에 arr[i]를 선언한다. (나중에 덮어 씌운 값 맨 앞에 넣을 예정) 3. left가 0.. 2021. 9. 9. [ 자바스크립트(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. 이전 1 ··· 5 6 7 8 9 10 11 ··· 16 다음
