목록전체 글 (65)
아무거나 내꺼 공부할래
▣ 문제 오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램 을 작성하세요. ▣ 입력설명 - 첫번째 줄에 첫 번째 배열의 크기 N(1
▣ 문제 1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 Inversion Sequence라 한다. 예를 들어 다음과 같은 수열의 경우 4 8 6 2 5 1 3 7 1앞에 놓인 1보다 큰 수는 4, 8, 6, 2, 5. 이렇게 5개이고, 2앞에 놓인 2보다 큰 수는 4, 8, 6. 이렇게 3개, 3앞에 놓인 3보다 큰 수는 4, 8, 6, 5 이렇게 4개...... 따라서 4 8 6 2 5 1 3 7의 inversion sequence는 5 3 4 0 2 1 1 0 이 된다. n과 1부터 n까지의 수를 사용하여 이루어진 수열의 inversion sequence가 주어졌을 때, 원래 의 수열을 출력하..
LRU(Least Recently Used, 카카오 캐시 문제 변형, 삽입정렬 응용) / c / 제한시간 없음
▣ 문제 - 캐시메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업 을 저장해 놓았다가 필요할 바로 사용해서 처리속도를 높이는 장치이다. 워낙 비싸고 용량이 작아 효율적으로 사용해야 한다. 철수의 컴퓨터는 캐시메모리 사용 규칙이 LRU 알고리즘을 따 른다. LRU 알고리즘은 Least Recently Used 의 약자로 직역하자면 가장 최근에 사용되지 않 은 것 정도의 의미를 가지고 있습니다. 캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘입니다. 만약 캐시의 사이즈가 5이고 작업이 2 3 1 6 7 순으로 저장되어 있다면, (맨 앞이 가장 최근에 쓰인 작업이고, 맨 뒤는 가장 오랫동안 쓰이지 않은 작업이다.) 2 3 1 6 7 1..
▣ 문제 N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요. 정렬하는 방법은 삽입정렬입니다. ▣ 입력설명 - 첫 번째 줄에 자연수 N(1 temp) num[j + 1] = num[j]; else break; } num[j + 1] = temp; } for (i = 0; i < n; i++) { printf("%d ", num[i]); } return 0; } 삽입 정렬이 선택, 버블, 삽입 정렬중에서 가장 문제에서 출제 빈도가 높다. 삽입 정렬은 i번째의 수를 temp에 저장시키고 뒤에서 앞으로 숫자를 비교해가면서 정렬하는 방법이다. 삽입 정렬의 경우 평균적인 시간 복잡도는 O(N^2)이지만 최적의 경우에는 O(N)이다.
▣ 문제 N개의 정수가 입력되면 당신은 입력된 값을 정렬해야 한다. 음의 정수는 앞쪽에 양의정수는 뒷쪽에 있어야 한다. 또한 양의정수와 음의정수의 순서에는 변함이 없어야 한다. ▣ 입력설명 - 첫 번째 줄에 정수 N(5 0 && num[j + 1] < 0) { temp = num[j]; num[j] = num[j + 1]; num[j + 1] = temp; } } } for (i = 0; i < n; i++) printf("%d ", num[i]); return 0; } 버블 정렬의 개념을 이용해서 num[j]가 양수 num[j+1]이 음수일때마다 두 수의 위치를 바꿔주는 방식으로 구현했다. . 내가 직접 한 코드는 배열중에서 음수가 있으면 해당 지점에서 계속해서 앞으로 옮기는 방식으로 구현했다. 기본적..
▣ 문제 N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요. 정렬하는 방법은 버블정렬입니다. ▣ 입력설명 - 첫 번째 줄에 자연수 N(1
▣ 문제 N명의 수학성적이 주어지면 그 중 3등을 한 수학성적을 출력하는 프로그램을 작성하세요. 만약 학생의 점수가 100점이 3명, 99점이 2명, 98점이 5명, 97점이 3명 이런식으로 점수가 분포되면 1등은 3명이며, 2등은 2명이며 3등은 5명이 되어 98점이 3등을 한 점수가 됩니다. ▣ 입력설명 - 첫 번째 줄에 자연수 N(1