Fall in IT.

힙 정렬(Heap Sort)의 특징 힙 정렬의 핵심 아이디어는 힙 트리 구조를 사용하여 정렬한다. 시간 복잡도 O(N * logN) 사전 지식 이진트리(Binary Tree): 모든 노드의 자식 노드가 2개 이하인 트리 완전 이진트리: 데이터가 루트노드부터 시작해서 자식 노드까지 왼쪽부터 오른쪽으로 차례차례 들어가 있는 형태의 트리 힙(Heap): 최소값이나 최댓값을 빠르게 찾아내기 위해서 완전 이진트리를 기반으로 하는 구조를 말한다. 코드 아래 코드는 상향식 구현 방식을 사용하였습니다. 하양식으로 구현하여도 무방합니다. function solution(heap) { let length = heap.length; let temp = 0; /** * 먼저 전체 트리구조를 최대 힙 구조로 바꾼다. * 즉, ..

기본적인 정렬 알고리즘에는 삽입, 선택, 버블, 퀵, 병합정렬 등이 있습니다. 이 중에서 병합정렬에 대해서 알아보도록 하겠습니다. 병합정렬(Merge Sort)의 특징 병합정렬의 핵심 아이디어는 "일단 반으로 나누고 나중에 합쳐서 정렬한다." 입니다. 시간 복잡도 O(N * log N) 퀵 정렬과 다르게 최악의 경우에도 O(N * logN)을 보장합니다. 코드 /** * 병합정렬의 핵심 아이디어, * `일단 반으로 나누고 나중에 합쳐서 정렬한다.` * * 퀵정렬과 다르게 항상 속도는 O(N * logN)이 된다. * 퀵정렬과 동일하게 분할정복법과 재귀함수를 사용한다. */ function solution(arr) { let sortedArr = []; mergeSort(arr, 0, arr.length ..

문제 자바스크립트의 Number객체의 내장 함수인 toString() 함수와 전역 함수인 parseInt() 함수를 사용하면, 진수변환을 간단하게 처리할 수 있습니다. 사용 방법 /** * 진수 변환 * * 10진수를 진수 변환할때는 Number객체의 내장 함수인 toString()을 사용한다. * 10진수 외의 다른 진수를 10진수로 변환할때는 전역 함수인 parseInt()을 사용한다. */ // 1. 10진수 -> 2진수 let 십진수 = 125; console.log(`1. 10진수(${십진수}) -> 2진수(${십진수.toString(2)})`); // 1111101 // 2. 10진수 -> 8진수 console.log(`2. 10진수(${십진수}) -> 8진수(${십진수.toString(8)}..

다트 게임 카카오톡에 뜬 네 번째 별! 심심할 땐? 카카오톡 게임별~ 카카오톡 게임별의 하반기 신규 서비스로 다트 게임을 출시하기로 했다. 다트 게임은 다트판에 다트를 세 차례 던져 그 점수의 합계로 실력을 겨루는 게임으로, 모두가 간단히 즐길 수 있다. 갓 입사한 무지는 코딩 실력을 인정받아 게임의 핵심 부분인 점수 계산 로직을 맡게 되었다. 다트 게임의 점수 계산 로직은 아래와 같다. 다트 게임은 총 3번의 기회로 구성된다. 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다. 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수1 , 점수2 , 점수3 )으로 계산된다. 옵션으로 스타상(*) , 아차상(#..

문제 설명 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 공백(" ) 또는벽(#") 두 종류로 이루어져 있다. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 지도 1과 지도 2라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다. 지도 1과 지도 2는 각각 정수 배열로 암호화되어 있다. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을..