Jerry의 컴퓨터 일기 💻

[Python][백준] 13144. List of Unique Numbers / 투포인터 (G4)

🔗링크 :  https://www.acmicpc.net/problem/13144🗒️파이썬 코드 풀이import sysinput = sys.stdin.readlineN = int(input())lst = list(map(int,input().split()))number = set()rs = sp = 0 for ep in range(N): while lst[ep] in number: number.remove(lst[sp]) sp += 1 number.add(lst[ep]) rs = rs + ep - sp + 1print(rs)ex)1 2 3 1 2 1. 위와 같은 입력을 예시로 들어보자. 아마 대부분의 보통은 1 / 1,2 / 1,2,3 /  2 / 2,3 / ..

🔗링크 :  https://www.acmicpc.net/problem/14891🗒️파이썬 코드 풀이import sysfrom collections import dequeinput = sys.stdin.readline# 방향 로테이션def wheel_rotate(graph,i,dir): graph[i].rotate(dir) return # 방향 로테이션 스택에 넣어주기def stack_rotate(graph,n,dir): stack = [(n,dir)] rdir = -dir for i in range(n,0,-1): if graph[i][6] != graph[i-1][2]: stack.append([i-1,rdir]) ..

🔗링크 :  https://www.acmicpc.net/problem/12865🗒️파이썬 코드 풀이N = int(input())INF = sys.maxsizedp = [INF]*(N*4)dp[0],dp[1] = 0,0for i in range(1,N+1): dp[i*3] = min(dp[i]+1, dp[i*3]) dp[i*2] = min(dp[i]+1, dp[i*2]) dp[i+1] = min(dp[i]+1, dp[i+1])dp = dp[:N+1]cur = Nlst = [N]for k in range(N,0,-1): if dp[k] == dp[cur]-1 and (k*3==cur or (k+1)==cur or (k*2)==cur) : lst.append(k) ..

🔗링크 :  https://www.acmicpc.net/problem/12865🗒️파이썬 코드 풀이N,K = map(int,input().split())lst = [(0,0)]dp = [[0] * (K+1) for _ in range(N+1)]for _ in range(N) : x,y = map(int,input().split()) lst.append((x,y))for i in range(len(lst)): w,v = lst[i] for j in range(1,K+1) : if j  1. 배낭 문제는 2차원 DP 테이블이 필요하다. (인덱싱을 편하게 하기위해 왠만하면 0을 추가 해준다. ) 2. (w,v) 무게와 가치를 입력받은 리스트를 만들어준다. 3. 입력받은..

🔗링크 :  https://www.acmicpc.net/problem/9084➕ 문제 풀기 전 먼저 동전 문제를 풀기 전에 아래 예시를 이해해보자.  1,2,3원으로 7원까지의 만들 수 있는 경우의 수이다.     (0)  (1)  (2)  (3)  (4)  (5)  (6)  (7)  1:  0     1    1    1     1     1    1    12:  0     1    2    2     3     3    4    43:  0     1    2    3     4     5    7    8 먼저 1원부터 시작한다. 오직 1원으로 1~7원을 만들 수 있는 경우의 수는 모두 1이다.이제 2원과 3원으로 가면 위와 같은 경우의 수가 나온다. (해당 경우의 수는 하나 하나 직접 찾아서 ..

🔗링크 :  https://www.acmicpc.net/problem/1541🗒️파이썬 코드 풀이import sysinput = sys.stdin.readlineS = input().split('-')lst = []for i in range(len(S)): lst.append(sum(list(map(int,S[i].split("+")))))rs = lst[0]for ls in lst[1:]: rs -= lsprint(rs) 1. 보통 입력은 split()으로 하는데, 이 문제의 경우 '-' 로 나눠준다.(한 번 빼기가 시작되면 그 이후 모든 숫자가 한꺼번에 빼주는 것이 최소 값을 만드는 최선의 선택) 2. 한번 '-' 로 나눠준 lst를 이번에는 '+' 로 나눠주고, int 형으로 바꾸면서..

🔗링크 :  https://www.acmicpc.net/problem/7569🗒️파이썬 코드 풀이import sysfrom collections import dequeM,N,H = map(int,sys.stdin.readline().split())graph = [[list(map(int,sys.stdin.readline().split())) for _ in range(N)] for _ in range(H)]di,dj,dh = [0,1,0,-1,0,0],[1,0,-1,0,0,0],[0,0,0,0,1,-1]def find_tomato(grp): q = deque([]) for h in range(H): for i in range(N): for j in r..

🔗링크 :  https://www.acmicpc.net/problem/14888🗒️파이썬 코드 풀이import syssys.setrecursionlimit(100000) input = sys.stdin.readlineN = int(input())lst = list(map(int,input().split()))add,sub,mul,div = map(int,input().split())mx = -sys.maxsizemn = sys.maxsizedef dfs(n,rs,add,sub,mul,div): global mn global mx if n == N: mn = min(rs,mn) mx = max(rs,mx) return if add > ..

🔗링크 :  https://www.acmicpc.net/problem/18352🗒️파이썬 코드 풀이import sysfrom collections import dequeinput = sys.stdin.readlineN,M,K,X = map(int,input().split())linked_lst = [[] for _ in range(N+1)]cost = [-1] * (N+1)for _ in range(M): s,e = map(int,input().split()) linked_lst[s].append(e)q =deque([X])cost[X] = 0while q: v = q.popleft() for e in linked_lst[v]: if cost[e] ==..

🔗링크 :  https://www.acmicpc.net/problem/1753🗒️파이썬 코드 풀이import sysimport heapqinput = sys.stdin.readlineV,E = map(int,input().split())K = int(input())linked_lst = [[] for _ in range((V+1))]for _ in range(E): u,v,w = map(int,input().split()) linked_lst[u].append((w,v))INF = sys.maxsizecost = [INF] * (V+1)heap = [[0,K]] cost[K] = 0while heap: ew,ev = heapq.heappop(heap) for nw,nv in..