Life and IT

소개 Linked List는 Array List와 다르게 엘리먼트와 엘리먼트 간의 연결(Link)을 이용해서 리스트를 구현한 것을 의미한다. 그렇다면 연결은 무엇이고 연결이 아닌 것은 무엇인지 생각해볼 필요가 있다. 메모리의 구조 일단 메모리의 구조에 대해서 먼저 알아보겠다. Array List와 Linked List라는 두 회사가 건물의 일부를 임대해서 사용한다고 생각해보자. Array List 회사 이 회사는 모든 직원이 한 곳에 모여있어야 한다는 철학이 있기 때문에 사무실이 모여있다. 만약 회사가 성장해서 사무실이 좁아지면 더 이상 새로운 직원을 뽑을 수 없다. 또한 만약 더 많은 공간이 필요하다면 더 많은 사람을 수용할 수 있는 공간을 찾아 전체가 이사를 해야 한다. Array List는 위의 비..

https://programmers.co.kr/learn/courses/30/lessons/12982 코딩테스트 연습 - 예산 S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 programmers.co.kr 나의 풀이 시간 효율성을 고려해 for문을 사용하였다. 길이가 1인 배열 d를 고려해 조건문을 활용하여 early return 하였다. function solution(d, budget) { let answer; if (d.length === 1) { return answer = d[0] a - b); for (let i = 0; i < d.length; i++) ..

이번 글에서는 정렬 알고리즘 중에서 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번을..