본문 바로가기

알고리즘

 (138)
[BOJ] [Python] 5568번 : 카드 놓기 N개의 카드 중에서 K장을 선택한다. K장을 나열해서 만들 수 있는 정수는 모두 몇 가지인지 구하는 문제이다. n = int(input()) k = int(input()) card = [] dp = [0] * n result = 0 for _ in range(n): card.append(int(input())) string = '' result = set() def select(cnt): global string if cnt == k: result.add(string) return for i in range(n): if dp[i] == 0: dp[i] = 1 tmp = str(card[i]) string += tmp select(cnt + 1) dp[i] = 0 string = string[:-len(t..
[BOJ] [Python] 2422번 : 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 문제를 요약해보자. 아이스크림 종류의 개수 : N개 섞으면 안되는 조합의 개수 : M개 섞으면 안되는 조합을 피해서, 3가지를 선택하면 된다. import sys from collections import deque input = sys.stdin.readline n, m = map(int, input().split()) dp = [0] * (n + 1) dic = [[] for _ in range(n + 1)] li = deque([]) result = 0 for _ in range(m): a, b = map(int, input().split()) dic[a].append(b) dic[b].append(a) def Ice_Cream(cnt): global result if cnt == 3: for da..
[BOJ] [Python] 15686번 : 치킨 배달 문제를 정리해보자. 도시 : N x N 빈칸 : 0 집 : 1 치킨집 : 2 도시의 칸 : (r, c) (각각 1부터 시작한다.) 치킨 거리 : 집과 가장 가까운 치킨집 사이의 거리 도시의 치킨 거리 : 모든 집의 치킨 거리의 합 거리 계산 : | r1 - r2 | + | c1 - c2| 가장 수익을 많이 낼 수 있는 치킨집의 개수, 최대 M개를 이용하여 도시의 치킨 거리의 최솟값을 출력하면 되는 문제이다. 먼저, 최대 M개를 선택해야 하는 점에 주목하자. 치킨집은 M개를 제외하고는 모두 폐업시킬 것이다. 완전탐색으로 생각하자면, 치킨집이 M개되는 모든 경우의 수를 따져주면 된다. n, m = map(int, input().split()) chicken = [] house = [] dp = [[0] * ..
[BOJ] [Python] 14502번 : 연구소 문제를 정리해보자. 연구소 : N x M 빈칸 : 0 ( 3개 이상 ) 벽 : 1 바이러스 : 2 ( 2개 이상, 10개 이하 ) 세울 수 있는 벽의 수 : 3개 (꼭 3개를 세워야 한다.) 벽을 3개 세운 뒤, 안전 영역의 크기의 최댓값을 구하는 문제이다. 바이러스는 bfs로 퍼트려주면 된다. 그 전에, 벽은 어떻게 세워야 할까? 벽을 세울 수 있는 모든 경우의 수를 탐색하면 된다. 먼저 bfs를 제외한 make_wall 코드를 보자. 재귀 함수를 이용해서 모든 경우의 수를 볼 것이다. 벽의 개수는 count 개수이고, 3개가 될 때까지 만들어준다. import sys from collections import deque input = sys.stdin.readline s = [] dx = [0, 0,..
[BOJ] [Python] 2960번 : 에라토스테네스의 체 소수의 배를 제거하면서 k번째를 찾으면 된다. dp 리스트로 중복방지를 하며, K번째를 찾을 수 있게 카운트해 줬다. 예를 들어, 6은 2의 3의 공통배수이다. 따라서 중복제거를 피해야 한다. import sys, math input = sys.stdin.readline n, k = map(int, input().split()) sosu = [] for num in range(2, n + 1): check = True for i in range(2, int(math.sqrt(num)) + 1): if num % i == 0: check = False break if check: sosu.append(num) def main(): cnt = 0 dp = [0] * (n + 1) for num in sosu..
[BOJ] [Python] 1935번 : 후위 표기식2 전형적인 스택 문제가 아닐까? ABC*+DE/-을 예로 살펴보자. 앞에서부터 하나씩 값을 넣다가, 연산자가 들어오면 연산을 한다. [1, 2, 3] [1, 6] [7] [7, 4, 5] [7, 0.8] [6.2] pop을 이용해서 2개의 원소를 뽑고, push[append]를 이용해서 연산 결과를 넣어준다. num = int(input()) string = input() check = ["*", "+", "/", "-"] dic = {} li = [] for s in string: if s in check: first = li.pop() second = li.pop() if s == "+": li.append(second + first) elif s == "-": li.append(second - fir..
[BOJ] [Python] 1158번 : 요세푸스 문제 n, k = map(int, input().split()) li = [num for num in range(1, n + 1)] result = [] for _ in range(n): i = k - 1 length = len(li) - 1 if i < length: result.append(str(li[i])) li = li[i + 1:] + li[:i] elif i == length: result.append(str(li[i])) li = li[:i] else: if not k % len(li): result.append(str(li[-1])) li.pop() else: i = (k % len(li)) - 1 result.append(str(li[i])) li = li[i + 1:] + li[:i] pr..
[BOJ] [Python] 7568번 : 덩치 모든 사람의 덩치 등수는 1에서 시작한다. 다른 사람보다 몸무게와 키의 값이 모두 작다면 둥수에 +1을 해준다. 이 문제는 N의 크기가 작기 때문에, 2중 반복문을 돌려된다. num = int(input()) kg_li = [] cm_li = [] result = [1] * num for _ in range(num): kg, cm = map(int, input().split()) kg_li.append(kg) cm_li.append(cm) for i in range(num): for j in range(num): if kg_li[i] < kg_li[j] and cm_li[i] < cm_li[j]: result[i] += 1 print(*result)
[BOJ] [Python] 11047번 : 동전 0 먼저, 동전 N종류를 내림차순으로 정렬해 리스트에 저장한다. 리스트 0번째부터 n-1번째까지 k원을 리스트의 각 값으로 나눈다. 각 나누는 과정이 끝날 때마다 나머지 값으로 K원을 갱신한다. K원보다 리스트의 값이 크다면, K원은 변하지 않을 것이다. 이는 동전을 사용하지 않았다는 뜻이 된다. 따라서, K원보다 작거나 같을 때를 따로 체크해서 동전을 사용했음을 확인해야 한다. num = list(map(int, input().split())) kind = num[0] target = num[1] wallet = [] for _ in range(kind): wallet.append(int(input())) wallet.reverse() result = 0 for coin in wallet: if coin
[BOJ] [Python] 11055번 : 가장 큰 증가 부분 수열 [1, 100, 2, 50, 60, 3, 5, 6, 7, 8]를 예로 이해하고 해결해보자. dp에는 자기 자신의 값이 초깃값으로 들어가 있다. 이제 0번째부터 9번째까지 하나씩 확인하며, dp를 늘려줄 것이다. 규칙은 아래와 같다. n번째) 0번째부터 n-1번째까지 돌면서, 1. n번째 수보다 작은 값을 찾는다. 2. 작은 값들이 가진 dp중 최대의 dp를 n번째 dp에 더해준다. 예를 들어, 지금 4번째라고 한다면 50보다 작은 값은 1과 2이다. 1보다 2의 dp값이 더 크므로, 2의 dp값에 50을 더해준다. 더해진 값은 50의 dp값이 된다. 마지막에 dp 리스트의 최댓값을 출력하면, 가장 큰 증가 부분 수열의 합을 찾을 수 있다. num = int(input()) li = list(map(int..

티스토리툴바