본문 바로가기
반응형

프로그래밍/알고리즘 & 자료구조73

백준 1644 : 소수의 연속합 with 파이썬 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 1. n까지의 소수 리스트를 만들어 문제를 해결하는 경우, 시간초과됨 n=int(input()) nums=[] for i in range(2, n+1): #소수는 2부터 n까지 cnt=0 for j in range(1, i+1): #i를 나누는 수는 1부터 i까지 if i%j==0: cnt+=1 if cnt==2: nums.append(i) #print(nums) result=0 summ=nums[0] st, end=0,0 while True: if summ==n: result+=1 summ-=nums[st] st+.. 2024. 1. 31.
백준 2018 : 수들의 합 5 with 파이썬 https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net # 포인트 1. 애매할땐 print()를 하여 구체적인 값을 보고 코드를 수정해주기 n = int(input()) cnt,summ = 0,0 start, end = 1,1 while end n: summ -= start start += 1 else: summ+=end end+=1 print(cnt) 내 경우에는 #프린트를 찍으면 n=15일 경우, end가 15인 경우가 찍히지.. 2024. 1. 31.
백준 1806 : 부분합 with 파이썬 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net # 포인트 1. ans에 최대 갯수를 설정하고, min() 함수를 통해 최소 갯수 갱신 2. 투 포인터인 앞쪽 인덱스 i와 뒤쪽 인덱스인 j 만들기 3. while 문을 돌며 최소갯수를 찾다가 뒤쪽 인덱스가 총갯수에 도달하면 break N, S = map(int,input().split()) nums = list(map(int,input().split())) i, j = 0, 0 s.. 2024. 1. 30.
백준 2559 : 수열 with 파이썬 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 1. sum()을 이용하면 시간복잡도가 O(n)이 되므로 시간초과 n,k=map(int, input().split()) num=list(map(int, input().split())) maxv=0 for i in range(n): tmp=sum(num[i:i+k]) #sum()의 시간복잡도는 O(n) maxv=max(maxv, tmp) #max()의 시간복잡도는 O(n) print(m.. 2024. 1. 29.
백준 14497 : 주난의 난 with 파이썬 https://www.acmicpc.net/problem/14497 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파 www.acmicpc.net # 포인트 1. #이 포함된 map을 받아와야 하기때문에 int로 변경할 것 없이 그냥 input().strip()으로 받아온다. 2. 좌표는 현재 위치(사각형)의 왼쪽위에 있기 때문에 y-1, x-1처럼 -1씩 해줘야 한다. 3. 숨바꼭질3와 비슷한 구성 친구가 없는 경우에는 그냥 통과할 수 있지만, 친구가 있거나, #인 경우에는 +점프를 해야 통과할 수 있다 from collecti.. 2024. 1. 28.
백준 1261 : 알고스팟 with 파이썬 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net # 포인트 1. v=[[-1]*가로 for _ in range(세로)] 방문처리하는 리스트의 기본값을 -1로 놓고, 방문하지 않았을때는 -1, 방문해서 벽을 뚫지 않으면 +0, 벽을 뚫으면 +1 로 한번에 체크해주기 2. 벽을 부술 필요가 없을 경우, q.appendleft()해주어 먼저 탐색할 수 있도록 from collections import deque m,n=map(i.. 2024. 1. 26.
반응형

티스토리툴바