백사니

코딩테스트 : 소수 찾기

문제 설명해당 문제는 한자리 숫자가 적힌 종이 조각을 이어붙여 만들 수 있는 소수의 개수를 구하는 문제이다.숫자는 여러 개를 이어붙일 수 있으며, 같은 숫자는 각각 다른 종이 조각으로 취급한다. 핵심 방법숫자 조각을 이어붙여 만들 수 있는 모든 경우를 탐색해야 한다.이어붙여 만들어진 수가 소수인지 확인해야 한다.같은 수가 중복으로 세지 않도록 이미 사용한 수는 set에 기록한다.소수 판별은 에라토스테네스의 체(n까지 소수 구하기 최적화)를 이용해 미리 구해둔다. 에라토스테네스의 체에 대한 자세한 설명은 아래 링크에 정리해두었다. 에레스토테네스의 체에라토스테네스의 체란?에라토스테네스의 체는 고대 그리스 수학자인 에라토스테네스가 만든 소수(Prime Number) 를 빠르게 찾는 방법이다. 예를 들어 1부터..

코딩테스트 : 피로도

문제 설명해당 문제는 현재 피로도 k를 기준으로, 여러 던전 중에서 최대한 많이 탐험할 수 있는 던전의 수를 구하는 문제다. 핵심 방법모든 던전에 대해 방문 가능한 순열을 DFS로 탐색하면서, 현재 피로도로 탐험 가능한 경우만 재귀적으로 진행한다.방문 여부를 체크하는 visited 벡터를 활용해 중복 탐험을 방지하고, 최대 탐험 횟수를 계속 갱신한다. DFS에 대한 자세한 설명은 아래 링크에서 확인할 수 있다. DFS( Depth-First Search) 깊이 우선 탐색DFS는 깊이 우선 탐색으로 이름에서 알 수 있듯 깊이를 우선으로 탐색하는 알고리즘이다.쉽게 말해 가장 끝의 부분까지 탐색했다가 돌아오면서 나머지 경로도 마찬가지로 끝 부분까지 탐색하는jinho082008.tistory.com #incl..

문제 설명해당 문제는 부대원들이 여러 지역에 흩어져 있을 때, 각 부대원이 본부로 복귀하는데 걸리는 최단시간을 계산하는 문제다.복귀가 불가능하면 -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방향 벡터 (상하좌우 + 대각선) ..