백사니

해당 문제는 괄호로 이루어진 문장을 주어진 규칙에 맞게 다시 만드는 문제로 주어진 규칙을 차근차근 구현한다면 어려움 없이 풀 수 있다.문자열을 분리한 후 특정 조건에서 다시 같은 과정을 반복하므로 재귀함수로 나누어서 구현하였다.#include #include #include using namespace std;// 문자열의 괄호 방향을 뒤집는 함수string changeStr(string str){ str.erase(str.begin()); // 첫 번째 문자 제거 str.erase(str.end() - 1); // 마지막 문자 제거 // 문자열의 각 문자에 대해 괄호 방향 뒤집기 for(char& ch : str) { if(ch == '(') ..

해당 문제는 주어진 지도에서 연결된 무인도를 찾아 각 섬에서 머물 수 있는 최대 일수를 계산하고, 결과를 오름차순으로 정렬하여 반환하는 문제이다. BFS를 이용해 연결된 영역을 찾고 중복 방지를 위해 방문 처리를 해준다.연결된 부분의 값들을 계산해 총 머무를 수 있는 일수를 구한다. BFS에 대한 자세한 내용은 아래 블로그에서 확인할 수 있다. BFS(Breadth-First-Search) 넓이 우선 탐색BFS는 넓이 우선 탐색으로 이름에서 알 수 있게 넓게 탐색하는 알고리즘이다.쉽게 말하면 가장 가까운 부분부터 탐색하며 점차 넓혀가는 알고리즘이다. BFS는 가장 가까운 부분부터 탐색하기에jinho082008.tistory.com#include #include #include #include using ..

해당 문제는 다익스트라 알고리즘을 사용하여 특정 시작점에서 각 마을까지의 최단 거리를 구하고, 주어진 시간 제한 내에 배달 가능한 마을의 수를 세는 문제다.1번 마을에서 출발하여 각 마을까지의 최단 거리를 다익스트라 알고리즘을 사용하여 구한다.이후 각 마을까지의 최단 거리가 K 이하인 마을의 개수를 세어 반환한다.#include #include #include #include #include using namespace std;int solution(int N, vector> road, int K) { // 그래프 표현 { 연결된 마을 번호, 거리 } vector>> graph(N + 1); vector distance(N + 1, INT_MAX); // 최단 거리 테이블 (무한대로 초기화..

이 문제는 손님들이 주문한 메뉴 조합을 분석하여, 가장 인기 있는 코스 메뉴 조합을 찾아내는 문제다.orders의 각 주문에서 각 course 값에(메뉴 개수) 해당하는 메뉴 조합을 카운트한다.이후 course 값에 대해 가장 많이 주문된 조합을 찾아서 2번 이상 주문되고 최대 주문 횟수를 가진 조합을 결과에 추가한다.#include #include #include #include using namespace std;// 재귀 함수: 조합 생성void makeCourse(vector v, string course, int target, vector& result) { // 코스의 요리 갯수가 목표 갯수와 일치하면 if (course.size() == target) { //코스의..

해당 문제는 3진법과 유사하지만, 0 대신 4를 사용하는 특이한 진법 변환 문제이다.때문에 3진법을 구하고 0 대신 4를 사용하며 나머지가 0일 경우 자릿수 보정을 해주면 된다.#include #include #include #include using namespace std;string solution(int n) { string answer = ""; // 124 나라 숫자를 저장할 문자열 변수 초기화 // n이 0이 될 때까지 반복 while(n != 0) { //124는 3진법이니 3으로 나눠서 나머지를 구해 3진법 구현 int temp = n % 3; // 나머지가 0인 경우, 124 나라에서는 4로 표현 if(temp ..

해당 문제는 호텔 예약 정보를 바탕으로 최소한의 객실을 사용하여 모든 손님을 수용하는 방법을 찾는 문제이다. 구분하기 편하게 예약 시작 시간을 기준으로 정렬하고 객실 배정 순서를 결정한다. room은 퇴실시간 후 청소시간을 가지고 있으며, room의 갯수가 곧 필요한 객실 수를 의미한다. Sort에 대한 자세한 내용은 아래 블로그에서 확인할 수 있다. Sort(정렬)Sort 사용법C++에서 Sort는 배열이나 컨테이너를 정렬하는 데 사용된다.기본적으로 오름차순 정렬을 수행하며, 내림차순으로 정렬도 가능하다.또한 커스텀 함수를 넘겨주므로 정렬 기준을 사용자jinho082008.tistory.com#include #include #include #include using namesp..

해당 문제는 Wire 한개를 끊었을 때 연결되어 있는 두 개의 그룹의 송전탑 개수를 구하는 문제로 두개의 송전탑은 최대 한개의 Wire로 연결되어 있다는 점을 이용해서 문제를 풀었다.이러한 특징을 이용한다면 [3,4] 와이어를 끊는다면 나누어지는 두 그룹엔 3과 4가 각각 한개씩 밖에 존재하지 않게 된다. 이후 wire에 3이 있으면 1번 그룹, 4가 있으면 2번 그룹으로 구분해서 그룹 내 송전탑의 갯수를 구하면 된다.송전탑은 번호마다 한개씩 있기에 set을 이용해 중복되는 원소 없이 그룹에 저장한다.구현 방법#include #include #include #include #include using namespace std;int solution(int n, vector> wires) { //두 그룹의..

해당 문제는 시소의 균형을 이루는 두 사람의 몸무게 관계를 파악하는 문제로, 주어진 몸무게 목록에서 짝꿍이 될 수 있는 쌍의 개수를 구하는 문제이다.놀이공원에 있는 시소는 중심으로부터 2m, 3m, 4m 거리에 좌석이 있으며, 두 사람이 시소에 마주 보고 탈 때, 시소가 평형을 이루려면 각 사람이 시소에 가하는 토크의 크기가 같아야한다. 즉, 탑승한 사람의 몸무게와 시소 축과의 거리의 곱이 양쪽 모두 같아야 한다.#include #include #include using namespace std;long long solution(vector weights) { long long answer = 0; // 시소 짝꿍 쌍의 개수를 저장할 변수 초기화 sort(weights.begin(), ..

해당 문제는 storey(층 번호)를 0층으로 만들기 위해 엘리베이터 버튼을 최소 몇 번 눌러야 하는지를 구하는 문제다.엘리베이터 버튼을 누를 때 한 자리씩 조정할 수 있으며, 5 이상의 숫자는 올림, 4 이하의 숫자는 내림하는 방식으로 최소 횟수를 구한다. 또한 낮은 자리의 반올림이 높은 자리에 영향을 줄 수 있으므로 낮은 자리부터 높은 자리로 계산한다.예를 들어,storey = 16 → 6을 올림(4) →20 → 2을 내림(2) → 0 (총 6번)storey = 2554 → 4 내림(4) → 2550→ 5 올림(5) →2600 → 6 올림(4) → 3000 → 3을 내림(3) → 0(총 16번)#include #include using namespace std;int solution(int store..

해당 문제는 보기엔 매우 복잡해 보이지만 규칙이 존재한다. 해당 규칙만 찾으면 구현은 비교적 간단하다.해당 문제는 1부터 n까지 숫자들이 시계 반대 방향으로 돌아가며 배치되어있다. 또한 이는 크게 3가지의 특징을 가지고 배치되어있다.1부터 4까지 위에서 아래로 내려오며 index 간격이 점차 증가한다.4부터 7까지 왼쪽에서 오른쪽으로 진행되면 index는 1씩 증가한다.7부터 9까지 아래에서 위로 올라오며 index 간격이 점차 줄어든다.위 규칙을 그림으로 나타내면 다음과 같다.(index 번호를 표시한 그림이다.)구현 방법#include #include using namespace std;//n일 때 총 index 크기를 구해주는 함수int numSize(int n){ int result = 0;..