구간 합 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 합 배열을 구하는 것이 중요 리스트 A 가 있을 때 합 배열 S S[ i ] = A[ 0 ] + A[ 1 ] + A[ 2 ] + ··· + A[ i-1 ] + A[ i ] # A[0] 부터 A[i] 까지의 합 합 배열을 미리 구해 놓으면 기존 리스트의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1) 로 감소 A[i] 부터 A[j] 까지 리스트 합을 합 배열 없이 구할 경우 최악의 시간 복잡도는 O(N) 이 된다. 합 배열 공식 S[ i ] = S[ i-1 ] + A[ i ] 구간 합 구하는 공식 S[ j ] - S[ i-1 ] # i에서 j까지 구간 합 11659 11659번: 구간 합 구하기 4 첫째..
🏷️CS/Algorithm
13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net import sys import math input = sys.stdin.readline test = int(input()) apply = map(int,input().split()) superv, sub_superv = map(int,input().split()) super = 0 for i in apply: i -= superv super += 1 if i > 0 : super += math...
2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net N = int(input()) num = 1 sum = 0 while True : sum += num for i in str(num): sum += int(i) if sum == N : print(num) break if num > N : print(0) break sum = 0 num += 1 코드 설명 14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제..
1152번: 단어의 개수 첫 줄에 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 공백 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열 www.acmicpc.net # 처음 풀이 s = input() s = s.strip().split() print(len(list(s))) # 사람들이 다 한줄로 푸네요.... print(len(list(input().strip().split()))) sys readline 써서 입력값 받아 오기 아래 코드는 러닝메이트 리더의 풀이 # coding = utf-8 if __name__ == '__main__' : import sys input = sys.stdin.readline fro..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내가 짠 코드 - 효율성 테스트 통과 실패 def solution(n): answer = 0 prime = [] for i in range(2,n+1,1): for j in range(2,i+1,1): if i%j == 0: prime.append(j) if len(prime) == 1: answer += 1 prime = [] else : prime=[] return answer 해결 방향 1. n^2되는 문제 해결하기 2. 수의 특징을 활용하여 소수 판별 함수에서 for문의 반복 횟수 줄이기 3. 에라스토..
