N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 "좋다(GOOD)"고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다. 풀이 JavaScript const fs = require('fs'); const input = fs.readFileSync('input.txt').toString().trim().split('\n'); const N = parseInt(input[0]); const A = input[1].split(' ').map(Number); let Result = 0; for (let k = 0; k < N; k++) { let find = A[k]; let i = 0; let j = N ..
어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다. 예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다. N을 입력받아 가지수를 출력하는 프로그램을 작성하시오. 풀이 JavaScript const n = parseInt(require('fs').readFileSync("input.txt").toString().trim(), 10); let count = 1; // 가장 마지막 수만 뽑는..
배열에서 중복된 값을 제거하기 위해서는 일반적으로 우선 배열을 정렬한다. 오름차순 정렬을 하면 중복된 값들이 인접한 위치에 모여 중복을 쉽게 찾을 수 있기 때문이다. 예를 들어, 정렬되지 않은 배열에서 중복을 찾으려면 배열의 모든 요소를 하나씩 비교해야 한다. 하지만 정렬된 배열에서는 중복된 값들이 연속해서 나타나기 때문에 중복을 찾는 과정이 간단해진다. 결국은 시간 복잡도를 줄이기 위함이다. 정렬된 배열에서 중복을 찾는 것은 인접한 값들만을 비교하면 되기 때문에 추가적인 반복문이나 자료구조를 사용할 필요가 없어진다. 반면, 정렬되지 않은 배열에서 중복을 찾으려면 모든 요소를 비교해야 하므로 시간 복잡도가 크게 증가할 수 있다. 예를 들어, 주어진 배열이 [4, 2, 1, 2, 4, 3, 1]이라고 가정..
시간 복잡도를 표현하는 빅오 표기법을 실제 파이썬 코드 예시와 함께 살펴보도록 하겠다. 시간 복잡도는 알고리즘의 성능과 효율성을 나타내는 지표로 사용된다. 코딩 테스트에서는 주어진 문제의 제약과 시간 복잡도에 맞는 알고리즘을 선택하여 효율적인 코드를 작성하는 것이 중요하다. 따라서 빅오 표기법을 고려하면 다양한 알고리즘의 성능을 분석하고 개선해 볼 수 있다. 시간 복잡도 예시 설명 O(1) 리스트 인덱싱 인덱스를 통해 리스트의 요소에 접근하는 작업은 일정한 시간이 소요됨 O(logn) 이진 탐색 정렬된 리스트에서 특정 값을 찾는 작업은 탐색 범위를 반으로 나누며, 탐색 속도가 로그에 비례 O(n) 선형 탐색 리스트의 모든 요소를 한 번씩 확인하는 작업은 입력 크기에 비례하여 진행됨 O(nlogn) 병합 ..
다음 문제들을 빅 오 표기법으로 나타내보자. 1. 주어진 해가 윤년인지 밝히는 다음 함수의 시간 복잡도를 빅 오 표기법으로 나타내자. function isLeapYear(year) { return (year % 100 === 0) ? (year % 400 === 0) : (year % 4 === 0); } 해답 O(1) 함수에 전달된 년도를 N이라고 하면, 년도가 몇이든 알고리즘에 걸리는 단계 수는 일정하다. 2. 주어진 배열의 모든 수를 합하는 다음 함수의 시간 복잡도를 빅 오 표기법으로 나타내자. function arraySum(array) { let sum = 0; for(let i = 0; i < array.length; i++) { sum += array[i]; } return sum; } 해답..
문제 N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길 이가 5인 최대 부분 증가수열을 만들 수 있다. 입력 예제 5 3 7 8 6 2 9 4 출력 예제 4 풀이 function solution(arr){ let answer = 0; let dy = Array.from({length: arr.length}, () => 0); // 앞에 다른 수가 없으니 자기 자신 1로 초기화 dy[0] = 1; for (let i = 1; i < arr.length; ..
문제 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. n개의 계단을 오르는 방법은 몇 가지인가? 입력 예제 7 출력 예제 21 풀이 function solution(n){ let answer=0; let dy = Array.from({length: n+1}, () => 0); dy[1] = 1; // 첫 번째 계단 가지수 dy[2] = 2; // 두 번째 계단 가지수 // 3 이상 계단 가지수 = 이전 두 계단 가지수를 더한 값 for (let i = 3; i
[알고리즘-JS] 이진 트리 순회 - 깊이 우선 탐색 (DFS)
- 전위 순회 (부모-왼쪽-오른쪽) : 1 2 4 5 3 6 7 - 중위 순회 (왼쪽-부모-오른쪽) : 4 2 5 1 6 3 7 - 후위 순회 (왼쪽-오른쪽-부모) : 4 5 2 6 7 3 1 전위 순회, 중위 순회, 후위 순회 출력 재귀 함수를 사용하여 이진 트리 순회를 출력한다. function solution(v) { let answer = 0; function DFS(v) { if (v > 7) return; else { console.log(v); // 전위순회: 1 2 4 5 3 6 7 DFS(v*2); console.log(v); // 중위순회: 4 2 5 1 6 3 7 DFS(v*2+1); console.log(v); // 후위순회: 4 5 2 6 7 3 1 } } DFS(v); retur..
문제 10진수 N을 2진수로 변환하여 출력하시오. 입력 예제 13 출력 예제 1101 풀이 재귀 함수를 사용해서 해결한다. function solution(n) { let answer = ""; // 재귀 함수 function DFS(n) { if (n === 0) return; else { DFS(parseInt(n/2)); answer += String(n%2); // 재귀 함수 뒤에서 더해야 스택에 쌓였던 것들이 // 위에서부터 실행되니까 역순으로 출력 가능 } } DFS(n); return answer; }
문제 N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마 구간간에 좌표가 중복되는 일은 없습니다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다. C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대 값을 출력하는 프로그램을 작성하세요. 입력 예제 5 3 1 2 8 4 9 출력 예제 3 풀이 // mid를 거리로 정하면 몇 마리의 말이 들어갈 수 있는가 function count (stable, dist) { let cnt = 1, ep=sta..