본문 바로가기

전체 글

 (107)
[백준] 10026 적록색약 / BFS / Python 골5 BFS 한번 풀면 BFS만 계속 푼다는 루머를 안믿었는데간단한 BFS는 그냥 바로 풀이가 눈에 보이고... 손에 한번만 익히면 다 풀 수 있어서...이것도 그냥 보자마자 바로 짜서 푼듯 2~30분 정도 걸린 듯? 적록색약이 아닌 경우 (no)적록색약인 경우(yes)로 함수를 나누고 이중 for문으로 그림 요소를 모두 탐색할 때visited 배열을 적록색약인 경우 or not 각각 2개 둬서탐색되지 않은 원소만 bfs로 진입한다 적록색약이 아닌 경우는 현재 입력된 문자와 같은 경우만 q에 append하고,적록색약인 경우에는 현재 입력된 문자가 B인 경우에는 B만 q에 append, R or G인 경우에는 R or G를 모두 q에 append한다 이렇게 bfs를 술술 짰더니 바로 맞았습니다가 떴다   fro..
[백준] 5567 결혼식 / BFS / Python 실2 https://www.acmicpc.net/problem/5567 BFS를 이용해 탐색하는데, depth 제한이 있음에 주의해야 한다 일단 상근이 학번인 1부터 시작한다 q를 돌면서현재 탐색 중인 요소 번째에 친구 관계를 분석한다만약 탐색한 적이 없는 친구면, visited로 바꿔주고,초대할 친구 목록에 추가해준다초대할 친구 목록은 set으로 선언했기 때문에 중복되지 않는 요소만 추가된다 추가 탐색은 친구의 친구까지만 가능하기 때문에현재 탐색 요소가 상근를 기준으로 친구를 탐색할 때만 q에 추가한다 그 외에 q에 추가할 경우, 친구의 친구의 친구를 탐색할 수 있기 때문 탐색을 모두 마친 후 invite의 길이를 출력하면 된다 from collections import dequen = int(input()..
[백준] 1806 부분합 / 투포인터 / Python 골4 https://www.acmicpc.net/problem/1806  이중 for문으로 그대로 구현했을 때는 시간초과가 떴다n,s = map(int, input().split())a = list(map(int,input().split()))# 연속 부분합 중 합이 s가 되는 것 중 가장 짧은 것l=100001for i in range(n): tl=0 r=0 for j in range(i+1,n): tl+=1 r+=a[j] if r>=s: l = min(l,tl) breakprint(l) 반복문은 한 번만 돌려야 0.5초 제한을 맞출 수 있을 것 같았음 두루뭉술하게 떠올렸을 때쭉 선형 탐색을 하면서 누적합을 하는데,..

티스토리툴바