본문 바로가기

백준43

백준 11505 - 구간 곱 구하기 (Python3) https://www.acmicpc.net/problem/11505💡 해결방법구간 곱을 다루는 세그먼트 트리를 구현해서 문제 해결👀 풀이세그먼트 트리로 초기화하는 메서드기존 값을 변경해주는 메서드입력된 구간 내의 곱을 반환하는 메서드를 구현하여 정해진 쿼리를 처리한다.특징으로는 기존 값을 원래는 내려가면서 업데이트를 했다면, 이번에는 말단 노드에서 시작해서 루트 노드까지 올라오며 update를 한다.🧾코드import sysinput = sys.stdin.readlinemod_value = 10**9+7N, M, K = map(int, input().split())arr = [int(input()) for _ in range(N)]tree = [0] * (N*4)def init(start, end, .. 2025. 3. 31.
[G1] 백준 2042 - 구간 합 구하기 (Python3) https://www.acmicpc.net/problem/2042💡 해결방법세그먼트 트리를 구현하고 정해진 명령어대로 수행한다.🧾코드# 2042 구간 합 구하기import sysinput = sys.stdin.readlineN, M, K = map(int, input().split())arr = [int(input()) for _ in range(N)]tree = [0] * (N*4)def init(start, end, idx): if(start == end): tree[idx] = arr[start] return tree[idx] mid = (start+end) // 2 tree[idx] = init(start, mid, idx*2) + init(mid+1,.. 2025. 3. 29.
[G5] 백준 2225 - 합분해 (python3) https://www.acmicpc.net/problem/2225💡 해결방법1차원에선 점화식이 보이지 않아서 2차원 grid에서 접근했다.별다른 해결방법이 있던게 아니라 모든 경우의 수를 보고나면 규칙이 보일까 해서였다.운이 좋게 해결할 수 있던 문제다. 아래는 dp table을 채우기 위해 완전탐색을 하는 코드다.dp[n][k] = n을 k개의 합으로 구하는 방법#2225 합분해 dp table 테스트import syssys.setrecursionlimit(10**5)n, k = map(int, input().split()) dp = [[0 for _ in range(k+1)] for __ in range(n+1)]for i in range(n+1): dp[i][1] = 1for i in .. 2025. 3. 17.
[G3] 백준 1520 - 내리막 (Python3) https://www.acmicpc.net/problem/1520💡 해결방법DFS + DP메모제이션DFS 만으로 풀면 시간초과or메모리초과DP 만으로 풀면 메모리초과처음엔 상하좌우가 아니라 [좌,우,아래]로만 움직일 수 있는 줄 알고 O(N^3) 풀이를 준비했던,, (0,0)에서 (r-1, c-1) 위치로 이동하는 경우의 수를 구하는 문제이다.이동 조건은 상하좌우 다 되고, 대신 grid의 현재위치의 높이가 이동하려는 위치의 높이보다 높아야 된다.처음 접근했던 방법이다.목적지(10)에서 목적지로 가는 방법은 0개라고 가정하고, 목적지에서 상하좌우에 자기 높이보다 높은 숫자로 이동하면서 {현재 방법 + 1}로 두는 방법으로 접근을 했다. 하지만 결국 그냥 dfs로 푸는 것과 별 차이가 없었다. 아싸리 그.. 2025. 3. 10.
[G5] 백준 2230 - 수 고르기 (Python3) https://www.acmicpc.net/problem/2230💡 해결방법A 배열에 입력받은 원소들을 정렬하면 이 문제를 쉽게 풀 수 있다.항상 차이가 M이상인 두 수를 고를 수 있다.A 배열을 정렬하면, 투포인터를 적용할 수 있기 때문이다.투포인터는 정렬된 배열에서 순차적으로 접근할 때 적용할 수 있는 알고리즘이다.🧾코드# 2230 수 고르기N, M = map(int, input().split())arr = [int(input()) for _ in range(N)]arr.sort()l, r = 0, 0ans = float('inf')while l = M: l += 1 ans = min(ans, differ)print(ans) 2025. 3. 1.
[G2] 백준 7453 - 합이 0인 네 정수 (Python3) https://www.acmicpc.net/problem/7453완전탐색( O(n^4) )으로 모든 경우의 수(조합)을 따져서 풀면 시간 안에 절대 해결할 수 없다.4,000 × 4,000 × 4,000 × 4,000 = 256,000,000,000,000 (256조 번 연산) 따라서 더 효율적인 방법이 필요하다. 💡 아이디어A[a] + B[b] + C[c] + D[d] = 0 을 만족하는 (a,b,c,d) 순서쌍의 개수를 구하는 문제이다.위 식을( A[a] + B[b] ) + ( C[c] + D[d] ) = 0 으로 고쳐 써도 전혀 문제 없다. AB: 모든 A[i]+B[j] 조합을 저장한 배열 CD: 모든 C[k]+D[l] 조합을 저장한 배열그래서 AB[i]+CD[j]=0 인 경우의 개수를 세면 이 .. 2025. 2. 25.
[G5] 백준 3020 - 개똥벌레 (Python3) https://www.acmicpc.net/problem/3020 문제 설명높이가 HHH일 때, 몇 개의 벽을 뚫어야 하는지 계산하고,그중에서 최소로 뚫을 수 있는 횟수와 그런 높이가 몇 개인지 구하는 문제이다.해결 방법은 크게 두 가지로 나뉜다.누적합(Prefix Sum) 활용이분 탐색(Binary Search) 활용해결 방법 1: 누적합(Prefix Sum)누적합을 사용하면 높이별로 벽을 뚫어야 하는 개수를 빠르게 계산할 수 있다.알고리즘 설명석순(아래에서 위로 솟는 기둥)과 종유석(위에서 내려오는 기둥)을 나눈다.종유석 높이를 변환하여 H - 종유석 길이 + 1 형태로 정리석순과 종유석의 누적합 배열을 만든다.각 높이별로 벽을 뚫어야 하는 개수를 계산하여 최소값을 찾는다.💻 코드 (누적합)# 30.. 2025. 2. 25.
[S4] 백준 31797 - 아~파트 아파트(Python3) https://www.acmicpc.net/problem/31797💡 해결과정 문제에 함정이 있었다. 아파트 술게임 특성상 절대 중간에 다른 층이 존재할 수 없다. 또, 독자적인 층을 부여할 수 없다.예를 들면 사람은 3명인데, 손을 가장 위로 뻗으며, "내 오른손은 100층" 뭐 이런식으로 말이다.하지만 이것은 실제 게임을 하는것이 아니라 문제이다. 고정관념에 휩싸였다간 이런 중간층 없이 높은 층을 불러버려 맞왜틀?을 외치게 만드는 문제다.  두 손의 높이를 편하게 left, right라고 부르겠다. 문제에서 주어지는 입력 조건은 참가자의 수 1,000일때 이 left, right가 9999, 10000일수도 있는 것이다.👀 풀이그래서 압축하듯이 정렬해서 풀면 된다.그래서 좌표 압축 문제가 이 문제.. 2024. 11. 14.

티스토리툴바