'🍧 코딩테스트' 카테고리의 글 목록

2024.05.08· 🍧 코딩테스트

🍧 문제왕자가 N명이 있는데, 서로 공주를 구하러 가겠다고 한다. 다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 한다. 왕은 왕자들을 나이 순으로 1~N번까지 차례로 번호를 매긴다. 그리고 1번 왕자부터 N번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다. 그리고 1번 왕자부터 시계방향으로 돌아가면 1부터 시작하여 번호를 외치게 한다. 한 왕자가 특정 숫자 K를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고, 원 밖으로 나오게 된다. 그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외친다. 이렇게 해서 마지막까지 남은 왕자가 공주를 구하러 갈 수 있다.예를 들어 8명의 왕자가 있을 때, 3을 외친 왕자가 제외된다고 하자. 처음에 3번 왕자가 3을 외쳐 제외되며, 이어 ..

[인프런 C++] 44. 마구간 정하기 (이진탐색 응용)

2024.05.08· 🍧 코딩테스트

🍧 문제N개의 마구간이 1차원 수직선상에 있습니다. 각 마구간은 X1, X2, X3 ... XN의 좌표를 가지며, 마구간간에 좌표가 중복되는 는 일은 없습니다.현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다. C마리의 말을 N개의 마구간에 배치했을 때, 가장 가까운 두 말의 거리가 최대가 되는 그 최댓값을 출력하는 프로그램을 작성하세요. ✨ 1트 (강의 풀이)마굿간의 위치를 정렬해준다. 1 2 4 8 9답의 범위 : 최솟값 ~ 최댓값 사이 👉 1 ~ 9두 말의 거리가 최대가 되야 하기 때문에, 1 위치부터 넣어본다. 1. mid = (1+9..

[인프런 C++] 43. 뮤직비디오(이진탐색 응용)

2024.05.07· 🍧 코딩테스트

🍧 문제DVD에는 총 N개의 곡이 들어간다. DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다.M개의 DVD에 모든 동영상을 녹화하기로 하였다. 이때 DVD의 크기를 최소로 하려한다. 그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다. ✨ 1트 (성공)오랜만에 성공.. /(ㄒoㄒ)/~~#include #include #include using namespace std;int main(void){ freopen("input.txt", "rt", stdin); int n, m, cnt = 0, total = 0; c..

[인프런 C++] 42. 이분검색(이진 탐색)

2024.05.07· 🍧 코딩테스트

🍧 문제임의의 N개의 숫자가 입력으로 주어집니다.N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. ✨ 1트 (성공)#include #include #include using namespace std;int main(void){ freopen("input.txt", "rt", stdin); int n, m; cin >> n >> m; vector a(n); for(int i = 0; i > a[i]; } sort(a.begin(), a.end()); int left = 0; int right = n-1; int mid; while(left m){ right = mid - 1; ..

[인프런 C++] 41. 연속된 자연수의 합

2024.05.07· 🍧 코딩테스트

🍧 문제입력으로 양의 정수 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법의 가짓수를 출력하는 프로그램을 작성하세요. 만약 N=15이면7+8 = 154+5+6 = 151+2+3+4+5 = 15와 같이 총 3가지 경우가 존재한다. ✨ 1트 (실패)앞에서부터 더해본다 👉 같은 경우 출력하고, 커지면 가장 큰 수를 빼서 확인해보기1~5, 4~6 처럼 겹치는 경우에 대해서 대비가 안됨 ✨ 2트 (강의 풀이)정말 엄청난 풀이인 것..주어진 n -1 -2 를 해준다. 👉 그 수에 % 2(뺀 수의 갯수), / 2를 해준다 👉 1+6, 2+6 = 7 + 8 = 15가 된다.나머지가 0값이면 더해서 만들어진다는 뜻#include #include #include using namespac..

[인프런 C++] 40. 교집합(투포인터 알고리즘)

2024.05.02· 🍧 코딩테스트

🍧 문제두 집합 A, B가 주어지면 두 집합의 교집합을 출력하는 프로그램을 작성하세요. 🍧 입력첫 번째 줄에 집합 A의 크기 N이 주어진다.두 번째 줄에 N개의 원소가 주어진다. 원소가 중복되지 않는다.세 번째 줄에 집합 B의 크기 M이 주어진다.네 번째 줄에 M개의 원소가 주어진다. 원소가 중복되지 않는다.각 집합의 원소는 int형 변수의 크기를 넘지 않는다. 🍧 출력두 집합의 교집합을 오름차순으로 정렬하여 출력한다. 🍧 1트 (강의 풀이)이중 for문 사용 지양a와 b배열을 정렬하고 비교해주어야 한다. 비교해서 다르면 👉 작은 숫자가 있는 배열의 위치를 이동비교해서 같으면 👉 두 배열의 위치를 모두 증가시킨다 & c배열에 넣어준다.한 배열이 끝나면 while문 끝 & c배열 출력#inclu..

[인프런 C++] 39. 두 배열 합치기

2024.05.02· 🍧 코딩테스트

🍧 문제오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하세요. 🍧 입력첫 번째 줄에는 첫 번째 배열의 크기 N이 주어진다.두 번째 줄에 N개의 배열 원소가 오름차순으로 주어진다.세 번째 줄에는 두 번째 배열의 크기 M이 주어진다.네 번째 줄에 M개의 배열 원소가 오름차순으로 주어진다.각 배열의 원소는 int형 변수의 크기를 넘지 않는다. 🍧 출력오름차순으로 정렬된 배열을 출력한다. 🍧 1트 (강의 풀이)a 배열과 b 배열을 두고, 각 배열의 값들을 비교하여 c 배열에 삽입한다.한쪽이 끝나면 중지하고, 나머지를 c 배열에 넣어서 구현한다.#include #include #include using namespace std;int a[101], b[10..

[인프런 C++] 38. Inversion Sequence

2024.05.02· 🍧 코딩테스트

🍧 문제1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 Inversion Sequence라 한다. 예) 4 8 6 2 5 1 3 71앞에 놓인 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가 주어졌을 때, 원래의 수열을 출력하는 프로그램을 작성하세요. 🍧 입력85 3 4 0 2 1 1 0 🍧 출력4 8 ..

[인프런 C++] 37. Least Recently Used (카카오 캐시 문제 변형)

2024.05.02· 🍧 코딩테스트

🍧 문제LRU 알고리즘 : Least Recently Used. 가장 최근에 사용되지 않은 것. 캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘. 만약 캐시의 사이즈가 5이고, 작업이 2 3 1 6 7 순으로 저장되어 있다면(맨 앞이 가장 최근에 쓰인 작업이고, 맨 뒤는 가장 오랫동안 쓰이지 않은 작업) 1. cache miss : 해야할 작업이 캐시에 없는 상태. 위상태에서 만약 새로운 작업인 5번 작업을 cpu가 사용한다면 cache miss가 되고, 모든 작업이 뒤로 밀리고 5번 작업은 캐시의 맨 앞에 위치한다. 5 2 3 1 6 (7번 작업은 캐시에서 삭제된다) 2. cache hit : 해야할 작업이 캐시에 있는 상태로 위 상태에서 만약 3번 작업을 cpu가 ..

[인프런 C++] 36. 삽입정렬

2024.05.02· 🍧 코딩테스트

🍧 문제N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.정렬하는 방법은 삽입정렬입니다. 🍧 입력첫 번째 줄에 자연수 N이 주어집니다.두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다. 🍧 출력오름차순으로 정렬된 수열을 출력합니다. 🍧 1트 (강의 풀이)#include #include #includeusing namespace std;int main(void){ freopen("input.txt", "rt", stdin); int n, temp, j; int a[101]; cin >> n; for(int i = 0; i > a[i]; } for(int i = 1; i = 0; --j){ if(a[j] > temp..

[인프런 C++] 35. Special Sort(구글 인터뷰)

2024.05.02· 🍧 코딩테스트

🍧 문제N개의 정수가 입력되면 당신은 입력된 값을 정렬해야 한다.음의 정수는 앞쪽에, 양의 정수는 뒷쪽에 있어야 합니다. 또한 양의 정수와 음의 정수의 순서에는 변함이 없어야 한다. 🍧 입력첫 번째 줄에 정수 N이 주어지고, 그 다음 줄부터 음수를 포함한 정수가 주어진다. 숫자 0은 입력되지 않는다. 🍧 출력정렬된 결과를 출력한다.🍧 1트 (강의 풀이)버블 정렬 활용양수와 음수가 만나면 위치를 변경해준다. 양수가 앞에 있는 경우#include #include #includeusing namespace std;int main(void){ freopen("input.txt", "rt", stdin); int n, temp; int a[101]; cin >> n; for(int i = 0; i > ..

[인프런 C++] 34. 버블정렬

2024.05.02· 🍧 코딩테스트

🍧 문제N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.정렬하는 방법은 버블정렬입니다. 🍧 입력첫 번째 줄에 자연수 N이 주어집니다.두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다. 🍧 출력오름차순으로 정렬된 수열을 출력합니다. 🍧 1트 (강의 풀이)#include #include #includeusing namespace std;int main(void){ freopen("input.txt", "rt", stdin); int n, temp; cin >> n; int a[n]; for(int i = 0; i > a[i]; } for(int i = 0; i a[j+1]){ temp = a[j]; a[..

티스토리툴바