본문 바로가기

개발자 강화/코딩 테스트

 (60)
[백준] 20922 겹치는 건 싫어 / 구현 / Python 실1 (개발자 강화/코딩 테스트) 2024. 11. 28. 23:51 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 (개발자 강화/코딩 테스트) 2024. 11. 27. 23:33 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값을 출력하고그 외에는..
[백준] 9935 문자열 폭발 / 구현 / Python 골4 (개발자 강화/코딩 테스트) 2024. 11. 26. 23:05 https://www.acmicpc.net/problem/9935 처음에 파이썬 replace로 비벼보려고 했는데, 칼같이 시간초과 나온대서 포기;; 다른 블로그 아이디어를 참고했다 stack에 문자열 요소를 하나씩 집어넣으면서그때마다 stack의 가장 최근에 집어넣어진 요소를 기준으로 폭발문자열 길이만큼 탐색했을 때그 문자열이 폭발문자열과 일치하면 stack에서 폭발문자열 길이만큼 pop하며 지워준다 stack이 비어있으면 FRULA를 출력하고그렇지 않으면 stack을 join을 써서 문자열로 만들어 출력한다 s = input()bomb = input()b = len(bomb)stack=[]for el in s: stack.append(el) if ''.join(stack[-b:])==bom..
[백준] 10026 적록색약 / BFS / Python 골5 (개발자 강화/코딩 테스트) 2024. 11. 25. 14:46 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 (개발자 강화/코딩 테스트) 2024. 11. 24. 22:56 https://www.acmicpc.net/problem/5567 BFS를 이용해 탐색하는데, depth 제한이 있음에 주의해야 한다 일단 상근이 학번인 1부터 시작한다 q를 돌면서현재 탐색 중인 요소 번째에 친구 관계를 분석한다만약 탐색한 적이 없는 친구면, visited로 바꿔주고,초대할 친구 목록에 추가해준다초대할 친구 목록은 set으로 선언했기 때문에 중복되지 않는 요소만 추가된다 추가 탐색은 친구의 친구까지만 가능하기 때문에현재 탐색 요소가 상근를 기준으로 친구를 탐색할 때만 q에 추가한다 그 외에 q에 추가할 경우, 친구의 친구의 친구를 탐색할 수 있기 때문 탐색을 모두 마친 후 invite의 길이를 출력하면 된다 from collections import dequen = int(input()..
[백준] 1806 부분합 / 투포인터 / Python 골4 (개발자 강화/코딩 테스트) 2024. 11. 23. 17:54 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초 제한을 맞출 수 있을 것 같았음 두루뭉술하게 떠올렸을 때쭉 선형 탐색을 하면서 누적합을 하는데,..
[백준] 14719 빗물 / 구현 / Python 골5 (개발자 강화/코딩 테스트) 2024. 11. 23. 16:16 https://www.acmicpc.net/problem/14719 SWEA에서 풀었던 VIEW 문제와 비슷하다고 생각햇음접근법은 좀 다르지만.. 결국 아이디어는 다른 블로그를 통해 얻긴 했는데 빗물이 고일 수 있는 위치는 1에서 n-2번째 블록이고, for문 범위를 잡는다현재 i번째 블록에서 좌, 우를 탐색한다 좌에서 max인 값과 우 에서 max값을 찾으면내 블록 위로 고일 수 있는 좌,우 기둥의 max값을 알 수 있음어차피 빗물은 벽이 아무리 멀리 떨어져있어도, 나보다 높은 좌우 기둥이 있으면 무조건 고임 좌,우 기둥 중 min값에 맞춰 빗물이 최대로 고일 수 있음 그리고, 그 좌,우 min 값 중 나 자신의 높이를 빼면 내 위치에서 고이는 빗물의 높이를 알 수 있음 그러나 좌,우min-나자신 값이..
[백준] 회전초밥 / Python 실1 (개발자 강화/코딩 테스트) 2024. 11. 22. 11:37 https://www.acmicpc.net/problem/2531처음에 했던 생각 for문으로 n개의 초밥을 탐색하면서i번째 초밥부터 k개의 초밥을 set으로 묶어서 종류를 헤아린 후종류 안에 c 쿠폰 초밥이 포함되지 않으면 1을 더해준 후이전 i-1번째 초밥까지 헤아린 종류 수 중 최댓값을 변수에 저장해놓고현재 상태에서 max로 비교해서 업데이트하면 어떨까 = 시간초과 엔딩 #접시, 초밥가짓수, 연속, 쿠폰번호n,d,k,c = map(int,input().split())a = [int(input()) for _ in range(n)]#쿠폰번호가 포함되지 않은 k개를 먹으면 최대가짓수?dp = [0]*n#i번째 위치에서 k개를 먹을 때 가짓수?s=0for i in range(n): temp=[] ..
[이취코] 음료수 얼려먹기 / BFS / Python (개발자 강화/코딩 테스트) 2024. 11. 21. 22:50 2차원 배열에서 0은 빈공간, 1은 벽얼음 개수를 구하는거라 0으로 구성된 묶음이 총 몇 개인지 구하면 됨 BFS의 전통적인 문제로... 전설의 문제 '그림'과 같은 형태 from collections import dequen,m = map(int,input().split())a = [list(map(int,input().strip())) for _ in range(n)]visited = [[False for _ in range(m)] for _ in range(n)]dx=[0,0,1,-1]dy=[1,-1,0,0]def bfs(i,j): q = deque() q.append([i,j]) visited[i][j]=True while q: cur = q.popleft() ..
[이취코] DP 실전 - 못생긴 수 / Python (개발자 강화/코딩 테스트) 2024. 11. 21. 22:05 2,3,5만을 약수로 가지는 합성수를 못생긴 수라고 한다1은 못생긴 수라고 가정한다n번째 못생긴 수를 구하자 처음 아이디어 접근 일단 1,2,3,4,5가 못생긴 수인건 맞으니dp = [1,1,1,1,1] 로 세팅한다 n이 5보다 작은 경우에는 n을 return하도록 한다 그 이상은 dp를 구한다 못생긴 수를 세는 cnt와 현재 수를 나타내는 cur 변수를 둔다while문을 돌며 cnt가 n에 도달하면 멈춘다 while문 내에서 현재 살펴보는 수를 1씩 증가시킨다현재 수가 2or3or5로 나누어떨어지고, dp[i//(2or3or5)-1]값이 1이라면그 수는 2,3,5만을 인수로 가진다는 뜻못생긴 수 cnt를 증가시키고, dp에도 못생긴 수라는 뜻으로 1을 삽입 그 외에는 0을 삽입한다 마지막에 현재 숫자를..

티스토리툴바