반응형 백준6 [알고리즘] 백준. 행렬 제곱 #10830 백준 단계별로 풀어보기 분할 정복 카테고리의 문제 중 10830번 문제인 '행렬 제곱'문제를 풀어보았습니다. 문제 크기가 N*N인 행렬A의 B제곱을 구하는 코드를 작성하라. 이때 $A^{B}$의 원소를 1000으로 나눈 나머지를 출력한다. 첫째 줄에 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000) 둘째 줄부터 N개의 줄과 N개의 행렬이 주어진다. #예시 2 5 1 2 3 4 로 주어지면 2 x 2 행렬 A = 1 2 3 4 A^5(B=5)를 구하면 된다. 접근법 첫번째 시도. 우선 B가 매우 큰 값이 올 수 있기 때문에 A의 B제곱에서 제곱 수인 B를 줄일 수 있는 방법을 고민했다. 즉, A를 B번 곱하는데, 이를 B보다 적게 곱하게 하고 싶었다. 분할 정복 문제이.. 2021. 1. 19. [알고리즘] 백준. ATM #11399, 검문 #2981 단계적으로 풀기에서 그리디 알고리즘 파트의 문제인 "ATM"과 수학3 파트 문제인 "검문"을 풀어보았다. ATM 예를 들어 다음과 같이 사람들이 ATM 앞에서 업무를 처리하기 위해 줄을 섰다고 하자. 그리고 밑의 숫자는 각 사람들이 업무를 보는 데 걸리는 시간이다. 각 사람들이 자신의 업무를 마치는 데까지 걸리는 시간은 다음과 같다. 이를 단순화 시켜보면, "기다리는 시간+자신의 업무 시간"만큼의 시간이 걸린다. 문제에서 요구하는 것은 모든 사람이 자신의 업무를 마치는 데 걸리는 시간을 최소화 시키도록 사람들을 줄 세우고 싶은 것이고, 그렇게 줄을 섰을 때 마지막 사람이 자신의 업무를 마칠 때까지 걸린 시간을 구하고자 하는 것이다. 위에서 "기다리는 시간+자신의 업무 시간"을 살펴보면, 결국 우리가 줄일.. 2020. 6. 28. [알고리즘] 백준. #1932 회의실 배정 문제를 간단히 설명하자면, n개의 입력값을 받는데, 회의의 시작 시간과 종료시간으로 구성되어 있다. 주 회의를 가능한 많이 진행하고자 한다면, 최대 몇 개의 회의가 진행될 것인가 이다. 뭔가 OS 시간에 배운 scheduling 알고리즘 중에서도 비슷한 게 있었던 것 같다.. 물론 cpu scheduling의 경우엔 중간에 가로채는 것도 가능하고 하니깐 조금은 다른 방향성을 띄게 될 것이다. 모든 프로세스의 시간을 다 알고 있는 것도 아니고,,, 예제로 나와있는 입력값을 도식화 하면 다음과 같다. 주황 막대기는 회의 시간을 나타낸다. 수직으로 내려와 수직선과 만나는 곳에서 시작 시간과 종료 시간을 유추해볼 수 있다. 결국 저 주황 막대들이 겹치지 않게 가장 많이 고르는 방법을 찾는 것이다. 그리고 그 때.. 2020. 6. 11. [알고리즘] 백준. 2748, 1003 피보나치(동적 계획법) Dynamic programming 파트 중 피보나치 수열에 관한 두 문제이다. 피보나치 수열에 대해 간단히 설명하자면, n번째 피보나치 수는 n-1번째 피보나치 수와 n-2번째 피보나치 수의 합이다. 여기서 n은 2이상의 자연수이고, 초깃값이 n=0, n=1일 때 각각 0, 1로 주어진다. 다음은 n과 이에 대응되는 피보나치 수이다. n 0 1 2 3 4 5 ... 피보나치 수 0 1 1 2 3 5 파이썬으로 구현했는데, 재귀함수 형태로 구현했을 때, pypy3으로 채점을 했는데도 속도가 느렸다. 따라서 다른 방식을 써보기로 했다. 먼저 2748번이다. 입력을 받는데, 90이하의 자연수를 입력값으로 받고 해당 수에 해당하는 피보나치 수를 출력해주면 된다. 필자는 재귀 함수 대신 파이썬의 리스트를 이용해.. 2020. 6. 6. [알고리즘] 백준. # 정렬 2751 O(nlogn)의 복잡도를 가진 정렬 방식으로 구현하라 했는데, 오랜만에 '합병 정렬(merge sort)'을 써서 한 번 구현해 보고자 하였다. (물론 문제에선 내장 함수를 쓰라고 하긴 했다..ㅎㅎ) 재귀 형식으로 구현했는데, 아니나 다를까. 실행시간 초과다.. n = int(input()) ls = [] for i in range(n): ls.append(int(input())) def combine(ls, start, mid, end): s = start t = mid+1 sorted_ls = [] while True: if s > mid: sorted_ls+=ls[t:end+1] break elif t>end: sorted_ls+=ls[s:mid+1] break if ls[s]=end: retur.. 2020. 6. 3. [알고리즘] 백준. 정렬 #2750 요즘 백준 문제 풀이를 하루에 하나 정도 해 나가고 있다. 단계별로 풀이 중에서 하루에 한 단계씩, 그 중에 하나를 골라서 하고 있다. 오늘은 정렬이 주제였는데, 시간복잡도가 O($n^2$)인 정렬을 수행하는 문제였다. 파이썬을 사용하니 확실히 코드가 간결하고 짜기 쉽다. list를 이용해서 쉽게 구현할 수 있었다. 삽입 정렬과 비슷하게 구현된 거 같은데, 숫자가 하나씩 주어져서 이런 식으로 구현하는 게 나을 거 같았다. 예제 입력은 다음과 같다. 처음에 숫자의 개수를 입력 받고 그 뒤에 숫자가 하나씩 입력된다. 5 5 4 3 2 1 이에 대한 출력값은 오름차순으로 정렬된 다음과 같아야 한다. 1 2 3 4 5 다음은 구현한 코드이다. ### 정렬 n = int(input()) ls = [] for i .. 2020. 6. 1. 반응형 이전 1 다음
