Life and IT

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 = []..

https://programmers.co.kr/learn/courses/30/lessons/81301?language=javascript 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr 나의 풀이 정규 표현식을 사용하여 0부터 9까지 replace 함수를 메소드 체이닝 하였다. 그리고 parseInt로 감싸서 숫자로 반환하였다. function solution(s) { return parseInt(s.replace(/zero/g, "0") .replace(/one/g, "1") .replace(/t..

두 가지 요소 - 보조 공간과 입력 공간 보조 공간 : 알고리즘이 실행을 위해 사용하는 임시 공간 입력 공간 : 입력의 크기를 고려하여 실행 시 필요한 공간 공간 복잡성을 평가하기 위해 보조 공간만 사용되는 시나리오가 있지만 이 글에서는 전체 공간(보조 및 입력)을 사용할 것이다. 공간 복잡도는 메모리 또는 데이터 저장의 사용을 평가하기 위해 고려하는 사항이다. 알고리즘은 몇 가지 작업을 수행하기 위해 메모리를 사용해야 한다. 프로그램 명령어 저장 (컴파일러 => 런타임) 실행 (예: 함수 호출, 점프 문) 데이터 저장(예: 상수 및 변수 값) 여기서 저장된 변수 데이터는 주요 고려 사항이다. 시간 복잡도와 마찬가지로 공간 복잡도는 일반적으로 빅오 표기법으로 표시된다. 예시 1) function add(..

빅오는 알고리즘이 얼마나 빠르게 실행될지를 비교할 때 사용된다. 시간 복잡도(Time complexity)를 통해서 알고리즘의 빠르기를 비교할 수 있다. 빅오( O ), 세타( Θ ), 오메가( Ω ) 시간 복잡도를 표기할 때에는 빅오만 표기하지 않는다. 최악, 평균, 최상의 경우에 따라서 빅오, 빅 세타, 빅 오메가를 표기한다. O(n): 최악의 경우 Θ(n): 평균의 경우 Ω(n): 최상의 경우 하지만 알고리즘을 평가할 때 보통 최악의 경우를 본다고 한다. 왜일까? 왜냐하면 최상의 경우는 유용한 정보가 아니기 때문이라고 한다. 사실상 대부분의 알고리즘에 특별한 입력 값을 이용하면 O(1)을 달성할 수 있을 것이다. 즉 최악의 상황에서도 이 정도의 성능은 보장할 수 있다는 것을 알려주는 것이 더 유용하..

https://programmers.co.kr/learn/courses/30/lessons/70128 코딩테스트 연습 - 내적 길이가 같은 두 1차원 정수 배열 a, b가 매개변수로 주어집니다. a와 b의 내적을 return 하도록 solution 함수를 완성해주세요. 이때, a와 b의 내적은 a[0]*b[0] + a[1]*b[1] + ... + a[n-1]*b[n-1] 입니다. (n은 a, b의 programmers.co.kr 풀이 a 배열을 원소 a와 인덱스 i로 맵핑해서 각 값에 b[i]를 곱한다. 바로 reduce로 a 배열을 누산한다(초기값 0으로 설정). var solution = (a, b) => a.map((a,i) => a * b[i]).reduce((acc,cv)=>{return acc..

https://programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 풀이 일치하는 번호의 배열 cor_list와 가려져 보이지 않는 배열 zero_list를 만들었다. win_nums에 대한 forEach 메소드로 값과 인덱스를 불러왔다. 그리고 lottos 배열에도 들어있는 숫자들을 cor_list에 넣었다. lottos의 가려진 숫자 0은 zero_list에 넣었다. 최고 순위는..

https://programmers.co.kr/learn/courses/30/lessons/17681 코딩테스트 연습 - [1차] 비밀지도 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다 programmers.co.kr 풀이 arr1과 arr2 두 배열을 각각 2로 계속 나누어 나머지가 1이면 1, 없다면 0을 새로운 배열에 집어넣었다. 그렇게 2진수로 변환하여 for문을 돌려 각 자리마다 2진수를 더했고 1 이상인 경우 #을, 0이라면 공백을 집어넣었다. 마지막으로 join('')을 사용하여 배열을 문자열로 변환하였다. ㅠㅠ 2진수로 변환하는 과정을 간소화할 방법이 떠..

https://programmers.co.kr/learn/courses/30/lessons/76501 코딩테스트 연습 - 음양 더하기 어떤 정수들이 있습니다. 이 정수들의 절댓값을 차례대로 담은 정수 배열 absolutes와 이 정수들의 부호를 차례대로 담은 불리언 배열 signs가 매개변수로 주어집니다. 실제 정수들의 합을 구하여 re programmers.co.kr 풀이 reduce 메소드를 활용하였고, 삼항 연산자로 signs의 값에 따라 부호를 부여하였다. 그리고 answer에 덧셈 누산을 시켜 값을 반환하였다. function solution(absolutes, signs) { var answer = 0; absolutes.reduce((acc,cv,idx) => { cv = signs[idx]..