본문 바로가기

Algorithm

[Baekjoon]백준 1654 랜선 자르기(실버 2) - Python, C++ 문제를 읽어보면 영식이는 여러 개의 랜선을 가진 상태에서 N개의 랜선을 만들고싶어한다그리고 N개 이상의 랜선을 만들 수 있는 가장 긴 랜선의 길이를 구하는 것이 문제이다예제를 보면 802, 743, 457, 539 이렇게 3개가 존재하는데랜선 하나의 길이가 201이 되면 11개를 만들 수 없지만, 200이 된다면 11개를 만들 수 있게 된다 그래서 처음에 들었던 생각으로는 모든 길이를 합친 후에 여기서 수를 나누어가며 확인해야되나? 라고 생각했다예제에서의 상황으로 가정하면 모든 수를 더하게 되면 2541이 나오게 되고, 이를 11로 나누면 231이 된다이 231을 이용하여 수를 조절하며 확인을 해볼까..? 라는 생각을 잠깐 해보다가 만약 숫자들의 차이가 너무 커지면시간복잡도 측면에서 너무 불리할 것 같다.. 더보기
[Baekjoon]백준 6549 히스토그램에서 가장 큰 직사각형(플래티넘 5) - Python 문제를 살펴보면 히스토그램이 주어지고, 이 히스토그램에서 그릴 수 있는 가장 큰 직사각형을 찾아그 넓이를 출력하면 되는 문제이다 높이가 가장 높은 index부터 확인을 하게 되면 우리의 입장에서는 간단하지만이를 코딩을 하기에는 왼쪽, 오른쪽으로 나누어 별도로 처리해야한다 또한 최대 넓이를 계산하기 위해for문을 두개 사용하게 되면 O(N^2)의 시간이 걸린다 그래서 이분 탐색의 원리처럼 중간 index를 기준 하나 첫 index부처 중간 index까지의 경우, 중간 index부터 끝 index까지의 경우 총 3개로 나누어 계산하는 로직을 생각하였다 이 방식을 사용하면 해당 함수를 재귀적으로 호출하면서index의 범위를 인자로 전달하기 때문에 분할 정복의 방식으로 해결할 수 있다 이후 while문에서 각 .. 더보기
[Baekjoon]백준 1920 수 찾기(실버 4) - Python, C++ 문제를 살펴보면 이분 탐색 테마의 문제인데, 첫번째에 비교 대상인 리스트가 주어지고두번째에 결과값에 영향을 끼치는 리스트를 하나 입력을 받는다 이후에 처음으로 입력받은 리스트에두번째로 입력받은 리스트의 값이 존재하면 1을, 아니라면 0을 출력하면 된다Python의 딕셔너리로 풀어도 가능할 거 같긴 하지만 문제 출제 의도에 맞게 이분 탐색을 직접 구현하여 코드를 작성하였다 코드 설명을 하기전에 이분 탐색에 대해 설명을 하자면 정렬된 리스트를 기준으로 하며, 해당 값을 찾을 때먼저 중간에 위치한 값과 비교를 한다 리스트에 정렬이 되어있기 때문에 해당 위치의 값과 비교를 하였을 때 값이 작다면더 낮은 index에 값이 존재할 것이고, 크다면 더 높은 index에 값이 존재할 것이라는 추측이 가능하다이러한 로직.. 더보기
[Baekjoon]백준 피보나치 수 6(골드 2) - Python 문제를 살펴보면 이전에 풀어보았던 피보나치수와 같다다만, 주어지는 숫자가 커지고 그로 인하여 시간이 오래 걸리기 때문에 분할 정복 알고리즘을 사용하여큰 숫자가 들어오더라도 빠른 속도로 연산을 하는 것이 목표이다이 문제를 분할 정복 알고리즘으로 풀기위해 점화식을 먼저 찾아보았고, 그 덕분에 빠른 방법을 알게되었다주어진 Fn, Fn-1, Fn-2를 활용하여 점화식을 만들수 있는데, 이를 행렬의 곱으로 표현할 수 있다# 기본적인 피보나치 점화식:# | F(n) | = | 1 1 | * | F(n-1) |# | F(n-1) | | 1 0 | | F(n-2) |풀이코드에도 들어간 주석인데, 이 점화식을 활용함과 동시에 이전 문제에서 행렬의 제곱을 분할정복을 사용하여 풀어보았기 때문에 이 코드를 .. 더보기
[Baekjoon]백준 10830 행렬 제곱(골드 4) - Python, C++ 문제를 살펴보면 이전에 풀이하였던 곱셈에서 제곱으로 레벨이 조금 올라간 모습이다이전 문제를 풀어오면서 분할 정복에 대한 알고리즘은 조금 익혔기 때문에 간단하게만 설명을 하자면그냥 일반적인 방법으로 제곱을 하게 되면 O(n)의 행렬 곱셈을 필요로 하지만, 분할 정복을 사용하면시간 복잡도를 O(logN)으로 줄일 수 있다 n = 1인 경우 행렬을 return하면 되고,짝수인 경우는 A^n = A^n/2 x A^n/2, 홀수인 경우는 A^n = A^n//2 x A^n//2 x A와 같은 방식으로 곱하면 된다def mul(a, b): # 행렬 곱 구하는 함수 res = [[0] * size for _ in range(size)] for i in range(size): for j in ra.. 더보기
[Baekjoon]백준 2740 행렬 곱셈(실버 5) - Python, C++ 문제를 살펴보면 그냥 단순하게 두 행렬을 입력받아 곱한 결과를 출력하는 문제이다행렬의 곱을 알고있다면 알겠지만, 두 행렬을 곱하려면 앞 행렬의 열의 개수와 뒤 행렬의 행의 개수가 같아야한다그리고 그 곱의 결과 행렬은 앞 행렬의 행의 크기가 행의 개수, 뒤 행렬의 열의 크기가 열의 개수가 된다즉, 3 x 2 , 2 x 4의 행렬의 결과는 3 x 4 행렬이 된다는 것이다 이 점을 참고하여 행렬의 값을 저장하는 리스트를 0으로 초기화하여 만들어주었고, for문을 통해 각 곱을 계산하고 더해주었다문제 자체는 쉽지만, 행렬의 곱 자체가 실수하기 쉽기 때문에 따로 그려가며 index를 확인하며 작성하였다결과는 언패킹을 사용하여 간단하게 출력하였다A = []row_size_A, col_size_A = map(int,.. 더보기
[Baekjoon]백준 11401 이항 계수 3(골드 1) - Python 문제 자체는 이전에 풀었던 이항계수 문제들과 동일하지만, 분할 정복을 사용하여야한다는 차이점이 존재한다일단 그래도 혹시나 싶어서 재귀함수를 사용하지 않고 팩토리얼을 계산하여 나머지를 출력하는 코드를 작성하였다num, square = map(int, input().split())def sol(num, square): if square == 0 or square == num: return 1 elif square > num // 2: square = num - square result = 1 for i in range(square): result = result * (num - i) // (i + 1) return result .. 더보기
[Baekjoon]백준 1629 곱셈(실버 1) - Python 문제를 보면 아주 단순하다 첫번째 입력받은 숫자를 두번째 입력받은 숫자만큼 제곱하고, 세번째로 입력받은 숫자로나누었을때의 나머지를 출력하면 된다 이 문제를 풀기위해 수학 공식의 일부를 사용하였는데,예를 들어 (10 x 20) % 4의 경우 (10 % 4) x (20 % 4)와 동일하다는 점을 활용하여 코드를 작성하였다num, square, div = map(int, input().split())if num > div: num %= div tmp = numfor _ in range(square): tmp = tmp * tmp % div print(tmp)분할정복 테마답게...시간초과가 발생한다 혹시나 했는데 역시나였다그래서 이 숫자를 나누어 계산하되, 재귀함수를 이용하는 코드를 작성할.. 더보기

티스토리툴바