본문 바로가기

Algorithm705

[구현/수학] 백준 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.
[탐색/DFS] 백준 11725 트리의 부모 찾기 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 문제 풀이 주어진 트리의 루트를 1이라고 했을 때, 각 노드의 부모를 구해야 합니다. 예제 입력 1번을 살펴보겠습니다. 트리의 루트를 1번으로 했을 때, 정렬하면 오른쪽과 같습니다. 사실 보기 좋게 만들기 위해서 오른쪽으로 정렬해둔 것이지, 컴퓨터 입장에서는 둘 다 같습니다. 2022.02.23 - [Algorithm] - [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 DFS는 인접.. 2022. 5. 3.

티스토리툴바