문제 지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다. DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지 되어야 한다. 순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다. 지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다. 고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기 로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 그리고..
문제 임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분 검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복 값은 존재하지 않습니다. 입력 예제 8 32 23 87 65 12 57 32 99 81 출력 예제 3 풀이 반 씩 나눠가면서 탐색한다. function solution(target, arr) { let answer = 0; let lt = 0; let rt = arr.length - 1; arr.sort((a, b) => a - b); while(lt target) rt = mid-1; // target이 mid를 기준으로 오른쪽에 있을 때 lt를 mid 바로 뒤로 옮기기 else lt..
문제 현수는 다음 달에 결혼을 합니다. 현수는 결혼식 피로연을 장소를 빌려 3일간 쉬지 않고 하려고 합니다. 피로연에 참석하는 친구들 N명의 참석하는 시간정보를 현수는 친구들에게 미리 요구했습니다. 각 친구들은 자신이 몇 시에 도착해서 몇 시에 떠날 것인지 현수에게 알려주었습니다. 현수는 이 정보를 바탕으로 피로연 장소에 동시에 존재하는 최대 인원수를 구하여 그 인원을 수용할 수 있는 장소를 빌리려고 합니다. 여러분이 현수를 도와주세요. 만약 한 친구가 오는 시간 13, 가는시간 15라면 이 친구는 13시 정각에 피로연 장에 존재하는 것이고 15시 정각에는 존재하지 않는다고 가정합니다. 입력 예제 14 18 12 15 15 20 20 24 5 14 출력 예제 2 풀이 각각의 start 시간과 end 시간..
문제 한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들 려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하 면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중 단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 입력 예제 3 3 1 3 2 3 출력 예제 2 풀이 function solution(arr) { let answer = 0; // 끝나는 시간 오름차순 정렬 arr.sort((a, b) => { // 끝나는 시간이 같으면 시작 시간으로 정렬 if (a[1] === b[1]) return a[0] - b[0] else return a[1] - b[1]..
문제 N개의 x, y 좌표가 주어지면 오름차순으로 정렬하시오. x값이 같다면 y에 의해 정렬합니다. 입력 예제 1 4 2 8 2 3 3 5 출력 예제 1 4 2 4 2 8 3 5 풀이 sort() 메서드를 사용하여 간단하게 해결할 수 있다. function solution(arr) { let answer = arr; arr.sort((a, b) => { if(a[0] === b[0]) return a[1] - b[1]; // y좌표로 오름차순 정렬 else return a[0] - b[0]; }) return answer; }
문제 캐시 메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업을 저장해 놓았다가 필요할 바로 사용해서 처리속도를 높이는 장치이다. 워낙 비싸고 용량이 적어 효율적으로 사용해야 한다. 철수의 컴퓨터는 캐시 메모리 사용 규칙이 LRU 알고리즘을 따른다. LRU 알고리즘은 Least Recently Used 의 약자로 직역하자면 가장 최근에 사용되지 않은 것 정도의 의미를 가지고 있습니다. 캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘입니다. 만약 캐시의 사이즈가 5이고 작업이 2 3 1 6 7 순으로 저장되어 있다면, (맨 앞이 가장 최근에 쓰인 작업이고, 맨 뒤는 가장 오랫동안 쓰이지 않은 작업이다.) 1) Cache Miss : ..
문제 삽입 정렬로 오름차순 정렬을 구현하시오. 입력 예제 13 6 5 2 11 19 출력 예제 2 5 6 11 13 19 풀이 function solution(arr) { let answer = arr; // 얕은 복사 for (let i = 0; i= 0; j--) { if (arr[j] > tmp) arr[j+1] = arr[j]; else break; } arr[j + 1] = tmp; } return answer; }
문제 N개의 정수가 입력되면 당신은 입력된 값을 정렬해야 한다. 음의 정수는 앞쪽에 양의 정수는 뒤쪽에 있어야 한다. 또한 양의정수와 음의 정수의 순서에는 변함이 없어야 한다. 입력 예제 8 1 2 3 -3 -2 5 6 -6 출력 예제 -3 -2 -6 1 2 3 5 6 풀이 일반 오름차순 정렬로 하면 음수, 양수 각각의 순서도 정렬되기 때문에 버블 정렬로 해결해야 한다. function solution(arr) { let answer = arr; // 얕은 복사 // 버블 정렬 for (let i = 0; i < arr.length-1; i++) { // 맨 뒤 요소는 계속 확정이므로 확인 X for (let j = 0; j < arr.length-1-i; j++) { // j가 양수고, j 뒤 요소가 ..
배열을 오름차순으로 정렬할 수 있는 방법은 여러 가지가 있다. sort() 메서드를 사용하는 방법부터, 다양한 정렬 알고리즘까지 정리해보자. 목차 sort() 선택 정렬 버블 정렬 1. sort() function solution(arr) { let answer = arr; arr.sort((a, b) => a - b); return answer; } 2. 선택 정렬 선택 정렬은 한 요소를 나머지 요소와 하나씩 비교하며 자리를 교체하는 알고리즘이다. 이중 for 문을 사용한다. function solution(arr) { let answer = arr; for (let i = 0; i < arr.length; i++) { let idx = i; for (let j=i+1; j < arr.length; j..
문제 정보 왕국의 이웃 나라 외동딸 공주가 숲속의 괴물에게 잡혀갔습니다. 정보 왕국에는 왕자가 N명이 있는데 서로 공주를 구하러 가겠다고 합니다. 정보왕국의 왕은 다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 했습니다. 왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매긴다. 그리고 1번 왕자부터 N 번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다. 그리고 1번 왕자부터 시 계방향으로 돌아가며 1부터 시작하여 번호를 외치게 한다. 한 왕자가 K(특정숫자)를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 된다. 그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외친다. 이렇게 해서 마지막까지 남은 왕자가 공주를 구하러 갈 수 있다. 예를 들어 총 ..