Fall in IT.

Union-Find 특징 대표적인 그래프 알고리즘으로 합집합 찾기라고도 불린다. 여러개의 노드가 존재할때 두 개의 노드가 같은 그래프에 속하는지 판별하는 알고리즘 코드 /** * 대표적인 그래프 알고리즘 Union-Find (합집합 찾기) * * 여러개의 노드가 존재할때 두 개의 노드를 선택해서 같은 그래프에 속하는지 판별하는 알고리즘 */ function solution() { /** * 배열의 인덱스는 노드 번호를 뜻하고 * 배열의 인덱스의 값은 부모 노드를 의미한다. * * 최초 배열에는 자기 자신이 부모 노드로 존재한다. */ let arr = []; for (let i = 1; i

문제 설명 수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한, 한 번 수신된 신호는 다른 탑으로 송신되지 않습니다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고받습니다. 높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑이 수신하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신할 수 없습니다. 송신 탑..

힙 정렬(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는 각각 정수 배열로 암호화되어 있다. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을..

문제 설명 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다. 이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라. 실패율은 다음과 같이 정의한다. 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수 전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가..

안녕하세요. 오늘은 Visual Studio Code에서 html 파일을 수정 후, 바로 웹브라우저로 실행하는 방법을 알아보겠습니다. Visual Studio Code 에서 웹페이지 실행하는 방법 VS Code를 실행 좌측 하단의 마켓플레이스를 선택 "open in browser" 를 검색 후, 설치 .html 파일에서 ALT + B 단축키를 사용하여 웹페이지를 실행 모두 즐거운 코딩하세요 :)

소수 찾기 문제 설명 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상 1000000이하의 자연수입니다. 입출력 예 n result 10 4 5 3 입출력 예 설명 입출력 예 #1 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환 입출력 예 #2 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환 // 첫 번째 답안. 하지만, 효율성 테스트에서 Fail function solution(n) { let answer = 0; let startTime = new Date(); for (let i = 2; i