2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net ✏️ 풀이 입력으로는 k개의 영역을 준다. 그래서 나는 x1, y1, x2, y2로 입력을 받았다. 이렇게 입력을 받아서 previsit으로 입력받은 영역을 방문 처리했다. 간단하게 표현하면 미로에서 벽을 세운 느낌으로 처리했다. 그리고 BFS를 통해서 영역의 너비를 계산했다. 이문제에서는 처음 입력받은 좌표에 해당하는 구역만큼만 방문 처리를 했으면 금방 풀 수 있는 문제였다. BFS는 평소에 풀던 다른 문제처럼 처리를 하면 되는 거여서 금방..
1G Cellularization (셀룰러화) 셀룰러 구조: 1G에서는 지리적으로 넓은 지역을 작은 셀로 분할하고, 각 셀에 기지국을 설치하여 셀룰러 구조를 형성했습니다. 겹치지 않도록 배치된 셀은 전체 지역을 균일하게 커버하도록 설계되었습니다. 무선 주파수의 효율적 사용: Cellularization은 무선 주파수를 효율적으로 사용하여 여러 휴대전화가 동시에 통화할 수 있도록 했습니다. 작은 셀 단위로 나누어 간섭 없는 통화를 가능케 했습니다. 무선 신호의 간섭 감소: 셀룰러 구조는 특정 지역에서 발생하는 통화에 대한 무선 신호 간섭을 감소시켰습니다. 핸드오프를 통해 이동 중에도 통화 품질을 유지할 수 있었습니다. 용량 향상과 확장성: Cellularization은 네트워크 용량을 향상하고 확장성을 제..
2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 분할 정복 공부하면서 이렇게 4개로 나눠지는 형태를 쿼드트리라는 것을 처음 알았다. 이렇게 4분할 해서 재귀를 돌리는 형태의 코드가 많이 나왔다. import sys input = sys.stdin.readline def divide(r, c, n): check, flag = matrix[r][c], True for i in range(r, r+n): for j in range(c, c+n): if check != matrix[i][j..
1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 위의 문제를 보고 분할 정복 문제라는 것을 알았지만, 분할 정복를 정확하게 모르고 있었기에 풀어내는데 조금 오래 걸렸다. import sys input = sys.stdin.readline def printResult(value, location): print(value + location) exit(0) def divide(n, r, c, value): n //= 2 if r < n and c < n: if n == 1: printResult(valu..
11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 처음에는 아래와 같이 정말 간편하게 풀 수 있을 것이라고 생각하고 풀었다. 아래와 같이 sum과 슬라이싱을 이용했더니 바로 실패했다. 그래서 누적합에 대해서 공부를 했다. n, m = map(int, input().split()) data = list(map(int, input().split())) for _ in range(m): i, j = map(int, input().split()) print(sum(data[i-1:j])) 아래는 ..
1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP문제를 잘 몰라서 처음에는 8까지 모든 경우의 수를 적었다. 적고 보니 어떻게 풀어야할 지 보여서 쉽게 풀 수 있다. 3이나 2로 나눠지면 best를 업데이트를 했다. 최소값만 넣을 수 있게 min을 활용해서 풀고, 마지막에 append하기 전에 min값을 넣었다. 이렇게 풀고 성공(832ms)은 했는데 생각을 해보니 굳이 인덱스를 넣을 필요가 없다는 것을 알게 되었다. import sys input = sys.stdin.readline num = int(input()) memo = [(0,0), (1,0)] for i in range(2, num+1): best = 99..
16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 이 문제를 풀면서 어떻게 BFS를 통해서 최소 탐색을 할 지 고민을 했습니다. 그래서 1~6을 추가해가면서 100이 되는 것을 확인해야한다고 생각했는데, 어떻게 풀어 나갈지가 가장 문제였다. 기존과 비슷하게 BFS를 진행하고, 각 경우의 수를 나누어 풀어나갔다. import sys from collections import deque input = sys.stdin.readline def bfs(start): q = ..
7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 앞에서 풀었던 토마토 문제와 같은 방법으로 BFS를 사용해서 풀면 쉽게 풀 수 있었다. 대신 2차원이 아닌 3차원 배열이라서 H의 값을 더 추가해서 풀었다. 코드는 앞에서 풀었던 BFS와 똑같지만 matrix의 차원만 하나 더 추가된 방법으로 풀었다. 그래서 쉽게 풀 수 있었다. import sys from collections import deque input = sys.stdin.readline directions = [(1, 0, 0..
