분류 전체보기225 [Problem Solving] BOJ 2613: 숫자구슬 문제 링크: https://www.acmicpc.net/problem/2613 인접한 구슬끼리 묶어서 그룹을 만든다. 각 그룹에는 한 개 이상의 구슬이 있다. low: 구슬의 적힌 숫자 중 최댓값high: 구슬의 적힌 숫자들의 합으로 설정하고low mid는 (low + high) / 2이다.1. 각 그룹의 구슬에 적힌 숫자의 합이 mid가 넘지 않도록 그룹을 만들었을 때, 발생하는 그룹의 수가 M보다 작거나 같다. -> 최소의 mid를 구하기 위해 범위를 더 낮춰본다. -> opt = min(opt, min), high = mid - 12. 각 그룹의 구슬의 적힌 숫자의 합이 mid가 넘지 않도록 그룹을 만들었을 때, 발생하는 그룹의 수가 M보다 많다. -> mid가 너무 작아서 너무 많은 그룹이 생겼으.. 2025. 4. 12. [Problem Solving] BOJ 7490: 0 만들기 문제 링크: https://www.acmicpc.net/problem/7490 백트래킹 + 문자열 문제이다. 1부터 N까지의 수를 순서대로 늘어놓고 인접한 수를 붙이거나 더하거나 빼서 0이 되는 경우의 수를 출력하는 문제이다.백트래킹이기 때문에 모든 함수를 재귀 호출하여 모든 경우의 수를 따져본다.식을 s에 만들어서 재귀함수에 넘겨준다. 공백이 있으면 replace함수로 공백을 제거한다음에 eval(e)로 0이면 s를 출력한다. import syssys.setrecursionlimit(10 ** 6)read = sys.stdin.readlineN = 0def is_zero(s): e = s.replace(" ", "").rstrip() if eval(e) == 0: return T.. 2025. 4. 6. [Problem Solving] BOJ 11497: 통나무 건너뛰기 문제 링크: https://www.acmicpc.net/problem/11497 통나무를 나열했을 때, 인접한 통나무 간 높이 차의 최댓값의 최솟값을 구하는 문제이다.첫 번째 통나무와 마지막 통나무는 인접해 있기 때문에 오름차나 내림차로 정렬하면 인접한 통나무 간 높이 차의 최댓값이 매우 커진다. 인접한 통나무 간 높이 차의 최댓값이 최소가 되는 경우는 가장 큰 통나무를 중심으로 하여, 큰 것 부터 작은 것 까지 가장 큰 통나무를 가운데 중심으로 하여 왼쪽, 오른쪽 번갈아 가면서 높은 경우이다. 이것을 구현하기 위해 deque 자료구조를 사용한 후, 높이 차의 최댓값을 구한다. 그것이 답이된다.import java.io.BufferedReader;import java.io.IOException;impo.. 2025. 4. 5. [Computer Algorithms] Combination (조합) N개 들어있는 배열에서 i개 고르는 경우를 모두 출력하는 알고리즘이다. mask를 이용해서 true인 자리에 있는 것을 출력한다.#include #include #include using namespace std;int main(){ int N = 5; vector arr = {1, 2, 3, 4, 5}; for (int i = 1; i mask(arr.size(), false); fill(mask.begin(), mask.begin() + i, true); // 앞의 i개를 true로 설정 do { for (int j = 0; j 10000의 이전 조합: 0100001000의 이전 조합: 0010000100의 이전 조합: 00.. 2025. 3. 30. [Problem Solving] BOJ 17471: 게리멘더링 문제 링크: https://www.acmicpc.net/problem/17471 그래프에서 지역구를 두 개로 나눈다. 한 지역구에는 적어도 하나의 노드를 가져야 하고, 한 지역구의 노드들을 하나의 연결요소여야 한다. 일단 모든 노드를 방문하는 bfs를 수행하는 데, bfs 호출 횟수가 3번 이상이라면, 그래프가 3개 이상으로 쪼개져있어서 두 개의 지역구로 나누는 것이 불가능 하다. 이 때는 -1을 출력하고 프로그램을 종료한다. bfs 호출 횟수가 정확히 2번이라면, 쪼개진 두 개의 그래프의 노드의 인구의 합의 차이가 답이 된다. bfs 호출 횟수가 정확히 한 번이라면, 전체 노드를 두 쪽을 내는 모든 경우의 수를 따져야한다.노드 집합을 분리해서 하나는 v1에 다른 하나는 v2에 저장한다.v1의 노드들이 .. 2025. 3. 30. [Problem Solving] BOJ 15990: 1, 2, 3 더하기 5 문제 링크: https://www.acmicpc.net/problem/15990 n이라는 수가 1과 2와 3의 합으로 이루어 질 때, 더해지는 수가 연속적이지 않은 경우의 수를 구하는 문제이다. dp테이블을 다음과 같이 정의할 수 있다.dp[n][i]는 수의 합이 n일 때, 마지막으로 더해진 수가 i인 경우의 수이다.따라서dp[n][1] = dp[n - 1][2] + dp[n - 1][3] (1 + n - 1 = n)dp[n][2] = dp[n - 2][1] + dp[n - 2][3] (2 + n - 2 = n)dp[n][3] = dp[n - 3][1] + dp[n - 3][2] (3 + n - 3 = n)라고할 수 있다. 결과로 dp[n][1] + dp[n][2] + dp[n][3] 를 출력하면 된다... 2025. 3. 29. 이전 1 2 3 4 ··· 38 다음