YoungSoo

이 문제는 알고리즘 유형 중 DFS를 통해 푸는 문제이다 깊이 우선 탐색(DFS, Depth-First Search)은 최대한 깊게 내려갔다가 더 이상 갈 수 없다면 다시 가장 가까운 갈림길로 돌아가 다른 방향을 탐색하는 깊이 우선 탐색 방식이다. 보통 스택 또는 재귀함수로 문제 풀이를 하며 모든 정점을 방문하거나 경로의 특징을 저장해야하는 문제는 DFS를 사용해 풀면 좋습니다. import sys sys.setrecursionlimit(10**9) input = sys.stdin.readline n, m, r = map(int, input().split()) v=[0] * (n+1) graph=[[] for i in range(n+1)] cnt=1 for i in range(m): a, b = map(..

먼저 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 빨간색 숫자를 제외한 나머지는 제외하고 구해야하는데 그냥 누적합만 한다면 파란색 숫자는 제외하고..

먼저 비교적 쉬운 문제인 가장 긴 증가하는 부분 수열 문제는 한 수열에서 부분적으로 증가하는 수열을 찾고 그 중에 제일 긴 부분 수열을 찾는 문제이다. import sys input = sys.stdin.readline n = int(input()) a = list(map(int, input().split())) dp = [0 for i in range(n)] for i in range(n): for j in range(i): if a[i] > a[j] and dp[i] < dp[j]: dp[i] = dp[j] dp[i] += 1 print(max(dp)) dp라는 배열을 먼저 선언해준 뒤 반복문을 통해 증가하는 부분 수열을 모두 구해준다. 이중 포문을 사용하는 이유는 현재 계산 중인 배열에 해당 조건에..

백트래킹에서의 마지막 문제였는데 백트래킹 알고리즘은 정말 어려웠다. 먼저 틀린 예제를 보자. import sys input = sys.stdin.readline def dfs(a): global result if len(s) == n//2: lt, st = 0, 0 for i in range(1, n+1): for j in range(1, n+1): if i not in s and j not in s: lt += arr[i-1][j-1] elif i in s and j in s: st += arr[i-1][j-1] result= min(result, abs(lt-st)) return for i in range(a, n+1): if i not in s: s.append(i) dfs(i) s.pop() n=..

백준 단계별로 풀어보기를 풀다가 백트래킹이란 이름을 처음 접하게 되었다. 설명에는 간단하게 모든 경우를 탐색하는 백트래킹 알고리즘이라고 적혀있지만 더 공부하고 가면 좋을 거 같다는 생각에 공부를 해보려고 한다. 백트래킹(Backtracking)이란 위에서 설명했듯이 모든 경우를 탐색하고 찾는 정답이 아니면 되돌아가 다른 경우를 찾아보는 문제 해결 기법을 말합니다. 백트래킹은 코딩을 할 때 반복문의 횟수를 줄여 시간이 줄어 효율적이고 백트래킹이 얼마나 잘 되어 있는 것에 따라 효율성이 결정됩니다. 반대로 깊이 우선 탐색(DFS)이 있는데 DFS는 모든 경우를 찾아봅니다. 그렇기 때문에 경우의 수가 줄어들지 않습니다.

이 문제를 처음 풀었을 땐 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()...