C++ 학습/C++ 코딩인터뷰[5장]20 [5. 배열] 5.14 임의의 순열 계산하기 [해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌시간복잡도와 공간복잡도의 관계를 계산하며,자료구조의 이해도와 실력을 향상하는데 목적이 있다.Q 5.14 임의의 순열 계산하기로 이루어진 임의의 순열을 동일한 확률로 만들어 내는 알고리즘을 작성하라.숫자를 같은 확률로 반환하는 임의의 숫자 생성기가 주어졌다고 가정해도 되며, 이 생성기를 가능하면 적게 호출하도록 하자.문제 5.12 오프라인 데이터 샘플 구하기에서 사용한 방법을 이용하려고 한다.https://msugi.tistory.com/26 [5. 배열] 5.12 오프라인 데이터 샘플 구하기[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]책.. 2025. 1. 15. [5. 배열] 5.13 온라인 데이터 샘플 구하기 [해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌시간복잡도와 공간복잡도의 관계를 계산하며,자료구조의 이해도와 실력을 향상하는데 목적이 있다.Q 5.13 온라인 데이터 샘플 구하기실시간으로 패킷이 유입되는 상황에서 어떤 정수값 k가 주어졌을 때, k개의 임의의 패킷을 균일한 확률로 유지하는 알고리즘을 설계하라.균일한 확률을 유지해야 하므로 다음과 같은 방법을 사용한다.0. 배열의 이름은 A , k는 패킷의 크기라고하자.1. 배열A를 라고 가정 하자.2. k=2라고하면 앞에서부터 2개인 를 가지고 시작하자.3. 다음 패킷을 읽어 r을 부분집합의 포함시킬 확률을 구하면 2/3이다.4. 포함시키게.. 2025. 1. 15. [5. 배열] 5.12 오프라인 데이터 샘플 구하기 [해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌시간복잡도와 공간복잡도의 관계를 계산하며,자료구조의 이해도와 실력을 향상하는데 목적이 있다.Q 5.12 오프라인 데이터 샘플 구하기서로 다른 원소로 이루어진 배열과 부분 집합의 크기가 주어졌을 때, 주어진 크기의 부분 집합을 반환하는 알고리즘을 작성하라. 단, 모든 부분 집합이 생성될 확률은 같아야 한다. 입력 배열을 통해 부분 집합의 결과를 반환하시오.같은 생성 확률의 부분 집합을 만들기 위해서는 다음과 같은 과정을 진행할 예정이다.0. 배열의 이름은 A , k는 부분집합의 크기, n은 임의로 생성된 숫자 라고하자.1. 숫자 생성기를 통하여 (.. 2025. 1. 15. [5. 배열] 5.11 다음 순열 구하기 [해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌시간복잡도와 공간복잡도의 관계를 계산하며,자료구조의 이해도와 실력을 향상하는데 목적이 있다. Q 5.11 다음 순열 구하기n개의 원소로 만들 수 있는 순열의 갯수는 n!개이다. 순열을 사전 순으로 정렬할때 다음으로 올 순열을 구하라.ex) P=의 다음 순열은 순열이 사전 순으로 정렬되어 있으므로, 순열의 크기를 조금만 증가시키는 것이 핵심이다.배열 A = 이라고 할때 A의 접미사 중에서 가장 긴 감소 순열은 이다.해당 순열은 사전 순으로 감소일때 다음순열이 존재하지않는다.따라서 5의 앞의 1과 감소순열 안에서 가장 작으며, 앞의 1보다 큰수와.. 2025. 1. 15. [5. 배열] 5.10 배열 안의 원소로 순열 구하기 [해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌시간복잡도와 공간복잡도의 관계를 계산하며,자료구조의 이해도와 실력을 향상하는데 목적이 있다. Q 5.10 배열 안의 원소로 순열 구하기배열에 주어진 숫자대로 순열을 재배치 하는 프로그램을 작성하라.ex) 배열 P = 안의 순열을 배열 A = 에 적용하면 가 된다.0,1,2,3 순서대로 배치되어야함 그래서 b,c,a,d이다.추가 공간을 사용할 수 있다면 간단하게 문제를 풀 수 있다.주어진 배열A와 길이가 같은 새로운 배열B를 사용하여 위치 i에 대하여 B[P[i]] = A[i] 로 할당한 뒤B의 결과를 A로 복사하면 시간 복잡도 O(n), 공간 복.. 2025. 1. 15. [5. 배열] 5.9 n보다 작은 모든 소수 나열하기 [해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌시간복잡도와 공간복잡도의 관계를 계산하며,자료구조의 이해도와 실력을 향상하는데 목적이 있다.Q 5.9 n보다 작은 모든 소수 나열하기양의 정수 n이 주어졌을 때, 1과 n 사이에 있는 모든 소수를 반환하는 프로그램을 작성해라.ex) 18이 입력되면 이 반환되어야 한다.간단한 방법은 2부터 n까지의 숫자를 모두 순회하는 것이다. 예를 들어 n=10 일때 bool배열을 로 초기화 하자 (0과 1은 소수가 아니므로 F)이제 n=2부터 T로 리스트에 추가하고 2의 배수를 F로 변경, n=3을 추가하고 3의배수를 변경... 을 반복한다.시간복잡도는 n개.. 2025. 1. 14. 이전 1 2 3 4 다음
