728x90 반응형 알고리즘109 [백준] 10026번: 적록색약 - python https://www.acmicpc.net/problem/10026 약간 귀찮은 BFS문제visted를 두고 방문안했으면 --> 방문처리 R G 를 같게 두고 다시visted 초기화 후 방문안했으면 --> 방문처리 답 출력을 진행한다.from collections import dequeimport sysarr = []dx = [-1, 0 , 1, 0]dy = [0, 1, 0 , -1]n = int(input())visited = [[False] * n for _ in range(n)]for _ in range(n): k = list(input()) arr.append(k)dq = deque()cnt1 = 0for i in range(n): for j in range(n): i.. 2024. 5. 7. [백준] 2252번: 줄 세우기 - python https://www.acmicpc.net/problem/2252 DAG 위상정렬을 이용한 문제 degree에 차수를 저장하고, 0인 차수를 큐에 넣음으로써 시작된다. 그 후 큐를 뽑아내며 그와 연결된 그래프의 차수를 감소하며 0일 경우에 큐에 삽입하여 큐가 빌때까지 이 작업을 반복한다. 처음에 인접행렬로 구현했으나 메모리초과로 인접리스트로 구현하니 메모리문제가 해결되었다.from collections import dequeimport sysinput = sys.stdin.readlinen, m = map(int, input().split())degree = [0] * (n+1)arr = [[] for _ in range(n+1)]dq = deque()for _ in range(m): a, b = .. 2024. 5. 7. [백준] 1182번: 부분수열의 합 - python https://www.acmicpc.net/problem/1182 부분수열은 상태트리로 1 0 으로 뻗어나가면 풀기 편리하다. 처음에 계속 예제문제가 2가 나와서 아이러니해서 고민을 했는데 문제를 잘 읽어보니 크기가 양수라는 조건이 있어서 공집합을 제외시켜줘야 답이 출력되는 형태였다. 그래서 DFS변수를 L 깊이, sum 합, k 부분집합의 개수 로 설정하고 양수가 아니면 cnt를 증가시켜주지 않는 조건을 추가하여 답을 출력하게 만들었다. n, s = map(int, input().split())arr = list(map(int, input().split()))cnt = 0def DFS(L, sum, k): global cnt if L == n: if s == sum and k!=.. 2024. 5. 6. [백준] 15486번: 퇴사 2 - python https://www.acmicpc.net/problem/15486 아까 푼 퇴사 1하고 뭐가 다른지 잘 모르겠는 문제 T, P에 값을 저장한 뒤, 뒤에서부터 값이 딱 퇴사일과 같을 경우에만 dp에 값을 저장하면서 저장시에는 전 날, T전 날 + P 가격과 비교하면서 값을 저장해준다. 만약 값이 퇴사일을 넘을시에는 전에 있던 값을 그대로 옮기면서 첫날까지 오면 첫날에 최대값이 나오게 된다.n = int(input())T = []P = []dp = [0] * (n+1)for _ in range(n): a, b = map(int, input().split()) T.append(a) P.append(b)for i in range(n-1, -1 , -1): if i+T[i] 완성 2024. 5. 6. 이전 1 ··· 4 5 6 7 8 9 10 ··· 28 다음 728x90 반응형
