[백준 알고리즘] - 행렬 제곱 (10830) with Python

📎 간략한 문제 정리 N by N 행렬 A가 주어질 때, A의 B제곱을 구하는 프로그램을 작성하는 문제입니다. 📈 문제 분석 곱셈 연산을 거듭제곱하는 문제이므로 백준 알고리즘의 곱셈(1629번) 풀이 를 참고할 필요가 있습니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 분할 정복을 활용합니다. 💻 풀이한 코드 from sys import stdin input = stdin.readline a, b = map(int, input().split()) matrix = [list(map(lambda x: x % 1000, map(int, input().split()))) for _ in range(a)] def power(m, y): if y == 1: return m partial = power(m, y // 2..
알고리즘 학습/백준 알고리즘 2021. 4. 17. 23:01
[백준 알고리즘] - 곱셈 (1629번) with Python

📎 간략한 문제 정리 자연수 A를 B번 곱한 수를 계산합니다. 즉, A의 B제곱을 계산하는데 그 결과를 C로 나눈 나머지를 출력합니다. 📈 문제 분석 A, B, C는 2,147,483,647 이하의 자연수입니다. 2,147,483,647(8번째 메르센 소수)는 2^31 - 1로 C언어 기준 정수자료형 최대치입니다(양의 정수 기준). 🙋‍♂️ 내가 처음 생각한 해결 방법 오버플로우 문제가 없다고 해도 A^B 연산이 끝난 뒤 C로 나누는 연산을 하면 속도 이슈가 발생할 수 밖에 없습니다. 그래서 각 연산의 중간에 C로 나누는 연산을 하는 구조로 작성해보겠습니다. 단순 반복으로는 연산 속도 이슈가 발생할 수 밖에 없습니다. 문제를 세분화하는 과정이 필요합니다(분할). 💻 풀이한 코드 from sys impor..
알고리즘 학습/백준 알고리즘 2021. 4. 16. 23:46
[백준 알고리즘] - 숫자 카드 2 (10816번) with Python

📎 간략한 문제 정리 개수가 (1 ≤ N ≤ 500,000)인 숫자 배열 N이 주어집니다. 각 숫자의 범위는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같습니다. 그 후 새로운 숫자 배열 M을 입력 받는데, M의 숫자들이 N의 배열에서 몇번 나오는지 출력하는 문제입니다. 📈 문제 분석 문제 카테고리는 이분탐색입니다. 배열 N의 정보를 어떻게 처리할지가 중요합니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 Counterdict를 활용해서 배열 N을 정리하면 O(N)으로 처리 가능할 것 같습니다. 💻 풀이한 코드 from sys import stdin from collections import Counter input = stdin.readline N = int(input()) N_d..
알고리즘 학습/백준 알고리즘 2021. 4. 15. 23:30
[백준 알고리즘] - 행렬 곱셈 (2740번) with Python

📎 간략한 문제 정리 분할 정복의 문제로 두개의 행렬이 주어지고 행렬 곱셈의 결과를 출력하는 문제입니다. 📈 문제 분석 분할 정복으로 행렬 곱셈은 각 위치 요소의 곱의 합이기 때문에 요소들을 순회하며 곱과 합 연산을 반복하면 됩니다. 사실 분할 정복 문제라고 하기엔 행렬곱의 정의를 알고 있으면 그대로 구현하는 문제이므로 시뮬레이션 문제에 가깝습니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 단순히 행렬곱의 정의대로 구현하면 되고, 포인트는 코드를 조금 더 간결하게 표현할 방법으로 잡았습니다. 💻 풀이한 코드 from sys import stdin input = stdin.readline AN, AM = map(int, input().split()) A = [list(map(int, input().split(..
알고리즘 학습/백준 알고리즘 2021. 4. 14. 23:06
[백준 알고리즘] - AC (5430번) with Python

📎 간략한 문제 정리 새로운 언어에는 두가지 함수 R(뒤집기), D(버리기)가 있습니다. R은 숫자의 순서를 뒤집는 함수이고 D는 첫번째 숫자를 버리는 함수입니다. 배열이 비어있을 때 D를 사용하면 에러가 발생합니다. 배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하는 문제입니다. 📈 문제 분석 함수 명령문을 순회하며 해당 함수를 적용할 수 있습니다. 문제는 R함수는 O(N)인데 이렇게 되면 O(N^2)로 100,000의 범위에서 100억으로 속도 이슈가 발생합니다. 단순히 반복문을 사용하면 문제가 발생합니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 우선 명령문에 RR이 연속으로 존재한다면 제거해줄 수 있습니다. 그리고 D의 개수가 전체 숫자의 개수보다 많다면 error가 ..
알고리즘 학습/백준 알고리즘 2021. 4. 13. 22:42
[백준 알고리즘] - 주유소 (13305번) with Python

📎 간략한 문제 정리 각 지역은 주유소를 가지고 있고, 주유소마다 기름의 가격은 다릅니다. 위의 그림에서는 각 지역마다 기름 가격이 5, 2, 4, 1원이고 지역간 이동시 필요간 기름의 양이 2, 3, 1 리터입니다. 왼쪽 시작점에서 오른쪽 도착점까지 이동하는데 필요한 기름의 최소 비용을 구하는 문제입니다. 📈 문제 분석 기름통의 크기가 한정되어있다면 조금 어려운 문제일 수 있겠지만 각 지역에서 기름을 무제한으로 구매 가능하므로 구매 조건만 생각하면 될 문제입니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 시작점에서 다음 지역의 기름값을 보고 만약 현재 위치 가격이 더 높다면 다음 지역 이동까지 필요한 만큼의 기름만 구매하고 넘어갑니다. 하지만 지금 지역의 기름가격이 더 낮다면 다다음 지역까지 거리만큼 기름..
알고리즘 학습/백준 알고리즘 2021. 4. 10. 21:27
[백준 알고리즘] - 전깃줄 (2565번) with Python

📎 간략한 문제 정리 두개의 전봇대에 숫자가 매겨져 있습니다. 예를 들어 아래와 같이 전깃줄이 연결되어 있습니다. 위에서 1-8 연결선과 3-9 연결선, 4-1 연결선 만 제거하면 겹치는 선이 없어집니다. 이렇게 겹치지 않기 위해 제거해야하는 최소 전깃줄의 수를 출력하는 문제입니다. 📈 문제 분석 주어진 전깃줄 연결 상태를 리스트로 표현해보겠습니다. [(1, 8), (2, 2), (3, 9), (4, 1), (6, 4), (7, 6), (9, 7), (10, 10)] 위에서 보면 없애야할 전깃줄을 제거하고 보면 튜플의 1번 인덱스 요소가 오름차순으로 정렬되어 있는 것으로 볼 수 있습니다. [(2, 2), (6, 4), (7, 6), (9, 7), (10, 10)] 🙋‍♂️ 내가 처음 생각한 해결 방법 L..
알고리즘 학습/백준 알고리즘 2021. 4. 9. 10:09
[백준 알고리즘] - 신나는 함수 실행 (9184번) with Python

📎 간략한 문제 정리 주어진 재귀 함수가 속도 이슈 없이 작동하도록 만듭니다. if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 📈 문제 분석 전형적인 DP 문제인 피보나치와 유사한 형식입니다. 단순 반복이 아니라 결과를 저장하면서 꺼내오는 구조로 작성해야 합니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 pseudo code에 나온 그대로 구현하지만 결과를 ..
알고리즘 학습/백준 알고리즘 2021. 4. 6. 21:25
1 2 3 4 5 ··· 8