Life and IT

이번 글에서는 정렬 알고리즘 중에서 Bubble 정렬, Insertion 정렬에 대해서 알아보고 구현해보려고 한다. Bubble Sort 버블 정렬은 최악의 시나리오에서 가장 비효율적인 정렬 알고리즘이지만, 우리가 이해하기 가장 쉬운 방식이다. 버블 정렬은 배열을 반복하고 각 인덱스를 옆에 있는 인덱스와 비교한다. 그리고 서로 크기 비교를 하며 모든 값들이 순서에 맞게 위치할 때까지 루프를 반복한다. 인덱스를 스왑 하는지를 확인하는 내부 루프와 교체된 항목이 있는지 확인하는 외부 루프가 있다. 따라서 버블 정렬의 시간 복잡도는 O(n^2)이다. 버블 정렬을 아래 코드로 구현해보았다. function bubbleSort (nums) { let i = 0; while(i < nums.length) { num..

Stack은 queue 없이 이야기할 수 없다. 큐는 First-In First-Out을 따른다. 큐는 대기열이며, 사람들이 줄을 서는 것과 비슷하다. 스택처럼 큐도 마찬가지로 대기열에서 빼낼 다음 요소가 무엇인지 엿볼 수 있다. 큐는 프린터기처럼 요청한 작업을 순서대로 처리한다. 하지만 Priority queues라는 것도 존재한다. 우선 순위우선순위 큐는 큐 안의 요소에도 우선순위를 할당한다. 따라서 우선 순위가 높은 항목이 먼저 큐에서 제거된다. 이것은 네트워킹에 유용하다. 일부 패킷은 다른 패킷보다 더 중요하기 때문이다. 비디오를 스트리밍하는 경우 나중에 패킷을 받으면 일부 프레임을 건너뛸 가능성이 높기 때문에 우선순위가 높다. 반면 Dropbox에 동기화하면 동기화를 계속하기 위해 네트워크 트래..

Stack 스택은 "Last-In First-Out"을 따르는 인터페이스이다. 스택(추가)에서는 푸시(제거) 또는 팝만 할 수 있다. 또한 마지막으로 푸쉬한 것은 곧 팝이 반환하는 것과 같다. 종종 스택을 수정하지 않고 스택의 최상위 값만 다루는 peek라고 부르는 메서드를 가지게 될 것이다. 다음 코드를 보자. function double(x) { return 2 * x; } function squareAndAddFive(y) { return square(y) + 5; } function square(z) { return z * z; } function maths(num) { var answer = double(num); answer = squareAndAddFive(answer); return ans..

https://programmers.co.kr/learn/courses/30/lessons/85002 코딩테스트 연습 - 6주차_복서 정렬하기 복서 선수들의 몸무게 weights와, 복서 선수들의 전적을 나타내는 head2head가 매개변수로 주어집니다. 복서 선수들의 번호를 다음과 같은 순서로 정렬한 후 return 하도록 solution 함수를 완성해주세요 programmers.co.kr 나의 풀이 function solution(weights, head2head) { const objList = []; const answer = []; head2head.forEach(function (strScore, strIndex) { let winMoreWeight = 0; let obj = {}; strSc..

https://programmers.co.kr/learn/courses/30/lessons/83201?language=javascript 코딩테스트 연습 - 2주차_상호평가 [[100,90,98,88,65],[50,45,99,85,77],[47,88,95,80,67],[61,57,100,80,65],[24,90,94,75,65]] "FBABD" [[70,49,90],[68,50,38],[73,31,100]] "CFD" programmers.co.kr 나의 풀이 이중 for 문에서 2차원 배열인 scores의 각 학생들에 대한 점수를 sum에 push 하였다. 조건으로 유일한 최고점 또는 최저점인 경우 splice로 제거하였다. 이후에 sum을 reduce 하고 sum의 길이로 나눔으로써 평균을 sumLi..

Quick Sort 1960년에 제안되었으며 이후 많은 사람들이 수정 및 보완하여 완성된 정렬 알고리즘이다. 소개된 지 반 세기가 넘었지만 현존하는 가장 빠른 정렬 알고리즘 중에 하나이다. 퀵 정렬은 in place 방법과 in place가 아닌 방법 2가지가 있는데, 실제로 많이 쓰이는 방법은 메모리 사용량이 적은 in place 방법이다. 그러나 in place가 아닌 방법이 더 직관적으로 이해하기 쉬우므로 이 방법을 먼저 정리하고 그다음 in place 방법을 정리하겠다. Basic Quick Sort - Not In Place 퀵 정렬은 지난 Merge Sort에서 소개한 Divide and Conquer 전략을 사용한 알고리즘이다. 즉, 정렬하는데 가장 간단한 배열은 바로 요소가 없거나 하나만 ..

https://programmers.co.kr/learn/courses/30/lessons/17682?language=javascript 코딩테스트 연습 - [1차] 다트 게임 programmers.co.kr 다트 게임의 계산 로직을 풀어보았다. *의 경우 자신과 뒤에 값에 2를 곱해주어야 해서 가장 나중에 계산하려고 했다. 따라서 S, D, T, #의 경우에 계산되는 값을 먼저 계산하였다. 이 과정에서 reduce를 사용하여 유일한 두 자리 숫자인 10은 이전 값과 현재 값을 문자열 더하기로 합쳐주었다. 그 후에 *을 찾고, 값을 계산하고 splice로 *을 없애주었다. 이 때문에 forEach가 아닌 for문을 사용하였다. 마지막으로 reduce로 누적 계산하여 답을 도출했다. 나의 풀이 functi..

Sorting은 일반적으로 검색과 함께 사용된다. Sorting 된 리스트는 그렇지 않은 리스트보다 검색하기가 더 쉽다. 주어진 리스트의 요소들을 정렬하는 방법은 많다. 이번 글에서는 Merge sort에 대해 알아본 내용을 정리해보려고 한다. Merge sort Merge sort는 인기 있는 방법 중 하나이며, 효율적인 방법이다. Logic Merge sort는 문제를 직접적으로 풀기 충분할 때까지 반복하여 주어진 배열을 쪼갠다. 다음 4가지 단계를 통해 그 과정을 확인해보자. 배열을 절반씩 두 개로 쪼갠다(홀수일경우 최대한 절반씩). 하나의 요소만을 가진 배열이 될 때까지 1번의 방식을 반복한다. 단일 요소 배열에서부터 시작하여, 배열을 합쳐서 sort 한다. 하나의 정렬된 배열이 될 때까지 3번을..

https://programmers.co.kr/learn/courses/30/lessons/42862?language=javascript 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 예전에 통과하지 못하고 다른 사람의 풀이를 보았던 문제이다. 지금이라면 풀 수 있을까 하여 다시 풀어보았고, 통과하였다! function solution(n, lost, reserve) { const lostFilterdAndSorted = lost.filter(number => !reserve.includes(number))...

https://programmers.co.kr/learn/courses/30/lessons/86491?language=javascript 코딩테스트 연습 - 8주차 [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] 120 [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] 133 programmers.co.kr 나의 풀이 한 쌍의 값 중 큰 값을 large 리스트에 push 하고, 작은 값은 small 리스트에 push 하였다. 그리고 large 리스트에서 가장 큰 값과, small 리스트에서 가장 큰 값의 크기를 answer에 선언하여 리턴했다. function solution(sizes) { const largeSideNumber = []..