본문 바로가기

전체 글

 (154)
[백준] 2668 숫자고르기 / dfs / python 골5 첫째 줄 숫자를 노드로둘째 줄 숫자를 노드와 연결된 숫자로 생각하면그래프 간선이라고 생각할 수 있다 입력받을 때 방향성 그래프 형태로 구성한다 뽑힌 숫자들이 이루는 집합, 숫자들이 가리키는 숫자들이 이루는 집합이 두 개가 동일하려면 집합 내 숫자들은 사이클을 형성해야 한다최대 사이클을 찾는 문제로 해석할 수 있다 그래프를 돌면서 현재 원소를 방문한 적이 없으면 dfs함수를 돌린다해당 원소가 시작점이 되기 때문에, 해당 원소와 빈 배열을 dfs 함수로 넘겨준다 dfs 함수만약 현재 node가 이미 방문된 경우현재까지 누적된 경로에 node값이 존재한다면 사이클임path에서 사이클에 해당하는 부분을 잘라 result 집합에 추가한다 현재 node를 방문 처리한다현재 node를 path에 추가한다현재 node..
[백준] 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..

티스토리툴바