본문 바로가기

백준 알고리즘89

백준 - 7795번 먹을 것인가 먹힐 것인가 python 문제풀이 [Hellfer] 🔷 알고리즘 분류 - 정렬, 두 포인터,  난이도 - 실버 3 문제 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.   두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다. 둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기.. 2024. 7. 2.
백준 - 1940번 주몽 python 문제풀이 [Hellfer] 🔷 알고리즘 분류 - 정렬, 두 포인터난이도 - 실버 4  문제 주몽은 철기 군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기 군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시.. 2024. 7. 1.
백준 - 6463번 팩트 python 문제풀이 [Hellfer] https://www.acmicpc.net/problem/6463문제N!은 "N 팩토리얼"로 읽으며, 처음 N개의 양의 정수를 곱한 값이다. 이때, N은 음이 아닌 정수이어야 한다. 예를 들면 다음과 같다. N       N!  0       1  1       1  2       2  3       6  4      24  5     120 10 3628800N을 입력 받아 0이 아닌 마지막 자리를 구하는 프로그램을 작성하시오. 예를 들어, 5!의 경우에 정답은 2이다. 5! = 120이고, 2는 0이 아닌 마지막 자리이기 때문이다.🔷 알고리즘 분류 - 다이내믹 프로그래밍 난이도 - 실버 5🔶문제 풀이 - 재귀함수를 이용한 풀이def factorial(x): # y를 1로 초기화 y = .. 2024. 5. 16.
백준 - 1110 더하기 사이클 python 문제풀이 [Hellfer] https://www.acmicpc.net/problem/1110 1110번: 더하기 사이클 0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, www.acmicpc.net 🔷 알고리즘 분류 - 수학, 구현 난이도 - 브론즈 1 🔶문제 풀이 - 구현을 이용한 풀이 n = int(input()) # 사용자로부터 정수 입력 받음 result = n # 초기 값으로 입력 받은 수를 저장 count = 0 # 사이클의 길이를 세기 위한 변수 초기화 while True: # 무한 루프 x = n // 10 # 입력 받은 수의 십의 자리 숫자를 구함 y = n %.. 2024. 3. 16.
백준 - 1292 쉽게 푸는 문제 python 문제풀이 [Hellfer] https://www.acmicpc.net/problem/1292 1292번: 쉽게 푸는 문제 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. www.acmicpc.net 🔷 알고리즘 분류 - 수학, 구현 난이도 - 브론즈 1 🔶문제 풀이 - 반복문을 이용한 풀이 n, m = map(int, input().split()) # n과 m을 입력받습니다. x = 0 # 결과를 저장할 변수 x를 초기화합니다. result = [] # 결과를 저장할 리스트 result를 초기화합니다. # 1부터 m까지 반복합니다. for i in range(1, m + 1): # i번째 수를 i번씩 result .. 2024. 3. 10.
백준 - 10844번 쉬운 계단 수 python 문제풀이 [Hellfer] https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 🔷 알고리즘 분류 - 다이내믹 프로그래밍 난이도 - 실버 1 🔶문제 풀이 - 다이내믹 프로그래밍을 이용한 풀이 n = int(input()) # dp[i][j]: 길이가 i이고 마지막 자릿수가 j인 계단 수의 개수 dp = [[0] * 10 for _ in range(n + 1)] # 길이가 1인 계단 수는 모두 1개 for i in range(1, 10): dp[1][i] = 1 # 길이가 2 이상인 계단 수 계산 for i in range(2, n + 1): for j in range(10): if j ==.. 2024. 2. 19.
백준 - 11725번 트리의 부모 찾기 python 문제풀이 [Hellfer] https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 🔷 알고리즘 분류 - 그래프 이론, 트리, 너비 우선 탐색 난이도 - 실버 2 트리는 계층적인 구조를 가지는 비선형 자료구조로, 노드(node)와 노드를 연결하는 간선(edge)으로 구성됩니다. 트리는 루트 노드(root node), 부모 노드(parent node), 자식 노드(child node), 잎 노드(leaf node, 터미널 노드) 등으로 구성되며, 특정 노드의 하위 트리(sub-tree)를 구성하는 노드들은 해당 노드의 자손(descendant).. 2024. 2. 7.
백준 - 1238번 파티 python 문제풀이 [Hellfer] https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 🔷 알고리즘 분류 - 그래프 이론, 데이스크트라, 최단경로 난이도 - 골드 3 다익스트라 알고리즘이란 특정한 시작 노드에서 출발하여 그래프 상의 모든 다른 노드로 가는 최단 경로를 찾는 알고리즘입니다. 음의 간선이 없는 경우에만 사용할 수 있습니다. 다익스트라 알고리즘은 '탐욕적인 방법'을 사용합니다. 매번 '가장 비용이 적게 드는 노드'를 선택해서 반복함으로써 최적.. 2024. 1. 31.
백준 - 1359번 복권 python 문제풀이 [Hellfer] https://www.acmicpc.net/problem/1359 1359번: 복권 첫째 줄에 세 정수 N, M, K가 주어진다. www.acmicpc.net 🔷 알고리즘 분류 - 수학, 브루트포스 알고리즘, 조합론 확률론 난이도 - 실버 4 🔶문제 풀이 - 확률론을 이용한 풀이 import math def combination(n, r): # 조합을 계산하는 함수 if n < r: # nCr에서 r이 n보다 크면 조합은 0 return 0 return math.factorial(n) / (math.factorial(r) * math.factorial(n-r)) # nCr = n! / (r!(n-r)!) n, m, k = map(int, input().split()) # n, m, k 입력 받기 x = .. 2024. 1. 29.
백준 - 1268번 임시 반장 정하기 python 문제풀이 [Hellfer] https://www.acmicpc.net/problem/1268 1268번: 임시 반장 정하기 오민식 선생님은 올해 형택초등학교 6학년 1반 담임을 맡게 되었다. 오민식 선생님은 우선 임시로 반장을 정하고 학생들이 서로 친숙해진 후에 정식으로 선거를 통해 반장을 선출하려고 한다. www.acmicpc.net 🔷 알고리즘 분류 - 구현 난이도 - 브론즈 1 🔶문제 풀이 - 구현을 이용한 풀이 # 입력 받을 테스트 케이스의 수 T를 입력받습니다. T=int(input()) # T만큼의 2차원 배열 x를 입력받습니다. x=[list(map(int,input().split())) for _ in range(T)] # T만큼의 세트 형태의 1차원 배열 y를 생성합니다. y=[set() for _ in range.. 2024. 1. 27.

티스토리툴바