분류 전체보기

    9184번: 신나는 함수 실행

    9184번: 신나는 함수 실행사용 언어: C++ 문제 요약재귀 호출만 생각하면 신이 난다!다음과 같은 재귀함수 w(a, b, c)가 정의되어 있다:if a 20 or b > 20 or c > 20: return w(20, 20, 20)if a 입력:여러 줄에 걸쳐 정수 a b c가 주어진다.모두 -1일 경우 입력 종료.출력:각 입력에 대해 w(a, b, c) = 결과값 형식으로 출력한다.문제의 함정재귀함수 구현 자체는 쉽지만,w(15, 15, 15) 같은 값은 수백만 번 호출되는 중복 재귀가 발생한다.그대로 구현하면 시간 초과 혹은 시간 폭탄.풀이메모이제이션 (Memoization)한 번 계산한 결과는 배열에 저장해두고다음에 같은 입력이 오면 즉시 반환한다.dp[a][b][c] 배열을 사용해서 캐..

    14889번: 스타트와 링크

    14889번: 스타트와 링크사용 언어: C++ 문제 요약총 N명의 사람이 있고, 이들을 두 팀(스타트 팀, 링크 팀)으로 나눈다. 각 팀에 속한 사람들의 능력치 합 차이를 최소화하는 것이 목표.능력치는 2차원 배열 S[i][j]로 주어지며,i번과 j번이 같은 팀일 때 더해지는 값은 S[i][j] + S[j][i].N은 항상 짝수이며, 두 팀은 N/2명씩 구성돼야 함.풀이1. 조합을 통해 팀을 나눈다N명 중 N/2명을 선택해서 스타트 팀을 구성하면,나머지 인원은 자동으로 링크 팀이 된다.→ 즉, 전체 경우의 수는 NC(N/2) 개의 조합.2. 각 조합에 대해 능력치 차이 계산스타트 팀의 능력치 = sum(S[i][j] + S[j][i]) (for i, j in 스타트 팀)링크 팀도 동일하게 계산두 팀의 차..

    14888번: 연산자 끼워넣기

    14888번: 연산자 끼워넣기사용 언어: C++ 문제 요약N개의 수와 N-1개의 연산자가 주어짐.수의 순서를 바꾸지 않고, 주어진 연산자를 모두 사용해 수식을 완성.연산 순서는 앞에서부터(왼쪽에서 오른쪽으로) 진행.가능한 모든 수식 결과 중 최댓값과 최솟값을 출력해야 함.풀이가능한 연산자 순열을 모두 탐색해야 하므로 백트래킹(DFS) 을 사용.각 재귀 단계마다 남아 있는 연산자 중 하나를 선택해 현재까지의 계산 결과를 갱신.나눗셈은 음수 처리를 주의해야 함 (C++ 기준: -(-a / b) 방식으로 처리).#include #include #include using namespace std;int N;vector A;int op[4]; // +, -, *, /int max_val = -1e9;int min..

    2580번: 스도쿠

    2580번: 스도쿠사용 언어: C++ 풀이문제 요약9×9 스도쿠 판에서, 일부 칸이 비어 있고(0으로 표시됨), 규칙에 맞게 모든 칸을 채워야 함.각 행에 1~9가 한번씩각 열에 1~9가 한번씩각 3×3 구역에 1~9가 한번씩풀이백트래킹 기법을 이용하여 모든 빈 칸에 대해 가능한 수를 대입하고,불가능한 경우 이전 상태로 돌아가서 다른 수를 시도.핵심 아이디어빈 칸을 순서대로 탐색하며 가능한 숫자를 시도숫자를 채울 때마다, 행/열/구역 사용 여부를 표시가능한 경우 다음 칸으로 재귀 호출실패하면 상태를 되돌리고 다음 숫자 시도 (백트래킹)구현 포인트각 행/열/3×3 구역에 대해 숫자 사용 여부를 확인하기 위해bool row[9][10], col[9][10], square[9][10] 배열을 사용한다.(i /..

    병합 정렬 (Merge Sort)

    병합 정렬이란?병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 전략을 사용하는 대표적인 정렬 알고리즘이다.배열을 작게 쪼개서 정렬한 뒤, 다시 합치면서 전체를 정렬해나가는 방식이다.핵심 개념 요약Divide (분할)배열을 반으로 나눈다.더 이상 나눌 수 없을 때까지 계속 쪼갠다 (즉, 길이가 1이 될 때까지).Conquer (정복)쪼개진 배열을 병합하며 정렬한다.두 개의 정렬된 배열을 하나의 정렬된 배열로 합친다병합 정렬 흐름예를 들어 배열이 아래와 같다고 해보자:[21, 10, 12, 20, 25, 13, 15, 22] 그림처럼 병합 정렬은 이 배열을 계속 반으로 쪼개고, 마지막에는 정렬된 조각들을 차례로 병합한다:가장 아래에선 [21], [10] 같이 한 원소짜리..

    24060번: 알고리즘 수업 - 병합 정렬 1

    24060번: 알고리즘 수업 - 병합 정렬 1사용 언어: C++ 풀이Merge Sort (병합 정렬) 문제.기본 병합 정렬 구현 문제. 핵심은 정렬이 완료된 배열이 아니라, 정렬 중 원소가 배열 A에 저장되는 순간을 추적해서,K번째로 저장되는 값을 출력하는 것.병합 과정에서 A[i] = tmp[t]가 실행될 때마다 저장 횟수(cnt)를 세고,cnt == K가 되면 해당 값을 result에 저장한다.만약 저장 횟수가 K보다 작으면 -1 출력.#include using namespace std;int A[500001], tmp[500001];int N, K, cnt = 0, result = -1;void merge(int p, int q, int r) { int i = p, j = q + 1, t = ..

    11505번: 구간 곱 구하기

    11505번: 구간 곱 구하기사용 언어: C++ 풀이구간 합 구하기 문제와 유사. 구간의 곱을 구하는 것이므로 트리는 똑같이 만든다. 한 가지 다른 점은, 트리를 만들때 % MOD를 한다는 것인데, 어차피 마지막에 한번 Mod를 하나 중간 계속 Mod를 하나 결과는 같다. 그래서 Overflow가 안나게 매번 % MOD를 해준다는 것. Query에서도 곱을 하면서 % MOD를 해준다.#include using namespace std;typedef long long ll;const int MOD = 1'000'000'007;constexpr int SZ = 1 > N >> M >> K; for (int i = 0; i > num; Set(i, num); } for (int i..

    2042번: 구간 합 구하기

    2042번: 구간 합 구하기사용 언어: C++ 풀이리프 노드들은 입력 값들, 부모 노드들은 값들의 합으로 설정해서 O(log n)으로 구간의 합을 구하는 세그먼트 트리 문제다. 주의할 점은 a == 1일때 c가 int 범위를 넘어서 오버플로우가 발생할 수 있어서 long long을 설정해야한다.#include using namespace std;typedef long long ll;// SZ는 N보다 크거나 같은 2^k 꼴의 수 (2^20 == 1,048,576 > 1,000,000)constexpr int SZ = 1 > N >> M >> K; for (int i = 0; i > num; Set(i, num); // 세그먼트 트리 초기화 } for (int i = 0; i..