문제 풀이/백준47 [S1] 백준 1992 - 쿼드트리 (Python3) https://www.acmicpc.net/problem/1992💡 해결방법분할정복 알고리즘을 적용해 해결했다.👀 풀이풀이 설명🧾코드# BOJ 1992N = int(input())grid = [input() for _ in range(N)]def sol(N, r=0, c=0): color = grid[r][c] for i in range(r, r+N): for j in range(c, c+N): if color != grid[i][j]: # 모두 같은 색이 아니라면 # 조건에 나온 순서대로 4분할로 쪼갠다. return '('+ sol(N//2, r, c) + sol(N//2, r, c + N//2) +.. 2024. 11. 10. [G5] 백준 1074 - Z (Python3) https://www.acmicpc.net/problem/1074💡 해결방법분할정복 알고리즘을 적용해서 문제를 해결했다.👀 풀이항상 2**(N*2) 매트릭스(r, c) 좌표 정보위 두 정보를 바탕으로 (r, c)가 몇 사분면에 있는지 파악해서 N 번만에 몇 번만에 방문하는지 계산한다.🧾 코드# 1074N, r, c = map(int, input().split())ans = 0while N: N -= 1 # 제1사분면 if r = 2**N: ans += 2 ** (N*2) c -= 2**N # 제2사분면 elif r = 2**N and c = 2**N and c >= 2**N: ans += 3*(2**(N*2)) r -= 2.. 2024. 11. 10. [S3] 백준 1463 - 1로 만들기(Python) https://www.acmicpc.net/problem/1463 풀이👀1부터 X까지 반복문으로 1회 순환한다.i (1에 대해서 dp[i]라 할 때, dp[i]는 1에서 출발하여 주어진 조건을 만족하며 i를 만들기 위해 필요한 연산 최소 횟수이다.그러면dp[i]는 (dp[i-1], dp[i//2], dp[i//3], dp[i//5]) 중에서 최솟값을 찾은 다음, +1을 한 값으로 결정난다.코드💻# 1로 만들기X = int(input())dp = [10**7] * (X+1)dp[1] = 0for i in range(2, X+1): dp[i] = dp[i-1] + 1 if i%2 == 0: dp[i] = min(dp[i//2] + 1, dp[i]) if i%3 == 0: .. 2024. 9. 5. [G4] 백준 12970 - AB (Python3) https://www.acmicpc.net/problem/12970풀이 아이디어문자열의 길이에 따라 A와 B로 만들 수 있는 조합의 최대 개수가 정해져있다. 직접 여러 길이의 문자열을 만들어가며 풀이할 때 알게 된 특징이다.길이가 10인 문자열로 만들 수 있는 조합의 최대 개수는 AAAAABBBBB로, 5*5=25개이다.길이가 11인 문자열로 만들 수 있는 조합의 최대 개수는 AAAAAABBBBB → 5*6=30 or AAAAABBBBBB → 6*5=30길이가 30인 문자열로 만들 수 있는 조합의 최대 개수는 15A15B → 15*15=225최대 개수의 공식은 $ \lfloor\frac{N^2}{4}\rfloor $ 이다. 그렇다면 최소 개수는 몇 개일까? 당연히 0개이다. 모든 길이에 대해서 A 혹은 .. 2024. 5. 4. [G5] 백준 11729 - 하노이 탑 이동 순서 (Python3) https://www.acmicpc.net/problem/11729풀이 아이디어재귀적인 방법을 사용하여 하노이 탑 문제를 해결합니다. 첫 번째 장대에 있는 원판들을 세 번째 장대로 옮기는 과정에서 아래의 과정을 반복한다.n-1개의 원판을 두 번째 장대로 옮긴다.가장 큰 원판을 첫 번째 장대에서 세 번째 장대로 옮긴다.두 번째 장대에 있는 n-1개의 원판을 세 번째 장대로 옮긴다.초기 상태의 가장 큰 원판을 목표하는 곳(세 번째 장대)으로 옮기고나면, 다시 두 번째 장대의 n-1개의 원판을 첫 번째 장대로 옮겨서 n-1번째로 큰 원판을 세 번째로 옮긴다.풀이👀재귀 함수 hanoi_tower를 정의한다. 이 함수는 매개변수로 원판의 개수 n, 출발지 기둥 frm, 보조 기둥 tmp, 목표 기둥 to를 받.. 2024. 5. 4. [S1] 백준 2156 - 포도주 시식 (Python3) https://www.acmicpc.net/problem/2156풀이 아이디어DP 테이블을 사용하여 각 잔을 선택하는 경우와 선택하지 않는 경우 등을 나누어 최대값을 갱신한다.풀이👀포도주 잔이 1개일 때는 그대로 마시는 것이 최대값이므로 DP tabel의 0번째 인덱스의 초기값으로 설정한다.포도주 잔이 2개일 때는 첫 번째 잔과 두 번째 잔을 모두 마실 수 있으므로 두 잔의 양을 더한 값을 최대값으로 설정한다.포도주 잔이 3개 이상일 때는 연속으로 3잔을 마실 수 없기 때문에 경우를 나누어 최대값을 갱신한다.case1) i번째 잔을 마시지 않는 경우: d[i-1]case2) i-1번째 잔을 마시지 않고 i번째 잔을 마시는 경우: d[i-2] + wine[i]case3) i-1번째 잔과 i번째 잔을.. 2024. 4. 28. [S1] 백준 1149 - RGB거리 (Python3) https://www.acmicpc.net/problem/1149풀이 아이디어동적 계획법(DP, Dynamic Programming) 알고리즘으로 해결한다.각 집의 Red, Green, Blue 으로 색칠하는 비용이 주어졌을 때, 각 집을 칠할 때의 최소 비용을 계산한다. 이때 DP table을 이용해서 이전 집까지의 최소 비용을 가지고 현재 집을 칠할 때의 최소 비용을 구한다.풀이👀'현재 위치(i번째 집)에 대해서 전 후가 다른 색깔의 집이어야 한다.'는 조건이 걸려있다. 쉽게 풀어 설명하면 '연속해서 같은 색을 칠하지 말라'는 조건이다. 1. 첫 번째 집부터 마지막 집까지 반복하면서, 이전 까지의 최솟값으로 현재 집을 색칠할 때 최소 비용을 계산한다.코드🐱👓N = int(input())RGB .. 2024. 4. 28. [S1] 백준 1932 - 정수 삼각형 (Python3) https://www.acmicpc.net/problem/1932해결방법정수 삼각형의 맨 아래층부터 위층으로 올라간다. 각 행의 원소를 순회하면서, 현재 위치의 정수와 현재 위치의 왼쪽 아래 정수와 오른쪽 아래 정수 중 더 큰 값과의 합을 DP table에 저장한다. ( max(왼쪽아래 정수, 오른쪽아래 정수) + 현재위치 정수 )풀이👀주어진 정수 삼각형에서 아래층부터 위층으로 올라가며 각 행의 원소를 순회한다.각 행의 원소를 순회하면서 현재 위치의 정수에 다음 행(아래층)의 왼쪽 대각선 정수와 오른쪽 대각선 정수 중 더 큰 값을 더해가며 최대 합을 계산한다.모든 행을 순회하면서 이를 맨 위층까지 반복한다.최종적으로 맨 위층의 최대 합을 반환한다.코드🐱👓n = int(input())triangle.. 2024. 4. 27. 이전 1 2 3 4 5 6 다음