YoungSoo

먼저 LIS는 보통 DP 문제로 많이 나오는데 DP로 풀이하면 시간 복잡도가 O(N**2)인데 이 문제는 O(NlogN)의 시간 복잡도로 문제를 풀어야 하기에 이분탐색을 통해 풀었고 지금까지 알고리즘을 공부하면서 제일 어려운 부분이 이분탐색인 거 같다. import sys input = sys.stdin.readline n = int(input()) aa = list(map(int, input().split())) result = [0] for a in aa: if result[-1] < a: result.append(a) else: start, end = 1, len(result) while start < end: mid = (start+end)//2 if result[mid] < a: start = ..

이 색종이 만들기 문제는 백준에서는 분할 정복 알고리즘으로 분류되어 있다. 여기서 분할 정복 알고리즘은 기본적으로 엄청나게 크고 방대한 문제를 조금씩 나눠가면서 푸는 문제인데 재귀 함수랑 비슷하다고 생각이 들어 재귀함수처럼 함수 내에서 자기 자신의 함수를 호출하여 푸는 방식으로 알고리즘을 생각해보았다. 풀이 import sys input = sys.stdin.readline n = int(input()) bd = [list(map(int, input().split())) for _ in range(n)] result = [] def d(x, y, n): color = bd[x][y] for i in range(x, x+n): for j in range(y, y+n): if color != bd[i][j]..

누적합 알고리즘 - 매우 많은 수를 반복할 수도 있기에 시간복잡도를 줄이는 알고리즘을 짜야하는데 그 알고리즘은 대체적으로 미리 배열에 수를 저장한 뒤 계산을 통해 값을 도출해내야하며 이것을 통해 수가 큰 답에서도 시간을 단축할 수 있다 이번 문제는 누적합 알고리즘을 통해 문제를 해결할 수 있는 문제였다. 앞에 푼 구간 합 구하기 4문제랑 유사하지만 이번 문제는 1차원 배열에서 구하는 것이 아닌 2차원 배열 공간에서 구하는 것이다. 그렇기 때문에 약간 다른 점이 있었다. 예를 들어 (x1=2, y1=2), (x2=3, y2=4) 이와 같은 예제가 있을 때 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 빨간색 숫자를 제외한 나머지는 제외하고 구해야하는데 그냥 누적합만 한다면 파란색 숫자는 제외하고..

이 문제를 처음 풀었을 땐 factorial함수와 반복문을 이용해서 구하였는데 이 방식으로 구하면 시간초과로 인해 실패한다. 그 이유는 2,000,000,000이라는 큰 숫자까지 풀 수 있기 때문에 반복문을 사용하면 시간초과가 나올 수 밖에 없었다. 그래서 새로운 방법을 생각했는데 그 방법은 끝자리가 0일 때는 10의 배수이며 10은 2와 5로 구성되어 있다. 2와 5의 개수가 같아야 10의 배수가 되므로 2와 5중에 작은 것의 개수를 구한다면 답이 나올 수 있다. import sys input = sys.stdin.readline def cnt(a,b) : result = 0 while a != 0: a = a//b result+=a return result n, m = map(int, input()...