본문 바로가기

전체 글

 (135)
[백준] 2304 창고 다각형 / Python 실2 https://www.acmicpc.net/problem/2304 가장 높은 기둥을 기준으로 좌 우로 나눔 왼쪽0부터 시작해서 가장 높은 기둥의 index까지우선 height는 가장 첫 번째 기둥 높이로 초기화한다 결과값에 height*(다음 기둥 위치-현재 기둥 위치)를 더해서 면적을 업데이트한다만약 현재 기둥보다 다음 기둥이 높은 경우에는 height값을 다음 기둥 높이로 업데이트한다 오른쪽은이 과정을 끝에서부터 가장 높은 기둥의 index까지 역순으로 진행한다height는 가장 마지막 기둥 높이로 초기화 한다결과값에 height*(현재 기둥 위치-이전 기둥 위치)를 더한다마찬가지로 현재까지 탐색한 기둥 중 가장 높은 기둥을 height에 업데이트 해야 한다 굿! https://velog.io/@ho..
[백준] 20922 겹치는 건 싫어 / 구현 / Python 실1 https://www.acmicpc.net/problem/20922 보자마자 필이 짜르르 옴이건 슬라이딩 윈도우다 윈도우 범위 조절을 위해 start, end 두개 사용범위 내 숫자 빈도는 딕셔너리 사용 현재 윈도우 범위에서 특정 숫자가 K개를 초과하면start를 움직여서 k개가 되도록 while문을 돌면서 이동 윈도우 최장 길이는end-start+1로 업데이트 from collections import defaultdictn,k = map(int,input().split())a = list(map(int,input().split()))count = defaultdict(int)start=0max_l = 0for end in range(n): count[a[end]]+=1 while count..
[백준] 21921 블로그 / 구현 / Python 실3 https://www.acmicpc.net/problem/21921 슬라이딩 윈도우로 푸는 문제! 처음에는 for문 돌면서 배열에 s = a[i:i+k] 값을 저장하고, max 값을 업데이트 하는 방식으로 구현했는ㄴ데이렇게 하면 O(n*x)가 되어 시간초과가 났다 그래서 슬라이딩 윈도우를 사용하면서 전역변수에서 현재 a[i]값을 더하고 이전 a[i-x] 원소 값을 빼서현재 sum이 x개의 원소 합으로 유지되도록 구현한다이렇게 하면 slicing으로 탐색해서 끊지 않아도 된다 만약 현재 sum이 이전 max값보다 크다면count값을 1로 리셋하고max값을 현재 sum으로 대체한다 만약 현재 sum과 max값이 같다면 count을 1 증가한다 max값이 0보다 크면 max값과 count값을 출력하고그 외에는..

티스토리툴바