게으름뱅이의 앞구르기

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

자연수 N이 주어지면, N의 각 자릿수의 합을 구해서 return 하는 solution 함수를 만들어 주세요. 예를들어 N = 123이면 1 + 2 + 3 = 6을 return 하면 됩니다. 코딩테스트 연습 - 자릿수 더하기 자연수 N이 주어지면, N의 각 자릿수의 합을 구해서 return 하는 solution 함수를 만들어 주세요. 예를들어 N = 123이면 1 + 2 + 3 = 6을 return 하면 됩니다. 제한사항 N의 범위 : 100,000,000 이하의 자연수 입출 programmers.co.kr 풀이1 function solution(n){ return n.toString().split('').reduce((prev,curr)=> Number(prev) + Number(curr)) } 처음에..

정수 num이 짝수일 경우 Even을 반환하고 홀수인 경우 Odd를 반환하는 함수, solution을 완성해주세요. 코딩테스트 연습 - 짝수와 홀수 정수 num이 짝수일 경우 Even을 반환하고 홀수인 경우 Odd를 반환하는 함수, solution을 완성해주세요. 제한 조건 num은 int 범위의 정수입니다. 0은 짝수입니다. 입출력 예 num return 3 Odd 4 Even programmers.co.kr 풀이 function solution(num) { return num % 2 ? "Odd" : "Even"; } 솔직히 너무 간단한 문제라 하나 더 해야겠다... 양의 정수 x가 하샤드 수이려면 x의 자릿수의 합으로 x가 나누어져야 합니다. 예를 들어 18의 자릿수 합은 1+8=9이고, 18은 9..

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세..

라빈 카프 문자열 매칭(Rabin–Karp algorithm) ASCII 코드 기반의 해시 함수를 이용하여 특정한 문자열에 대한 해시 값을 구함 연속적인 문자열이 이어지는 상황이므로 해시 함수의 동작에 있어서 연산속도가 O(1) 라빈카프 문자열 매칭 알고리즘에서 해시함수는 각 문자의 ASCII 코드 값에 2의 제곱 수를 차례대로 곱하여 더한 값을 구함. 일반적으로 서로 다른 문자열의 경우 해시값이 다르게 나옴. 그러나 해시기반이기 때문에 충돌 처리 필요 다음 해시 값 = 2 * (현재 해시값 - 가장 앞에 있는 문자의 수치) + 새 문자의 수치 참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수

트리구조로 구간 합 구하기 세그먼트 트리는 구현하는 과정이 복잡하고 어려움 → 인덱스 트리는 구현이 매우 간단하며 O(logN)의 시간 복잡도를 가짐 인덱스 트리는 세그먼트 트리에 비해 메모리 효율성이 높음 특정 숫자의 마지막 비트를 구함(A & -A) 각 인덱스의 마지막 비트를 내가 저장하고 있는 값들의 개수로 계산 마지막 비트만큼 구간을 앞으로 이동하며 합을 구함 참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수

세그먼트 트리로 구간합* 구하기 선형적으로 구간합을 구하면 O(N)의 시간 복잡도를 가지므로 비효율적임 트리구조를 이용하여 구간합을 구하여 O(logN)의 시간복잡도로 구간합을 구함 *구간합 : 여러개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터 합을 구하는 것 완전 이진 트리에 데이터 삽입 구간 합 트리 생성(특정 범위 인덱스의 값을 저장함) 필요한 구간에 포함된 트리 노드의 값들로 구간합을 계산함 참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수

가중치가 있는 연결된 무방향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성 트리를 찾는 알고리즘 각 간선에 대한 정보를 우선순위 큐에 담아 처리하는 방식으로 구현 프림 알고리즘 작동 순서 그래프에서 정점하나를 선택하여 트리 T에 포함시킴 T에 포함된 노드와 T에 포함되지 않은 노드 사이의 간선 중에서 가장 가중가 작은 간선을 찾음 해당 간선에 연결된 T에 포함되지 않은 노드를 트리 T에 포함시킴 모든 노드가 포함될 때까지 반복 각 간선에 대한 정보를 우선 순위 큐에 담아 처리하는 방식으로 구현 참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수