kiteday 님의 블로그

https://school.programmers.co.kr/learn/courses/30/lessons/150367 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 이진수, 이진트리 탐색 문제이다. 문제를 푸는 방법은 1. 이진수 변환2. 탐색이 가능하도록 2**n +1이 될 때까지 앞에 0을 추가한다.3. 탐색 - 루트 노드가 더미노드이면 (0이면) 자식노드는 모두 0이어야 한다.- 위 조건을 모두 통과하면 가능 아니면 불가능- 루트를 기준으로 left와 right로 나누어 생각할 것.def check_tree(tree): if len(tree) == 1: return True r..

https://www.acmicpc.net/problem/2293DP문제이다.가방 물건 넣기와 다른 점은 동전은 여러 개 사용할 수 있다는 것. import sysn, k = map(int, sys.stdin.readline().split())coins = [int(sys.stdin.readline()) for _ in range(n)]dp = [0]*(k+1)dp[0] = 1coins.sort()for i in range(n): for j in range(coins[i], k+1): dp[j] = dp[j]+dp[j-coins[i]] print(dp[k]) 앞선 가방에 물건넣기를 참고해서 풀었더니 처음보다 빨리 완성할 수 있었다. for문 범위지정에 헤매어 정답이 나오지..

https://www.acmicpc.net/problem/12865 DP로 푸는 냅색문제이다.이걸 recursive 방식으로는 풀어봤는데 그 방식은 시간초과 or 메모리초과가 났다. (당연함)예전에 풀었다가 실패했던 것 재도전한 문제인데도 이번 주에 푼 것 중에 가장 어려웠다. import sysN, K = map(int, sys.stdin.readline().split())things = [list(map (int, sys.stdin.readline().split())) for _ in range(N)]bag = [0]*(K+1)for w, v in things: for k in range(K, w-1, -1): bag[k] = max(bag[k], ..

https://www.acmicpc.net/problem/13023 DFS, 백트레킹 문제이다.처음에 문제 자체를 잘못 이해하고 중간에 치명적인 실수한 부분이 몇군데 있었다. import sysdef dfs(num, count): global link, visited, n, found if count == 4: found = True return visited[num] = True for l in link[num]: if visited[l] == False: dfs(l, count + 1) visited[num] = False n, m = map(int, sys.stdin.readline().split..

https://www.acmicpc.net/problem/2573 DFS/ BFS + 네 방향 검사 문제이다. import sysfrom collections import dequedx = [-1, 1, 0, 0]dy = [0, 0, 1, -1]def bfs(x, y): queue = deque([(x, y)]) global matrix, visited while queue: x, y = queue.popleft() ice[x][y] = 0 for idx in range(4): nx = x+dx[idx] ny = y+dy[idx] if 0 0 and not visited..

https://www.acmicpc.net/problem/7569 import sysfrom collections import dequedx = [1, -1, 0, 0, 0, 0]dy = [0, 0, 1, -1, 0, 0]dz = [0, 0, 0, 0, 1, -1]M, N, H = map(int, sys.stdin.readline().split())box = [[list(map(int, sys.stdin.readline().split())) for _ in range(N)] for _ in range(H)]visited = [[[False]*M for _ in range(N)] for _ in range(H)]queue = deque()for x in range(H): for y in range(N..

https://www.acmicpc.net/problem/2812 그리디, 스택 문제주어진 수에서 k만큼을 제외하고 가장 큰 수를 반환하는 문제이다. 사실 이 문제는 보자마다 백트레킹밖에 생각이 안났다..그래서 시간복잡도 때문에 통과는 안되지만, 반례 100개는 모두 통과한 백트레킹 코드도 함께 첨부한다.import sysn, k = map(int, sys.stdin.readline().split())nums = str(sys.stdin.readline())size = n-kstack = []for num in nums: while k > 0 and stack and stack[-1] stack에 수를 넣고 만약 stack의 맨 위에 있는 수와 현재 수를 비교했을 때 현재 수가 크다면 stack에 ..

https://www.acmicpc.net/problem/1202 여러 개의 가방과 보석을 담아 최대값을 만드는 그리디 문제이다.import sysimport heapqn, k = map(int, sys.stdin.readline().split())jew = []for _ in range(n): jew.append(list(map(int, sys.stdin.readline().split()))) jew.sort(key=lambda x : (x[0], x[1]))# print(jew)bag = []for _ in range(k): bag.append(int(sys.stdin.readline()))bag.sort()price = 0idx = 0temp = []for b in bag: w..

https://www.acmicpc.net/problem/21921 슬라이딩 윈도우 문제이다.정해진 크기 X만큼 윈도우를 설정하고 하나씩 이동해가며 최고합 값과 수를 찾는다. N, X = map(int, input().split())num = list(map(int, input().split()))start = 0end = X-1max_sum = sum(num[:X])count = 1new_sum = max_sumwhile True: start += 1 end +=1 if end>=N: break new_sum = new_sum - num[start-1] +num[end] if new_sum > max_sum: max_sum = new_sum ..

https://www.acmicpc.net/problem/1644 소수찾기 + 투포인터 문제이다.소수찾기는 에라스테네스의 체로 먼저 찾는다. 에라스테네스의 체는 간단하게 설명하면 소수를 찾으면 소수의 배수는 모두 소수가 아님을 판정하는 것이다.예를 들어- 2은 소수이므로 2의 배수는 모두 소수가 아니다.- 3은 소수이므로 3의 배수는 모두 소수가 아니다.- 5는 소수이므로 5의 배수는 모두 소수가 아니다.... 이 문제에서는 N보다 작은 수로 연속된 합을 구하는 것이므로 N까지의 소수를 구해주면 된다. # 소수의 연속합 # 소수는 에라스토스네스의 체를 이용해 구하고 합은 투포인터N = int(input())nums = []is_prime = [True]*(N+1)is_prime[0] = Falseis_p..