백사니

문제 설명해당 문제는 부대원들이 여러 지역에 흩어져 있을 때, 각 부대원이 본부로 복귀하는데 걸리는 최단시간을 계산하는 문제다.복귀가 불가능하면 -1을 반환해야 한다. 핵심 방법destination을 시작점으로 잡고 BFS를 돌려서, 각 지역까지의 최단 거리를 미리 계산한다.복귀하려는 지역(sources)마다 거리 정보를 꺼내서 결과에 담는다. BFS에 대한 자세한 내용은 아래 블로그에서 확인할 수 있다. BFS(Breadth-First-Search) 넓이 우선 탐색BFS는 넓이 우선 탐색으로 이름에서 알 수 있게 넓게 탐색하는 알고리즘이다.쉽게 말하면 가장 가까운 부분부터 탐색하며 점차 넓혀가는 알고리즘이다. BFS는 가장 가까운 부분부터 탐색하기에jinho082008.tistory.com #inclu..

문제 설명해당 문제는 정수 배열 array에 포함된 모든 숫자에서 숫자 7이 등장하는 횟수를 세는 문제다. 핵심 방법각 숫자를 1의 자리부터 확인하며 7이 나올 때마다 카운트를 증가시킨다.이를 위해 % 10과 /= 10 연산을 이용해 숫자를 자리수 단위로 분해한다. 한 줄 설명배열의 모든 수를 순회하면서, 각 수의 모든 자리에서 7이 몇 번 나오는지 세어 총합을 구한다.#include #include using namespace std;int solution(vector array) { int answer = 0; // 7의 개수를 저장할 변수 for(int i : array) // 배열의 각 숫자에 대해 반복 { while(i > 0) // 숫자가 0이 될 때까지 반복..

문제 설명해당 문제는 자연수 order에 포함된 3, 6, 9의 개수를 세어 해당 숫자만큼 박수를 치는 369 게임의 규칙을 구현하는 문제다. 핵심 방법order를 한 자리씩 나누어 3, 6, 9 중 하나가 포함될 때마다 카운트를 증가시킨다.이를 위해 나머지 연산 % 10과 나눗셈 연산 /= 10을 반복한다. 한 줄 설명숫자를 1의 자리부터 확인하면서 3, 6, 9가 나올 때마다 박수 횟수를 1씩 더한다.#include #include using namespace std;int solution(int order) { int answer = 0; // 박수 횟수를 저장할 변수 while(order > 0) // order가 0이 될 때까지 반복 { // 일의 자리가 3, 6..

문제 설명해당 문제는 문자열 my_string에서 자연수만 추출하여 그 합을 구하는 문제다.문자와 숫자가 섞여있으며, 연속된 숫자는 하나의 숫자로 간주한다. 핵심 방법알파벳 문자를 모두 공백으로 치환하여, stringstream을 사용해 공백 기준으로 분리된 문자열을 숫자로 변환하고 모두 더한다. 한 줄 설명문자열에서 숫자 이외의 문자를 공백으로 바꾸고, 공백 기준으로 숫자를 분리해 모두 더하는 방식이다.#include #include #include // isalpha 함수 사용을 위한 헤더#include // stringstream 사용을 위한 헤더using namespace std;int solution(string my_string) { int answer = 0; ..

문제 설명해당 문제는 연속된 num개의 정수를 더해서 total을 만들 수 있는오름차순 수열을 구하는 문제이다. 핵심 방법수열의 중앙값 기준으로 시작값을 계산한다.총합 total은 등차수열의 합 공식에 따라total= (first+last)×num​ / 2​따라서 수열의 중앙값은 total / num 이고,중앙값에서 num / 2를 뺀 값부터 시작하면 연속된 수를 만들 수 있다.vector solution(int num, int total) { vector answer; // 중심값 계산: 수열의 평균값 (중앙값) int center = ceil((double)total / num); // 시작 숫자 = 중앙값 - (num / 2) // 예: num = 3, center = ..

문제 설명해당 문제는 주어진 수열 common이 등차수열 또는 등비수열일 때,그 다음에 올 숫자를 예측하는 문제이다.즉, 등차인지 등비인지 판별한 후, 다음 항을 계산해 반환하면 된다. 핵심 방법앞의 세 수를 비교하여 등차수열인지 등비수열인지 판별한다.등차수열이면: a[n+1] = a[n] + d등비수열이면: a[n+1] = a[n] * r를 이용해 마지막 원소의 다음 수를 계산한다.

문제 설명해당 문제는 balls개의 서로 다른 구슬 중 share개를 고르는 조합의 수를 구하는 문제이다.즉, 조합 공식으로 계산하여 반환해야 한다. 핵심 방법분자 n! 와 분모 r!(n−r)! 를 따로 계산하지 않고,n×(n−1)×…×(n−r+1) / r! 형태로 순차적으로 계산하여 오버플로우를 방지하고 속도를 높인다. int solution(int balls, int share) { long long result = 1; // 결과를 저장할 변수, 오버플로우 방지를 위해 long long 사용 // 조합 수 계산: C(n, r) = n! / ((n-r)! * r!) for (int i = 1; i

문제 설명해당 문제는 2차원 배열에서 지뢰(값이 1인 칸)와 인접한 8방향(상하좌우 + 대각선) 모두를 위험지역으로 간주하고,그 외의 안전한 지역의 칸 수를 구하는 문제이다. 핵심 방법2차원 배열을 순회하면서 지뢰(1) 위치를 찾는다.해당 위치를 기준으로 8방향 인접한 칸까지 모두 위험지역으로 마킹한다.마지막에 0으로 남아있는 칸이 안전한 지역이다. 한 줄 요약지뢰가 있거나 인접한 칸을 전부 위험지역으로 처리하고, 남은 0의 개수를 구한다.#include using namespace std;int solution(vector> board) { int n = board.size(); vector> danger(n, vector(n, false)); // 8방향 벡터 (상하좌우 + 대각선) ..

문제 설명해당 문제는 정수 배열에서 가장 많이 등장한 값인 최빈값을 찾아 반환하는 문제이다.단, 최빈값이 여러 개라면 -1을 반환해야 한다. 핵심 방법map을 사용해 각 숫자의 등장 횟수를 세고,최대 등장 횟수를 기준으로 가장 많이 등장한 값이 여러 개인지 여부를 판단한다.여러 개면 -1하나면 해당 값을 반환map에 대한 자세한 내용은 아래 블로그에서 확인할 수 있다. std::map, std::unordered_mapstd::mapmap은 정렬된 컨테이너로 key 값을 기준으로 자동 정렬된다.(정렬은 오름차순)또한 중복키를 허용하지 않기 때문에 동일한 key 값은 존재할 수 없다.이진 탐색 트리를 기반으로 구현이 되었jinho082008.tistory.com #include #include #incl..

문제 설명해당 문제는 1번 노드에서 시작했을 때 최단 경로로 가장 멀리 떨어진 노드들의 개수를 구하는 문제다.BFS(너비 우선 탐색)을 사용하여 1번 노드부터 시작해 각 노드까지의 거리를 구한다.그 중 가장 멀리 떨어진 거리를 가지는 노드들의 개수를 세면 된다. 핵심 방법인접 리스트를 구성해 그래프 표현(index 1의 요소들은 1과 연결된 모든 노드)BFS를 통해 각 노드까지의 최단 거리 계산최댓값 거리를 구하고, 그 거리를 가진 노드 개수 반환#include #include #include #include #include #include using namespace std;// BFS를 통해 1번 노드에서 가장 멀리 있는 노드들의 개수를 구하는 함수int bfs(vector>& v){ queue..