백준 문제 풀이 (12) 썸네일형 리스트형 [백준] 1202 "보석 도둑" -python 알고리즘 가방 무게를 오름차순으로 정렬하면서 차례대로 순회하고 이때 가방 무게보다 작은 w를 가진 보석을 모두 최대힙에 넣어둔 뒤 각 차례마다 최대힙에서 pop연산을 수행하면 그리디하게 각 단계에서의 최선의 경우를 뽑을 수 있다. 핵심은 힙에 들어가 있는 보석들은 다음 순회때도 무조건 포함될 수 있기 때문에 수행 가능한 알고리즘이다. 소스코드 # 보석 도둑 import heapq import sys n, k = map(int, sys.stdin.readline().split()) items = [] for _ in range(n): w, v = map(int, sys.stdin.readline().split()) items.append([w, v]) bags = [] for _ in range(k): b.. [백준] 1926 "그림" -python 알고리즘 BFS를 통해 그래프를 탐색하면서 시작지점의 개수와 bfs를 통해 방문한 개수를 각각 저장하여 출력한다. 소스코드 # 그림 import sys n, m = map(int, sys.stdin.readline().split()) arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)] cnt = 0 result = 0 visited = [[0 for i in range(m)] for j in range(n)] q = [] dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] for i in range(n): for j in range(m): if visited[i][j] or arr[i][j] == 0: contin.. [백준] 1744 "수 묶기" -python 알고리즘 무작위로 나열된 수열로 해결하기에는 답이 없다고 판단하여 정렬한 상태에서 규칙을 찾았다. 오름차순 정렬 이후 음수와 양수가 나뉘는 부분을 생각해보았고 음수가 짝수개인 동안은 왼쪽부터 2개씩 묶고(덱에서 왼쪽 2개씩 뺌), 오른쪽에서는 1보다 큰 수가 짝수개인 동안은 2개씩 묶는다(덱에서 오른쪽 2개씩 뺌), 길이가 2이상인 경우까지 위 과정을 반복한다. 주의할 점은 왼쪽, 오른쪽 둘 다 홀수개가 남았다면 브레이크를 통해 반복을 빠져나온다. 그 다음 덱에 남은 개수에 대해 음수, 0이 같이 있으면 둘을 곱해주는 예외처리를 한 뒤에 나머지 상황은 전부 더해주면 최대가 된다. 소스코드 # 수 묶기 import collections n = int(input()) arr = [] for _ in rang.. [백준] 7490 "0 만들기" -python 알고리즘 N개의 숫자에 대해 N-1번 연산을 수행하면서 각 연산에서는 공백, 덧셈, 뺄셈을 수행 가능하므로 재귀를 통해 연산자를 넘겨주면서 빽트래킹 알고리즘을 이용한다. 3^(N-1) 만큼의 시간이 걸리지만 N의 최대값 자체가 9이므로 백트래킹을 통해 효율적으로 구현 가능하다. 또한, 수식 연산시 파이썬의 내장함수인 eval()을 이용하였다. eval()함수는 파라미터로 수식을 str타입으로 전달해주게 되면 계산해주는 착한 친구이다. 소스코드 # 0 만들기 n = int(input()) def func(k, r: str, N): #반복, 수식, 값 if k == N+1: result = eval(r.replace(" ", "")) if result == 0: print(r) return func(k+1,.. [백준] 10997 "별찍기 - 22" 재귀 -python 알고리즘 재귀호출을 통해 별을 찍는다. 가로 4n-3, 세로4n-1인 2차원 배열을 생성한 뒤 함수를 통해 찍어준다. 주의 할 점은 base conditon은 N=1일때 이고 각 호출마다 함수가 실행하고 넘길 모양은 첫행, 첫열, 마지막행, 마지막 열(y축이 1인경우 제외) 하고 가운데 r자 모양이다. 소스코드 # 별 찍기 - 22 n = int(input()) stars = [[" " for i in range(4*n-3)] for j in range(4*n -1)] #배열초기화 def fill(N, x, y): if N == 1: #기저 조건 stars[x][y] = "*" return l1 = 4*N-1 l2 = 4*N-3 #열찍기 for i in range(l1): stars[x+i][y] = ".. [백준] 1182 "부분수열의 합" 백트래킹 -python 알고리즘 공집합을 제외한 2^n - 1개의 부분집합에 대해 모두 탐색을 실시한다. 이때 부분집합의 개수는 원소를 포함시킬것인가 아닌가 2가지로 나뉘어 2^n개임을 생각해보면 빽트래킹을 통해 쉽게 구할 수 있다고 생각하였다. 소스코드 # 부분수열의 합 import sys n, s = map(int, sys.stdin.readline().split()) arr = list(map(int, sys.stdin.readline().split())) result = 0 if s == 0: # s = 0 인경우 공집합을 제외 result = -1 def func(idx, S): global result if idx > n-1: if S == s: result += 1 return func(idx + 1, S + ar.. [백준] 1874 "스택 수열" -python 알고리즘 1부터 n까지 순회하면서 입력 값과 일치하는경우 push, 일치하지 않는 경우 pop을 실행하고 실행 연산의 결과를 배열에 저장한다. 소스코드 # 스택 수열 import sys n = int(sys.stdin.readline()) arr = [int(sys.stdin.readline()) for _ in range(n)] idx = 0 stack1 = [] stack2 = [] cal = [] for i in range(1, n+1): stack1.append(i) cal.append('+') while stack1 and stack1[-1] == arr[idx]: stack2.append(stack1.pop()) cal.append('-') idx += 1 if stack2 == arr: fo.. [백준] 11054 "가장 긴 증가하는 부분 수열" -python 알고리즘 다이나믹 프로그래밍 기법을 통해 i번째 요소를 포함하여 최대길이인 지점을 저장한 뒤 dp중 최댓값을 출력한다. 또한, 최소 길이는 1이므로 dp의 값을 1로 초기화한다. 소스코드 # 가장 긴 증가하는 부분 수열 import sys n = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().split())) dp = [0] + [1] * n for i in range(1, n+1): for j in range(1, i): if arr[j-1] < arr[i-1]: dp[i] = max(dp[i], 1 + dp[j]) # i번째 요소까지 최대 길이 print(max(dp)) 느낀점 dp를 무작정 0으로 초기화했고 맨 뒤에 값을 출력.. 이전 1 2 다음
