📜 알고리즘

1. 문제 설명문제 URL: https://www.acmicpc.net/problem/2015이 문제는 주어진 수열에서 연속된 부분 수열의 합이 특정 값  K 가 되는 경우의 수를 찾는 문제입니다. 수열의 각 요소는 정수로 이루어져 있으며, 연속된 부분 수열을 선택했을 때 그 합이 정확히  K 가 되는 경우의 수를 구해야 합니다. 문제를 해결하기 위해 누적합을 활용하여 각 부분 수열의 합을 계산하고, 딕셔너리를 이용해 빠르게 결과를 구할 수 있습니다.2. 정답 코드import sysinput = sys.stdin.readlineN, K = map(int, input().split()) # 수열의 길이 N과 목표 합 K를 입력받음A = list(map(int, input().split())) # 수열 ..

1. 문제 설명문제 URL: https://www.acmicpc.net/problem/2189 이 문제는 주어진 미로에서 출발점(0, 0)에서 시작하여 도착점(N-1, M-1)까지 최단 경로를 찾는 문제입니다. 미로는 0과 1로 구성된 2차원 배열로 표현되며, 1은 이동 가능한 길을, 0은 이동할 수 없는 벽을 나타냅니다. 상하좌우로만 이동할 수 있으며, 최단 경로의 거리를 계산해야 합니다. BFS(너비 우선 탐색)를 이용하여 최단 경로를 구할 수 있으며, 도달할 수 없는 경우는 없습니다.2. 정답 코드import sysinput = sys.stdin.readlinefrom collections import deque# N: 미로의 행 개수, M: 미로의 열 개수N, M = map(int, input()..

1. 문제설명문제 URL : https://www.acmicpc.net/problem/1343 이 문제는 주어진 문자열에서 ‘X’로 이루어진 모든 부분을 ‘AAAA’ 또는 ‘BB’로 대체하는 문제입니다. ‘X’를 덮을 수 있는 방법은 두 가지뿐이며, 4개의 연속된 ‘X’는 ‘AAAA’로, 2개의 연속된 ‘X’는 ‘BB’로 변환할 수 있습니다. 그 외의 경우에는 덮을 수 없기 때문에 불가능한 경우를 처리해야 합니다. 예를 들어, 입력이 “XX….XXXX”일 경우, 가능한 변환은 “BB….AAAA”입니다. 만약 덮을 수 없는 패턴이 존재할 경우, -1을 출력합니다.2. 정답코드import sysinput = sys.stdin.readline# 보드를 입력받아 리스트로 변환board = list(input()..

1. 문제설명문제 URL : https://www.acmicpc.net/problem/2417이 문제는 주어진 자연수  n 에 대해, 그 수보다 크거나 같은 가장 작은 제곱수를 찾는 문제입니다. 예를 들어,  n 이 10일 경우, 4의 제곱인 16이 10보다 크거나 같은 최소의 제곱수입니다. 따라서, 출력값은 4가 됩니다.2. 정답코드import sysinput = sys.stdin.readline# 입력값 n을 정수로 읽어들임n = int(input())# 이분 탐색을 위한 시작점과 끝점 설정s = 0 e = 2**63ans = -1# 이분 탐색 수행while s = n: # 중간값의 제곱이 n보다 크거나 같은 경우 ans = mid # 가능한 답으로 설정 e..

1. 문제설명문제URL : https://www.acmicpc.net/problem/1748 이 문제는 1부터 N까지의 모든 숫자를 이어서 썼을 때, 그 숫자의 총 자릿수를 구하는 문제입니다. 예를 들어, N이 12일 경우, 1부터 12까지의 숫자를 이어서 쓰면 “123456789101112”가 되며, 이때 총 자릿수는 15가 됩니다.2. 정답코드import sysinput = sys.stdin.readline# 입력을 받아서 정수형으로 변환N = int(input())# 자리수(i)와 결과값(ans)를 초기화i = 1ans = 0while True: # 현재 자리수에서의 마지막 수(end)를 계산 end = int('9' * i) # 현재 자리수에서의 시작 수(start)를 계산 ..