본문 바로가기

코딩테스트

 (10)
JS 탐욕(Greedy) 알고리즘 심화 34 ✏️ 주유소 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net let fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().split('\n'); let c = Number(input[0]); /* cties */ let d = input[1].split(' ').map(Number); /* distance */ let p = input[2].split('..
JS 탐욕(Greedy) 알고리즘 기초 12 ✏️ 현재 상황에서 당장 가장 좋아보이는 상황만을 선택하는 알고리즘이다. ✏️ 동전0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net ✏️ ATM https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi..
JS 정렬 문제 ✏️ 수 정렬하기 2 https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net let fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().split('\n'); let cnt = Number(input[0]); let arr = []; for (let i=1; i
코딩테스트를 위한 정렬 ✏️ 선택정렬 가장 작은 것을 선택해서 앞으로 보내는 정렬이다. 작은 값을 찾는데 N, 정렬하는데 N-1번 수행해야하기 때문에 O(n^2)의 복잡도를 가진다. function selectionSort(arr) { // 작은 값 찾기 for (let i = 0; i arr[j]){ minIdx = j; } } // 작은 값을 정렬하기 위해 Swap let temp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = temp; } } ✏️ 버블정렬 서로 인접한 두 원소를 비교 후 필요시 위치를 변경하여 정렬한..
코딩테스트를 위한 자료구조 자료구조는 다수의 자료(data)를 담기 위한 구조이며, 데이터의 수가 많아질수록 효율적인 자료구조가 필요하다. ✏️ 자료구조의 종류 선형구조 (linear data structure) 배열 (Array) 연결 리스트(linked list) 스택 (stack) 큐 (queue) 비선형구조 (non-linear data structure) 트리 (tree) 그래프 (graph) ✏️ 복잡도 시간 복잡도 (time complexity) : 알고리즘에 사용되는 연산 횟수를 측정 공간 복잡도 (space complexity) : 알고리즘에 사용되는 메모리의 양을 측정 ✏️ 시간 측정 일반적으로 연산 횟수가 10억을 넘어가면 1초 이상의 시간이 소요되며, n이 1,000일 경우 O(n) : 약 1,000번 연산 ..
JS 문자열 문제 ✏️ 문자열 반복 https://www.acmicpc.net/problem/2675 반복함수 repeat(횟수)를 기억하자! 2675번: 문자열 반복 문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다 www.acmicpc.net let fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().split('\n'); let testCase = Number(input[0]); for(let i=1; i
JS 배열 문제 ✏️ 최소, 최대 https://www.acmicpc.net/problem/10818 최대, 최소값은 문제는 제시되는 제일 큰 수를 최소값에, 제시되는 제일 작은 수를 최대값에 초기화하고 시작하는게 좋다. 10818번: 최소, 최대 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. www.acmicpc.net let fs = require('fs'); let input = fs.readFileSync('/dev/stdin').toString().split('\n'); let n = Number(input[0]); let arr = ..
JS 반복문 문제 ✏️ 합 https://www.acmicpc.net/problem/8393 등차수열의 합 공식 : n * ( n + 1 ) / 2 8393번: 합 n이 주어졌을 때, 1부터 n까지 합을 구하는 프로그램을 작성하시오. www.acmicpc.net ✏️ 빠른 A+B https://www.acmicpc.net/problem/15552 15552번: 빠른 A+B 첫 줄에 테스트케이스의 개수 T가 주어진다. T는 최대 1,000,000이다. 다음 T줄에는 각각 두 정수 A와 B가 주어진다. A와 B는 1 이상, 1,000 이하이다. www.acmicpc.net

티스토리툴바