백사니

문제 설명해당 문제는 진열대에 나열된 보석들 중 모든 종류의 보석을 하나 이상 포함하는 가장 짧은 구간을 찾는 문제이다.예를 들어 보석 종류가 4개라면 이 4가지 종류를 모두 포함하는 가장 짧은 구간의 시작과 끝 인덱스를 반환해야 한다. 핵심 방법슬라이딩 윈도우 + 해시맵(map) 을 사용하여 현재 구간 내 보석의 종류를 세고,모든 종류가 포함되었을 때 왼쪽 포인터를 줄이며 최소 구간을 갱신하는 방식이다. 슬라이딩 윈도우(Sliding Window) 기법은 배열이나 리스트에서 일정한 구간(윈도우)을 유지하며 왼쪽, 오른쪽 포인터를 이동시키는 방식으로 문제를 푸는 알고리즘 기법이다. Two Pointer 기법과 비슷하며 두 포인터의 구간을 검색하고 진행 방향이 같다는 것이 핵심이다. Two Pointer ..

문제 설명해당 문제는 선분 3개가 주어졌을 때, 서로 두 개 이상 겹치는 구간의 전체 길이를 구하는 문제이다.겹치는 구간은 정확히 두 개 또는 세 개의 선분이 공통으로 지나가는 부분만을 의미하며,겹치는 구간이 여러 구간에 걸쳐 있을 경우, 그 총 길이를 반환해야 한다. 핵심 방법좌표의 범위가 -100 ~ 100이므로 이를 0 ~ 200으로 shift시켜 1차원 배열에 표시한다.각 선분이 지나가는 구간을 배열에 누적하고값이 2 이상인 위치만 길이로 계산한다.#include #include using namespace std;int solution(vector> lines) { int arr[201] = {0}; // -100 ~ 100 범위를 0 ~ 200으로 매핑하기 위한 배열 // 각 선분의..

문제 설명해당 문제는 네 개의 점을 두 개씩 연결해 직선을 만들었을 때, 서로 평행한 직선 쌍이 존재하는지를 판단하는 문제이다. 핵심 방법네 점 중 두 점을 선택해 직선을 만들고, 나머지 두 점으로 또 하나의 직선을 만든다.두 직선의 기울기를 비교해 기울기가 같으면 평행한 것으로 간주한다.기울기를 정수형으로 비교하기 위해 분수의 곱셈 형태로 비교한다.나눗셈을 사용하지 않는 이유는, 부동소수점(floating point) 연산의 특성상 정확한 값이 아닌 근사값으로 표현되기 때문입니다.예를 들어,1 ÷ 3 = 0.333... 처럼 무한 소수는 컴퓨터 내부에서 정확히 표현할 수 없고,0.33333334처럼 근사값으로 저장된다.따라서 0.33333334 == 0.33333334처럼 보이지만,실제로는 미세한 오차..

문제 설명해당 문제는 "aya", "ye", "woo", "ma" 네 가지 단어를 조합해 만들어진 문자열인지 판별하고, 조카가 발음 가능한 단어의 개수를 구하는 문제이다. 핵심 방법문자열에서 "aya", "ye", "woo", "ma" 중 하나로 시작하는지를 확인하고 제거한다.모든 단어가 제거되어 문자열이 비어있다면 발음 가능한 단어로 인정한다. find에 대한 자세한 내용은 아래 블로그에서 확인할 수 있다. Find의 자료구조 별 시간 복잡도find 함수는 컨테이너에서 특정 데이터를 찾아주는 함수로 해당 데이터의 iterator를 반환한다.find 함수는 컨테이너의 종류와 데이터 구조에 따라 시간 복잡도가 결정된다.Vector와 Dequevector와 deque에jinho082008.tistory.co..

해당 문제는 k를 num에서 찾은 후 위치를 반환하는 문제이다. 일반적으로는 자리수대로 체크하는 방법이 존재하지만 find 함수를 사용해 더욱 간단히 풀어보았다. find에 대한 자세한 내용은 아래 블로그에서 확인할 수 있다. Find의 자료구조 별 시간 복잡도find 함수는 컨테이너에서 특정 데이터를 찾아주는 함수로 해당 데이터의 iterator를 반환한다.find 함수는 컨테이너의 종류와 데이터 구조에 따라 시간 복잡도가 결정된다.Vector와 Dequevector와 deque에jinho082008.tistory.comint solution(int num, int k) { string s = to_string(num); // 정수를 문자열로 변환 size_t pos = s..

해당 문제 해당 문제는 구매한 금액에 따라 정해진 비율로 할인을 적용한 뒤 최종 지불 금액을 계산하는 문제이다. 핵심 방법 핵심 방법은 주어진 가격 범위에 따라 할인율을 분기 처리하고, 정수 계산으로 소수점을 버리며 할인된 가격을 계산하는 것이다.#include #include // 표준 네임스페이스 사용using namespace std;// 가격을 받아서 할인 적용 후 지불 금액을 반환하는 함수int solution(int price) { // 10만 원 이상 30만 원 미만일 경우 5% 할인 if(price >= 100000 && price = 300000 && price = 500000) return price * 80 / 100; // 20% 할인 == 가격의 80% ..

해당 문제는 n명이 slice개로 나누어진 피자를 먹을 때 모두가 1조각씩은 먹기 위해서는 몇개의 피자가 필요한지 구하는 문제이다. cmath 라이브러리의 함수인 ceil함수는 소수점 존재 시 올림해주기 때문에 이를 이용하면 간단하게 풀 수 있다. cmath에 다양한 수학 함수에 대한 내용은 아래 링크에 정리해두었다. 코딩테스트에 자주 사용하는 수학함수 모음 (cmath 라이브러리)abs(x)절댓값을 반환하는 함수로 int(int), float(fabs), long(labs), double 등 데이터 타입에 따라 함수명이 다르다.#include #include int main() { std::cout 내부적으로는 단순히 부호 비트만 제거하거나 음수일 경jinho082008.tistory.com #incl..

문제 설명해당 문제는 불량 사용자 목록(banned_id)에 와일드카드(*)가 포함되어 있으며, 이 와일드카드에 매칭되는 사용자 ID(user_id)를 조합하여 가능한 제재 아이디 목록의 경우의 수를 구하는 문제다. 핵심 방법banned_id의 각 패턴에 대해 user_id에서 매칭 가능한 인덱스를 미리 구해둔다.BFS를 활용해 각 banned_id에 user_id를 하나씩 매핑하면서 중복되지 않도록 제재 아이디 조합을 만든다.각 조합은 set 형태로 저장하고, set>으로 중복 조합을 제거해 경우의 수를 센다. BFS에 대한 자세한 내용은 아래 블로그에서 확인할 수 있다. BFS(Breadth-First-Search) 넓이 우선 탐색BFS는 넓이 우선 탐색으로 이름에서 알 수 있게 넓게 탐색하는 알고..

문제 설명해당 문제는 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..