https://www.acmicpc.net/problem/12865당연히 Knapsack problem이다.dp를 사용해서, 물건의 중량을 배열의 인덱스로, 안의 값을 해당 중량이었을 때의 최대 가치를 저장하는 데 사용한다.물건의 중량과 가치가 입력될 때마다, 최대 중량부터 해당 물건의 중량 초과일 때까지의 인덱스를 뒤부터 앞으로 돌며해당 중량을 넣었을 때와 넣지 않았을 때(기존에 저장되어 있던 값)을 비교하여, 둘 중 큰 값을 저장한다.뒤에서부터 앞으로 도는 이유는, 앞부터 저장하게 되면 해당 물건을 여러 번 저장하게 될 수 있어서이다..이렇게 물건을 넣었을 때의 케이스들을 따져본 후, 해당 물건만 들어갔을 때도 저장해준다. 이때도 기존 저장 가치와 비교해서 저장한다.import sysinput=sys..
https://www.acmicpc.net/problem/171441. 미세먼지 확산 - 1-1. 지금 미세먼지 있는 곳 확인 - 스택에 넣어 - 1-2. 스택에 있는 거 다 처리(확산, 계산)하면서 새로 생성은 스택에 넣지 x ** 스택 써야 하는 이유 : 현재 자리의 미세먼지 확산 시 옆에 값들이 확산된건지아닌건지알수가없음... 그래서 스택써야햄.. 2. 공청기 작동 3. 다시 스택에 미세먼지 스팟들 넣음.. t초가 될 때까지 반복 t초 후 양수인 곳들 필터링해서 sumimport sysr,c,t = map(int, input().split())a = [] # r x cairp=[] for y in range(r): # air_purifier -> -1, else -> >0 a.append..
https://www.acmicpc.net/problem/1043testcase.ac에서도 모든 테스트케이스를 통과하고, 질문게시판에 있는 모든 예제들도 다 통과해서 도대체 뭐가 문제인지..왜 3%에서 계속 틀리는 지 고민했던 문제이다.알고 보니, pop_party 함수에서 ppl 리스트 값을 통해 party를 제거할 때, 여기서 거짓말 불가한 사람을 더해주지 않아서 그런 거였다! 거짓말 불가한 사람을 통해 다시 그 사람이 참석한 파티가 거짓말 불가함을 판정할 때, 이렇게 퍼져 나갈 때 거짓말 불가한 사람 리스트(knows)에 제대로 사람을 추가했는 지 확인해보길..import sysfrom collections import defaultdictinput=sys.stdin.readlinen, m = m..
https://www.acmicpc.net/problem/13549import sysfrom collections import dequeinput = sys.stdin.readlinen, k = map(int, input().split())p = [-1 for _ in range(100001)]dq = deque([n])p[n]= 0while dq: x= dq.popleft() if x==k : print(p[k]) break if 0p[x]): p[2*x]=p[x] dq.appendleft(2*x) # 우선 처리 if 0p[x]): p[x-1] = p[x]+1 dq.append(x-1)..
https://www.acmicpc.net/problem/11725 1 - 6 => 1을 통해서 둘 중 부모가 1이란 것을 알 수 있음1. 입력받은 연결을 가지고 인접 행렬 만듦 2. 1부터 차례대로 트리 연결하며, 배열에 부모 저장 3. 저장한 배열 출력1 - 6 - 3 - 5 - 4 - 2 - 7 이렇게 자식이 하나 이상인 경우가 있기 때문에, 인접 행렬에서 부모를 뺀 후 iter의 형태로 자식들을 모두 스택에 넣어야 한다.import sysfrom collections import defaultdictinput=sys.stdin.readlineadj = defaultdict(list)n = int(input())parent = [0 for _ in range(n+1)]for _ in..
https://www.acmicpc.net/problem/1987BFS 로 처리 어려움➡️왜냐하면 지금까지 지나왔던 알파벳을 누적 저장해야 함따라서 Backtracking으로 처리하되, 길을 더 갈 수 없다면 지금까지 경로 길이를 이전에 저장해둔 최장의 길이와 비교하여 더 길 경우 갱신알파벳의 경우 갯수가 정해져 있으므로 boolean 타입의 길이 26인 배열 사용하여 지금까지 지나 온 알파벳 체크 그러나 dfs로 모든 루트 검사할 경우, 반복적으로 같은 지점 들릴 수 있음 => DP 사용하여 반복 계산 줄이기import sysfrom collections import dequeinput = sys.stdin.readliner, c = map(int, input().split())board = [inpu..
https://www.acmicpc.net/problem/15666import sysinput= sys.stdin.readlinen,m = map(int, input().split())num = sorted(set(map(int, input().split())))arr=[]def dfs(start, depth): if depth==m: print(*arr) return for i in range(start, len(num)): arr.append(num[i]) dfs(i, depth+1) arr.pop()dfs(0,0)
https://www.acmicpc.net/problem/2161deque를 사용해 맨 앞과 뒤에서 pop, push 일어나는 것 사용!from collections import dequeimport sysn = int(sys.stdin.readline())cards = deque(i for i in range(1, n+1))while cards: print(cards.popleft(), end=" ") if cards : cards.append(cards.popleft())
https://www.acmicpc.net/problem/15649백트래킹 기법을 통해 출력import sysinput = sys.stdin.readlinen, m = map(int, input().split())check = [False] * (n+1)num = []def dfs(left): # 남은 개수가 0이면 지금까지 쌓은 조합/순열을 출력 if left == 0: print(*num) return for i in range(1, n+1): if not check[i]: check[i] = True # i를 선택했으니 표시 num.append(i) # 경로에 추가 ..
https://www.acmicpc.net/problem/3085문제에 제대로 나와 있지 않아 처음에 조금 고민했는데,알고 보니 딱 하나를 옆의 것과 바꿨을 때를 고려하는 것이다.즉, 현재 사탕과 다른 바로 옆/아래의 사탕을 바꿨을 때의 연속된 같은 사탕 개수 중 최대 값을 구하면 된다.그냥 브루트포스 문제이다.import sysinput = sys.stdin.readlinemaxcnt=0n = int(input())board=[]for _ in range(n): board.append(list(input().rstrip()))def checkarr(board, x): global maxcnt secnt=1 for j in range(1,n): if board[j-1][..
