알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 정렬을 이용한 그리디 문제입니다. 최소 강의실을 구해야하는 문제입니다. 강의를 최대로 이어서 할 수 있도록 만들어야합니다. 따라서 한 강의를 시작으로 최대한 다른 강의로 이어봅니다. 다른 강의를 시작할 수 없는 때가 온다면 강의실을 하나 추가하고 해당 강의를 시작합니다. 이러한 과정을 반복하면 강의실의 갯수를 구할 수 있습니다. 이를 우선순위 큐를 통해서 풀면 됩니다. 자세한 것은 코드를 참고해주세요 #define _CRT_S..

문제 링크입니다. https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 정렬을 이용해 푸는 문제입니다. A의 배열은 오름차순으로, B의 배열은 내림차순으로 정렬해 서로 곱해주면 되는 문제입니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include using namespace std; int N;..

문제 링크입니다. https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 그리디 알고리즘을 이용해 정렬로 푸는 문제입니다. 최대로 많은 회의를 찾는 문제입니다. 찾는 방법은 A라는 회의가 끝났을 때, A 회의 끝나는 시간에 가장 빨리 시작하는 회의면서 가장 빨리 끝나는 회의여야합니다. 따라서 먼저 끝나는 시간을 기준으로 오름차순으로 정렬합니다. 이때 끝나는 시간이 같다면 -> 일찍 시작하는 것을 선택해야합니다. 따라서 시작 시간을 기준으로 오름차순 정렬합니다. 가장 먼저 시작하는 회의는 첫번째에 있는 회의입니다. 따라서 해당 회의의 끝나는 시간을 시작으로 다음 회의를..

문제 링크입니다. https://www.acmicpc.net/problem/18766 18766번: 카드 바꿔치기 범고래와 돌고래는 카드놀이를 좋아한다. 각 카드는 빨강 (R), 노랑 (Y), 파랑 (B) 중 하나의 색으로 칠해져 있고 0-9 사이의 숫자가 적혀있다. 색과 숫자가 같은 카드가 여러 장 있을 수도 있다. 최 www.acmicpc.net 정렬을 이용해 푸는 문제입니다. 돌고래가 카드를 바꿔치기 했는지의 여부를 판단하는 문제입니다. 2개의 문자열 배열이 주어지는데, 두 문자열 배열이 일치하다면 -> 바꿔치기 X 두 문자열 배열이 다르다면 -> 바꿔치기 0 따라서 두 문자열 배열을 같게 만들어줘야합니다. 각 문자열 배열을 정렬을 시킨뒤, 전부 비교해주면 됩니다. 자세한 것은 코드를 참고해주세요 ..

문제 링크입니다. https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 정렬을 사용한 문제입니다. 산술 평균값, 중앙값, 최빈값, 범위를 구하는 문제입니다. 중앙값, 범위의 경우에는 sort를 이용해 정렬을 한 뒤, 출력을 해주면 쉽게 할 수 있습니다. 산술 평균의 경우, 소수 첫번째 자리에서 반올림을 해야합니다. 따라서 캐스트 연산자를 사용해, 실수형 변수로 변환한 뒤, 출력해주면 됩니다. 최빈값의 경우는 조건이 있습니다. 1. 최빈 값이 여러개인 경우, 두번째..

문제 링크입니다. https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 삼성 SW 역량테스트 기출문제입니다. 정렬을 한 뒤의 MAP의 저장이 중요했습니다. 정렬을 하는 기준은 수의 등장횟수(오름차순)이며, 등장횟수가 같다면 수가 커지는 순서로 정렬을 하면 됩니다. 예를 들어, (3 , 3 , 2 , 1 , 2) 가 있다고 했을 때, (1 , 1 , 2 , 2 , 3 , 3)으로 정렬이 됩니다. 행의 갯수가 열의 갯수보다 많거나 같을 때에..

문제 링크입니다 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 입력된 단어를 정렬하는 문제입니다. cmp라는 함수를 사용해서 길이, 사전순으로 정렬을 하는 방식으로 풀었습니다. 정렬을 다한 후에는 출력 for문에서 같은 문자를 제외하고 출력했습니다. cmp함수에서 첫번째로 length를 이용해 길이를 비교합니다. 길이가 다르다면 올바른 return 값을 해주면 됩니다. 만약 길이가 같다면 단어를 사전 순으로 비교해서 올바른 retu..