소프트웨어 작업실

[BOJ 2745] 진법 변환 - [수학, 구현, 문자열]문제 링크https://www.acmicpc.net/problem/2745문제 요약$B$진법 수 $N$을 입력받아 10진법으로 변환하여 출력한다. 알파벳 대문자는 10부터 35까지의 숫자를 나타낸다.접근 방법자료구조: std::string (입력받는 $N$의 각 자릿수를 확인하기 위함)알고리즘: 다항식 계산 (Horner's Method 응용)핵심 아이디어:문자열의 앞에서부터 읽으며 현재까지의 결과에 진법 $B$를 곱하고, 새로운 자릿수 값을 더해준다.문자가 '0'~'9'인 경우와 'A'~'Z'인 경우를 분기 처리하여 정수형 값으로 변환한다.풀이 코드#include #include using namespace std;int main() { /..

[BOJ 24313] 알고리즘 수업 - 점근적 표기 1 - [수학 / 구현]문제 링크https://www.acmicpc.net/problem/24313문제 요약함수 $f(n) = a_1n + a_0$와 양의 정수 $c, n_0$가 주어질 때, 모든 $n \ge n_0$에 대하여 $f(n) \le c \cdot g(n)$ (단, $g(n) = n$)을 만족하는지 판별하는 문제.접근 방법자료구조: 단순 변수 (int)알고리즘: 수학적 조건 판별핵심 아이디어:빅오 표기법의 정의를 만족하려면 두 가지 조건을 동시에 충족해야 합니다.시작점 조건: $n = n_0$일 때, $f(n_0) \le c \cdot n_0$가 성립해야 합니다.기울기 조건: $n$이 $n_0$보다 커질 때 $f(n)$이 $c \cdot n$..

[BOJ 24267] 알고리즘 수업 - 알고리즘의 수행 시간 6 - [수학, 구현]문제 링크https://www.acmicpc.net/problem/24267문제 요약주어진 MenOfPassion 알고리즘(3중 for문)의 수행 횟수와 수행 시간을 다항식으로 나타냈을 때의 최고차항 차수를 출력하는 문제.입력 크기 $n$ ($1 \le n \le 500,000$)접근 방법자료구조: 정수형 변수 (long long)알고리즘: 수학 (조합론, Combination)핵심 아이디어:코드의 3중 반복문 조건($1 \le i 서로 다른 3개의 수를 뽑는 경우의 수와 동일함을 알 수 있습니다.즉, 수행 횟수는 ${}_nC_3 = \frac{n(n-1)(n-2)}{6}$ 입니다.다항식 $\frac{n(n-1)(n-2)}..

[BOJ 24266] 알고리즘 수업 - 알고리즘의 수행 시간 5 - [수학/구현]문제 링크https://www.acmicpc.net/problem/24266문제 요약주어진 3중 중첩 반복문 알고리즘(MenOfPassion)의 실행 횟수와 해당 수행 시간을 다항식으로 나타냈을 때의 최고차항 차수를 출력하는 문제입니다.접근 방법자료구조: 없음 (기본 변수 사용)알고리즘: 수학적 분석 (시간 복잡도 계산)핵심 아이디어: 1. 의사코드에서 $i, j, k$가 각각 $1$부터 $n$까지 순차적으로 반복되므로 전체 수행 횟수는 $n \times n \times n = n^3$입니다. 2. 입력값 $n$이 최대 500,000이므로, $n^3$은 최대 $1.25 \times 10^{17}$이 되어 int 범위를 초과합..

[BOJ 24265] 알고리즘 수업 - 알고리즘의 수행 시간 4 - [수학, 구현]문제 링크https://www.acmicpc.net/problem/24265문제 요약주어진 MenOfPassion 알고리즘(이중 for문 구조)의 수행 횟수와 시간 복잡도의 차수(최고차항)를 출력하는 문제.입력 크기 $n$ ($1 \le n \le 500,000$)에 대해 코드의 핵심 루프가 실행되는 총횟수를 구해야 함.접근 방법자료구조: 정수형 변수 (long long)알고리즘: 수학 (등차수열의 합)핵심 아이디어:외부 루프 i는 $1$부터 $n-1$까지 반복하고, 내부 루프 j는 $i+1$부터 $n$까지 반복합니다.i에 따른 수행 횟수는 다음과 같습니다:$i=1$: $n-1$회$i=2$: $n-2$회...$i=n-1$:..