본문 바로가기

Algorithm706

[구현/수학] 백준 1434 책 정리 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1434번: 책 정리 첫째 줄에 박스의 개수 N, 책의 개수 M이 주어진다. 둘째 줄에는 박스의 용량 A1, A2, ..., AN이 주어지고, 셋째 줄에는 B1, B2, ..., BM이 주어진다. www.acmicpc.net 2. 문제 풀이 1. 현재 책이 현재 박스에 들어가지 않으면, 3번으로 간다. 아니면 2번으로 간다. 2. 현재 책을 현재 박스에 넣는다. 다음 책을 손에 집고 1번으로 간다. 3. 현재 박스를 다른 쪽으로 치운 다음에, 테이프로 못 열게 봉인한다. 다음 박스를 앞으로 가져오고 1번으로 간다. 책을 박스에 보관할 때, 낭비되는 박스 용량을 구하는 문제입니다. 다국어 문제라서 번역이 조금 어색합니다. 위 로직을 조금 쉽게 풀어쓰면 아래와.. 2022. 5. 12.
[구현/수학] 백준 2740 행렬 곱셈 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 2. 문제 풀이 두 행렬의 곱을 구하는 문제입니다. 크기가 N*M인 A행렬과 크기가 M*K인 B행렬의 곱은 N*K입니다. 행렬의 곱은 A행렬의 열과 B행렬의 행이 같아야만 할 수 있고, 문제에서는 M이 고정이므로 이 점은 고려하지 않아도 됩니다. for i in range(N): for j in range(K): for z in range(M): # c11 = a11*b11 + a12*b21 re.. 2022. 5. 11.
[분할정복/DQ] 백준 10830 행렬 제곱 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 문제 풀이 행렬 A의 B 거듭제곱을 구하는 문제입니다. 행렬의 곱셈은 위와 같이 행과 열의 곱으로 이루어집니다. 반복문으로 구현하려면 무려 3중 for문을 써야 합니다. (O(n^3)) 따라서 계속 A를 곱하는 방법으로는 당연히 시간초과가 납니다. 2022.05.08 - [Algorithm] - [분할정복/재귀] 백준 1629 곱셉 - 파이썬(Python) 그 대신 A^B제곱을 A가 될 때까지 둘로 나눈다음, 다시 곱해주면 .. 2022. 5. 10.
[동적계획법/DP] 백준 12865 평범한 배낭 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 2. 문제 풀이 제한된 배낭 용량에 최대한 가치있는 물건들을 채우는 문제입니다. 2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP) [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP) [ Contents ] 1. 동적 프로그래밍(Dynamic Programmin.. 2022. 5. 9.
[분할정복/재귀] 백준 1629 곱셈 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 2. 문제 풀이 효율적으로 거듭제곱을 구하는 문제입니다. 단순히 A**B를 하면 시간 초과가 납니다. 2022.01.29 - [Algorithm] - [Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘 [Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘 각개격파(各個擊破): 적을 하나하나 따로 떼어 무찌름 유독 외세의 침략을 많이 받았던 우리 민족의 대표적인 전술은 '매복'과 '각개격파'였습니다. .. 2022. 5. 8.
[수학/그리디] 백준 14659 한조서열정리하고옴ㅋㅋ - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 14659번: 한조서열정리하고옴ㅋㅋ 첫째 줄에 봉우리의 수 겸 활잡이의 수 N이 주어진다. (1 ≤ N ≤ 30,000) 둘째 줄에 N개 봉우리의 높이가 왼쪽 봉우리부터 순서대로 주어진다. (1 ≤ 높이 ≤ 100,000) 각각 봉우리의 높이는 중복 없이 www.acmicpc.net 2. 문제 풀이 뒤에 자신보다 낮은 봉우리가 있으면 죽일 수 있습니다. 한 사람이 최대 몇 명을 죽일 수 있는지 구해야 합니다. 2022.01.26 - [Algorithm] - [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결 [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결 경주마들을 자세히 보면, 양쪽 시야를 차단하는 안대를 끼.. 2022. 5. 7.
[수학/그리디] 백준 14720 우유 축제 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 14720번: 우유 축제 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후 www.acmicpc.net 2. 문제 풀이 딸기 - 초코 - 바나나 순으로 우유를 먹은 횟수를 구하는 문제입니다. 순서에 맞는 우유가 왔을 때, 먹는 것이 최선이기 때문에 직관적으로 해결할 수 있습니다. 3. 코드 # 입력 N = int(input()) store = list(map(int, input().split())) # 우유 먹방 order = 0 res = 0 # 먹은 우유 갯수 for milk in store: if milk == or.. 2022. 5. 6.
[구현/수학] 백준 11660 구간 합 구하기 5 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 2. 문제 풀이 2차원 행렬의 구간 합을 구하는 문제입니다. 2022.02.14 - [Algorithm] - [구현/수학] 백준 11659 구간 합 구하기 4 - Python [구현/수학] 백준 11659 구간 합 구하기 4 - Python [ Contents ] 1. 문제 (링크 참조) 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M.. 2022. 5. 5.
[탐색/BFS] 백준 16953 A → B - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 2. 문제 풀이 1) A*2 2) A*10 +1 2가지 연산을 최소로 사용해서 A를 B로 만드는 문제입니다. 2022.03.19 - [Algorithm] - [탐색/BFS] 백준 9019 DSLR - 파이썬(Python) BFS 탐색문제로, DSLR 문제와 비슷합니다. B를 넘어서기 전까지 2가지 연산을 수행하다가 B가 되면 탐색을 종료합니다. 만약 모든 경우의 수를 탐색했는 데도 B가 되지 않는다면 -1를 출력합니다. 3. 코드 from collections import deque # 입력 A, B = map(int, input().spl.. 2022. 5. 4.

티스토리툴바