본문 바로가기
반응형

알고리즘 테스트58

백준 1920: 수 찾기 (파이썬) 문제: https://www.acmicpc.net/problem/1920 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 코드 #https://teching.tistory.com/ import sys def find(a, list): left = 0 right = len(list) while left a: right = mid elif list[mid] < a: left = mid + 1 e.. 2022. 5. 4.
피보나치 수를 구하는 다양한 방법 알고리즘 문제를 풀다 보니 피보나치 수를 구하는 방법이 상당히 많다. 따라서 이 피보나치 수로 배울 수 있는 알고리즘이 다양하기에 한번 정리를 해보려고 한다. 피보나치 수열이란? 기원전 5세기 인도의 수학자 핑갈라가 쓴 책에서 처음 언급 됐으며 유럽에서 레오나르도 피보나치가 토끼 수의 증가에 대해서 이야기 하면서 유명해졌다. 해당 내용은 n번째 달의 토끼 쌍의 수는 첫 달에는 새로 태어난 토끼 한 쌍만이 존재한다. 두 달 이상이 된 토끼는 번식이 가능하다. 번식 가능한 토끼 한 쌍은 매달 새끼 한 쌍을 낳는다. 토끼는 죽지 않는다 이 문제를 통해서 나온 것이 바로 피보나치 수열이다. 첫 번째 달, 두 번째 달 까지는 1쌍이 존재할 것이다. 세 번째 달이 되면서 토끼가 번식이 가능해지면서 2쌍이 되고 3번.. 2022. 4. 6.
백준 11444: 피보나치 수 6 (파이썬) 문제: https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 코드 # https://teching.tistory.com/ import sys def matrixMultiple(matrix1, matrix2): res = [[0]*len(matrix2[0]) for _ in range(len(matrix1))] for i in range(len(matrix1)): for j in range(len(matrix2[0])): for k in range(len(matrix1[0])): res[i][j] += matrix1[i][k] .. 2022. 4. 6.
백준 2740: 행렬 곱셈 (파이썬) 문제: https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 코드 #https://teching.tistory.com/ import sys n1, m1 = map(int, sys.stdin.readline().split()) matrix1 = [list(map(int, sys.stdin.readline().split())) for _ in range(n1)] n2, m2 = map(int, sys.stdin.readline().sp.. 2022. 4. 5.
백준 11401: 이항 계수 3 (파이썬) 문제: https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 코드 #https://teching.tistory.com/ n, k = map(int, input().split()) mode = 1_000_000_007 def pastPow(a, b, c): if b == 0: return 1 elif b == 1: return a % c else: DivCon = pastPow(a, b // 2, c) if b % 2 == 0: return (DivCon * DivCon) .. 2022. 4. 1.
백준 1629: 곱셈 (파이썬) 문제: https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 코드 # https://teching.tistory.com/ a, b, c = map(int, input().split()) def pastPow(a, b, c): if b == 0: return 1 elif b == 1: return a % c else: DivCon = pastPow(a, b // 2, c) if b % 2 == 0: return (DivCon * DivCon) % c else: return (DivCon * DivCon * pastP.. 2022. 3. 29.
백준 1780 : 종이의 개수 (파이썬) 문제: https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 코드 1 #https://teching.tistory.com/ import sys cnt = { -1: 0, 0: 0, 1: 0 } def check(paper, n): if n == 1: return True plag = paper[0][0] for i in range(n): for j in range(n): if plag != paper[i][j]: return False r.. 2022. 3. 29.
백준 1992: 쿼드트리 (파이썬) 문제: https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 코드 #https://teching.tistory.com/ import sys res = "" def makeConftti(list): global res tmp = 0 for line in list: tmp += sum(line) n = len(list) if tmp == n*n: res += "1" return elif tmp == 0: res += "0" return #가.. 2022. 3. 29.
백준 2630: 색종이 만들기 (파이썬) 문제: https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 코드 #https://teching.tistory.com/ import sys cntWhite = 0 cntBlue = 0 def makeConftti(paper): global cntBlue, cntWhite tmp = 0 for line in paper: tmp += sum(line) n = len(paper) if tmp == n*n: cntBlue += 1.. 2022. 3. 29.
반응형

티스토리툴바