백사니

문제 설명해당 문제는 5g 기지국의 전파 도달 거리로는 현재의 공백을 모두 커버할 수 없기 때문에 새로운 기지국을 최소한으로 설치해서 모든 아파트에 전파를 전달해야 하는 문제이다.기지국이 설치된 위치와 전파 거리 w를 기준으로 커버할 수 없는 구간을 찾아 그 구간을 커버할 수 있는 최소 기지국 개수를 계산해야 한다. 핵심 방법각 기지국은 stations[i] - w부터 stations[i] + w까지를 커버한다.커버되지 않는 구간의 길이를 gap이라고 할 때, 하나의 기지국이 커버할 수 있는 범위는 2w + 1이므로필요한 기지국 수는 ceil(gap / (2w + 1))이 된다. ceil 함수는 cmath 헤더에 포함된 수학 함수로,실수 값을 입력받아 그 값보다 크거나 같은 최소 정수를 반환한다.즉, 소..

문제 설명 해당 문제는 모든 차량의 경로가 주어졌을 때, 차량마다 적어도 한 번은 단속 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 구하는 문제이다. 카메라는 구간의 정수 지점에 설치할 수 있으며, 차량의 진입지점과 진출지점에 설치된 카메라도 만난 것으로 간주한다. 핵심 방법 차량의 진출 지점을 기준으로 정렬한 뒤, 카메라를 해당 차량의 진출 지점에 설치한다. 해당 지점보다 진입 지점이 앞선 차량들은 이 카메라로 커버할 수 있다. 이 과정을 반복하며 최소의 카메라 개수를 구한다.#include #include #include using namespace std;int solution(vector> routes) { // 차량의 진출 시점을 기준으로 정렬 sort(rout..

문제 설명해당 문제는 A팀의 출전 순서가 고정된 상태에서, B팀이 출전 순서를 전략적으로 조절해 최대 승점을 얻는 문제이다. 핵심 방법 A팀을 내림차순 정렬, B팀을 오름차순 정렬한다. B팀은 자신보다 가장 작은 A팀원을 이기거나, 이길 수 없다면 가장 센 A팀원에게 져주는 전략을 취한다. 양쪽 포인터(frontPoint, backPoint)를 이용해 A팀의 가장 약한 선수와 가장 강한 선수를 판단하고, 이에 따라 B팀 선수를 배치한다. TwoPointer 기법에 대한 설명은 아래 링크에 정리해두었다. Two Pointer 기법1차원 배열에서 각자 다른 원소를 가리키는 2개의 포인터를 사용하여 목표값을 구하기 위한 기법완전탐색 O(n^2)보다 효율적인 O(n)으로 동작정렬된 배열에서 효율적으로 동작한다...

문제 설명해당 문제는 장르별로 가장 많이 재생된 노래를 2개씩 골라 베스트 앨범을 만드는 문제이다. 구현 조건장르별 총 재생 수를 기준으로 가장 인기 있는 장르부터 수록한다.각 장르 내에서는 가장 많이 재생된 노래부터 최대 2곡을 선택한다.재생 수가 같다면 고유 번호(인덱스)가 작은 노래를 우선한다. 문제 풀이 핵심 장르별 재생 수 총합을 저장한다. 장르별 노래 목록과 인덱스를 저장한다. 장르를 재생 수 총합 기준으로 정렬한다. 각 장르마다 노래 리스트를 재생 수 기준으로 정렬한 뒤, 최대 2개를 고른다.#include #include #include #include using namespace std;vector solution(vector genres, vector plays) { vector..

문제 설명해당 문제는 n크기의 집합에 합이 S이면서 각 원소의 곱이 최대인 집합을 반환하는 문제이다. 이 문제는 n이 최대 10000까지이기 때문에 꽤 크다. 때문에 BFS나 DFS 같이 탐색하면서 수를 찾는다면 시간초과 문제가 생길것이다. 그렇다면 어떻게 푸는게 좋을까? 핵심 방법이 문제에는 규칙이 존재한다.원소의 곱이 최대가 되려면 각 원소가 최대한 같은 값을 가지고 있을 때 최대가 된다.예) n = 3, s = 9 : [3, 3, 3] = 27, [1, 4, 4] = 16, [2, 3, 4] = 24 #include #include #include using namespace std;vector solution(int n, int s) { // n개의 자연수로 s를 만들 수 없다면 -1 반환 ..

문제 설명해당 문제는 정수 배열 numbers에서 서로 다른 인덱스에 있는 두 수를 골라 더할 수 있는 모든 경우의 수를 구하고, 그 결과를 오름차순 정렬된 배열로 반환하는 문제이다. 핵심 방법중복 제거를 위해 set을 사용하면 코드가 간결해지고, 자동 정렬도 된다.i와 j 쌍을 중복되지 않게 고르기 위해 j = i+1부터 시작하는 것이 중요하다. set에 대한 자세한 설명은 아래 링크에 정리해두었다. 중복을 방지해주는 자료구조 Setset은 중복을 허용하지 않는 자료구조이다. 즉 set에 중복된 값을 넣을 시 한 번만 저장된다. set은 2가지 종류가 있는데 set과 unordered_set이다. unordered_set은 unordered_map과 마찬가지로 jinho082008.tistory.com..

문제 설명해당 문제는 숫자로 이루어진 문자열에 숫자를 의미하는 영단어가 섞여 있는 경우, 이를 원래 숫자 형태로 변환하는 문제이다.문자열에는 zero부터 nine까지의 영단어가 포함될 수 있으며, 이 단어들을 실제 숫자로 바꿔 하나의 정수로 반환해야 한다.예를 들어 "one4seveneight"은 "1" + "4" + "7" + "8"로 해석되어 1478이 된다. 핵심 방법자 0부터 9까지에 해당하는 영단어를 미리 매핑해놓는다.입력 문자열에서 해당 영단어가 존재할 경우 find 함수로 위치를 찾고, 해당 부분을 대응하는 숫자로 replace 한다.모든 영단어를 숫자로 치환한 후, stoi() 함수를 이용해 문자열을 정수로 변환해 반환한다. map에 대한 자세한 설명은 아래 링크에 정리해두었다. std::..

문제 설명 해당 문제는 문자열 배열에서 각 문자열의 n번째 문자를 기준으로 정렬하는 문제이다.만약 n번째 문자가 같다면, 전체 문자열 기준으로 사전 순 정렬을 진행한다. 핵심 방법정렬 기준이 단순히 n번째 문자이므로, std::sort에 비교 함수를 전달하여 커스텀 정렬을 구현한다.a[n] == b[n]인 경우 a 문자열이 모두 n보다 길다는 조건이 있기 때문에 a[n] 접근은 안전하다. sort에 대한 자세한 설명은 아래 링크에 정리해두었다. Sort(정렬)Sort 사용법C++에서 Sort는 배열이나 컨테이너를 정렬하는 데 사용된다.기본적으로 오름차순 정렬을 수행하며, 내림차순으로 정렬도 가능하다.또한 커스텀 함수를 넘겨주므로 정렬 기준을 사용자jinho082008.tistory.com #include..

문제 설명해당 문제는 두 개의 정수 배열을 이진수로 해석해 겹쳐진 비밀지도를 해독하는 문제이다.지도는 정사각형 형태이며, 두 지도의 각 줄을 OR 연산한 결과를 통해 벽(#) 또는 공백( )을 판단한다. 이때 OR 연산의 결과가 1인 경우 벽으로, 0인 경우 공백으로 처리한다. 핵심 아이디어비트 연산 OR을 활용해 벽이 하나라도 존재하면 벽으로 표시이진수로 변환 후, 1이면 '#', 0이면 ' '으로 변환자릿수 맞추기: 항상 n자리로 표현되도록 한다. #include #include using namespace std;vector solution(int n, vector arr1, vector arr2) { vector answer; // 최종 결과를 담을 문자열 벡터 for(int i..

문제 설명해당 문제는 각 사진에 등장하는 인물들의 이름이 주어지고, 인물마다 '그리움 점수'가 부여되어 있을 때,사진별로 등장 인물의 그리움 점수를 모두 더한 '추억 점수'를 계산하는 문제이다. 핵심 방법이름과 그리움 점수를 빠르게 조회하기 위해 unordered_map을 사용한다.각 사진을 순회하며 사진 속 인물이 점수표에 있는 인물이라면 그 점수를 더한다.사진별 계산된 점수를 결과 벡터에 차례대로 넣는다. map에 대한 자세한 설명은 아래 링크에 정리해두었다. std::map, std::unordered_mapstd::mapmap은 정렬된 컨테이너로 key 값을 기준으로 자동 정렬된다.(정렬은 오름차순)또한 중복키를 허용하지 않기 때문에 동일한 key 값은 존재할 수 없다.이진 탐색 트리를 기반으로 ..