BOJ82 [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 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. [Problem Solving] BOJ 14426: 접두사 찾기 문제 링크: https://www.acmicpc.net/problem/14426 S를 정렬한다.S에서 각 T[i]에 대해 이진탐색 한다.java에서 이진탐색의 결과는 정확히 일치하는 값이 있으면 그 값이 존재하는 S에서의 index를 반환하고, 일치하지 값이 없으면 T[i]가 삽입될 자리를 -index-1로 반환한다. 이 때 index = -index-1로 바꿔주면 S[index]는 T[i]를 접두사로 갖는 문자열이다.index가 N보다 작고 S[index]가 T[i]로 시작하는 문자열인지 startsWith함수를 사용해 확인하여 이 결과가 참이라면 result를 1증가시킨다. import java.io.BufferedReader;import java.io.IOException;import java.io.. 2025. 3. 25. [Problem Solving] BOJ 1013: Contact 문제 링크: https://www.acmicpc.net/problem/1013 정규 표현식을 사용하여 주어진 문자열이 정규 표현식에 매칭되는지 확인하는 문제이다.pattern에 ^(100+1+|01)+$ 을 컴파일하는데,여기서 ^와 &는 주어진 문자열의 전체를 매칭한다는 뜻이다. ^는 문자열의 시작을 의미하고, $는 문자열의 끝을 의미한다.주어진 문자열 전체에 대해 (100+1+|01)+이라는 패턴이 존재하는 지 확인해야한다.패턴 (100+1+|01)+은(100+1+) 이라는 패턴이 한 번 이상 존재 하거나, (01) 이라는 패턴이 한 번 이상 존재하는 패턴이다(100+1+)은 10뒤에 0이 한 번 이상 나타나야 하고, 그 뒤에 1이 한 번 이상 나타나는 패턴이다. import sysimport rere.. 2025. 3. 23. [Problem Solving] BOJ 1461: 도서관 문제 링크: https://www.acmicpc.net/problem/1461 N권의 책이 0에 존재하고, 한번에 M권의 책을 들고 원래 자리로 옮길 수 있을 때, 최소 걸음 수를 구하는 문제이다. 가장 먼 거리에 있는 책을 정리하고 다시 0으로 돌아오는 것은 비효율적이므로, 가장 먼 거리에 있는 책은 맨 마지막에 정리하고 0으로 돌아오지 않아야 한다. 가장 먼 거리에 있는 책이 0보다 큰 위치에 존재한다면, 0보다 작은 위치에 있는 책들을 우선 정리 하고, 0보다 큰 위치에 존재한 책들을 정리하는데, 가장 멀리 있는 책은 가장 마지막에 정리하고 돌아오지 않는다.가장 먼 거리에 있는 책이 0보다 작은 위치에 존재한다면, 0보다 큰 위치에 있는 책들을 우선 정리 하고, 0보다 작은 위치에 존재한 책들을 정.. 2025. 3. 22. 이전 1 2 3 4 ··· 14 다음