Algorithm475 [파이썬] 백준 2230 : 수 고르기(골드5) [파이썬] 백준 2230 : 수 고르기(골드5)https://www.acmicpc.net/problem/2230풀이방향성 생각입력이 10만 이상이라 $O(N^2)$로는 불가능하다.투 포인터로 제한적인 영역을 탐색하면서 $O(N)$으로 풀어주기. 전체코드import sysinput = lambda : sys.stdin.readline().rstrip()N,M = map(int,input().split())arr = [int(input()) for _ in range(N)]arr.sort()l,r = 0,0answer = float('inf')while l코멘트while 조건에서, l==r까지는 가능하다.같은 숫자에서 조건을 만족시키고, l+=1로 탈출하면 된다.양 쪽에서 포인터를 조이는지, 같은 지점에서 .. 2024. 10. 2. [파이썬] 백준 3151 : 합이 0 (골드4) [파이썬] 백준 3151 : 합이 0 (골드4)https://www.acmicpc.net/problem/3151풀이방향성 생각입력 크기가 10000이라, dict으로 val:개수 형태로 반환해서 계산하기$O(N)$으로 압축해주고, aaa, aab 에서 각 $O(N)$이라 $O(2N)$이다.abc로 0을 만드는 경우가 $O(N^2)$이라 브루트포스로 풀이 전체코드from collections import defaultdict as ddN = int(input())arr = list(map(int,input().split()))answer = [0,0,0]cnts = dd(int)for a in arr: cnts[a] += 1# a a aif cnts[0] >= 3: answer[0] += cnt.. 2024. 10. 2. [파이썬] 백준 1595 : 북쪽나라의 도로 (골드4) [파이썬] 백준 1595 : 북쪽나라의 도로 (골드4)https://www.acmicpc.net/problem/1595풀이방향성 생각BFS를 통해서 한 점에서 가장 끝 점으로 간 후 BFS를 돌려준다.트리의 지름을 구하는 문제와 동일한 발상전체코드from collections import deque, defaultdict as ddimport sysinput = lambda: sys.stdin.readline().rstrip()graphs = dd(list)while True: try: a,b,c = map(int,input().split()) graphs[a].append((b,c)) graphs[b].append((a,c)) except: .. 2024. 10. 1. [파이썬] 백준 1202 : 보석도둑 (골드2) [파이썬] 백준 1202 : 보석도둑 (골드2)https://www.acmicpc.net/problem/1202풀이방향성 생각그리디 + 정렬각 가방에 들어갈 수 있는 보석들의 최대 무게를 구해야한다.가방마다 for문을 돌리고, 가방에 들어가는 보석들 중 최대 가격을 찾아서 합해주기.입력 사이즈가 커서 $O(NlogN)$ 기반이라 힙 말고 떠올릴 자료구조는 크게 없어보인다.전체코드import heapq as hqimport sysinput = lambda : sys.stdin.readline().rstrip()n,k = map(int,input().split())J = sorted((tuple(map(int,input().split())) for _ in range(n)), reverse=True)B = .. 2024. 10. 1. 이전 1 ··· 38 39 40 41 42 43 44 ··· 119 다음