KBW's cosmos

""" 1. 아이디어 연산자들 숫자만큼 리스트로 연산자를 담고 백트래킹으로 순회한다. 그리고 각각의 결과값을 구해 비교하여 최댓값과 최솟값을 구한다. 2. 시간복잡도 - O(N^2) : 100 * 100 가능 3. 자료구조 N: int; A: int[]; operator: str[]; canUsedCnt: int[]; maxValue, minValue: int; """ import sys sys.setrecursionlimit(10 ** 4) input = sys.stdin.readline N = int(input()) A = list(map(int, input().split())) canUsedCnt = list(map(int, input().split())) operatorList = ..

처음 필자는 시작 시간과 끝나는 시간의 차를 구해 그것을 기준으로 오름차순 정렬 후 다른 회의 시간대와 겹치지 않는다면 추가하는 방식으로 풀려고 했다. 하지만 이 방식의 경우 이중 for문을 사용하게 되므로 O(n^2) : 100000 * 100000 = 100억 (> 4억(시간제한 2초))이 되버려 불가능한 풀이였다. 이는 조금 생각을 달리하여 풀리는 문제였는데, 전체 회의의 시작시간은 0시로 정해져있으니 굳이 회의 시간을 구해주지 않더라도 끝나는 시간을 기준으로 오름차순 정렬하면 그것이 회의 시간을 정렬한 것과 비슷한 의미가 될 수 있었다. 그리고 한가지 더 고려해야할 사항이 있는데 끝나는 시간이 같은 경우이다. 끝나는 시간이 같다면 빨리 시작하는 순서대로 정렬이 되어야한다. 예를 들어보겠다. (3 ..

1. 아이디어 재귀 호출로 인한 시간복잡도를 줄여줄 수 있는 DP를 이용해야한다. 3차원 배열로 memoization을 만들면 되지 않을까..? 20 * 20 * 20의 공간만 있으면 된다. 2. 시간복잡도 - O(n^3) : 20 * 20 * 20 = 8000 -> 가능 3. 자료구조 a, b, c: int; dp: int[][][]; 전체코드 ↓ import sys sys.setrecursionlimit(10 ** 6) input = sys.stdin.readline def w(a, b, c): if a 20: return w(20, 20, 20) elif dp[a][b][c]: return dp[a][b][c] elif a < b < c: dp[a][b][c] = w(a, b, c-1) + w(a,..

1. 아이디어 for문으로 1부터 N까지 돌리면서 이미 선택한 값이 아닌 경우 선택 M개 선택하는 경우 출력하고 return 하나의 리스트를 사용할 것이고 return해서 위 depth로 올라왔을 때 그대로 append만 하면 기존 리스트의 옆에 붙을테니 백트래킹 방식으로 return할 때 리스트 맨 끝을 지워주는 처리를 해줘야함. 2. 시간복잡도 - BackTracking - 중복이 가능한 경우 : O(N^N) (N = 8까지 가능) (시간제한 1초인데 1초에 2억까지 처리가능하므로) - 중복이 불가능한 경우 : O(N!) (N = 10까지 가능) - 중복이 불가능하면 depth가 깊어짐에 따라 N개에서 하나씩 줄어드니까 N!인 것 3. 자료구조 N, M: int; result = int[]; visi..

1. 아이디어 bfs로 queue를 만들고 1인 지점부터 시작해서 queue에 넣고 pop하길 반복한다. 처음 시작할 때 1인 지점을 몽땅 queue에 넣어두고 시작한다. 처음 1인 곳이 여러곳일 수 있다. 그래서 queue에 있는걸 다 처리하게 해야한다. 따로 if문을 두고 break하지 않는다. 마지막에 이중포문 돌리면서 익지못한 토마토(0)가 있는지 확인 없다면 가장 큰 숫자 출력 2. 시간복잡도 - BFS : O(V + E) - V : 1000 * 1000 - E : 4 * 1000 * 1000 - V + E : 5 * 1000 * 1000 = 5e6 (5백만) - 이중포문 : O(NM) - NM : 1000 * 1000 - 전체 시간복잡도 : O(6NM) = 6e6 (6백만) - 2억보다 작으므..

정점과 간선은 Graph에서 나오는 개념들이다. 정점은 흔히 Vertex라고 부르며 간선은 Edge라고 부른다. 전체 풀이 ↓ import sys from collections import deque N, M, V = map(int, sys.stdin.readline().rstrip().split()) graph = [[0] * (N + 1) for _ in range(N+1)] DFS_visited = [False] * (N + 1) BFS_visited = [False] * (N + 1) for _ in range(M): x, y = map(int, sys.stdin.readline().rstrip().split()) graph[x][y] = 1 graph[y][x] = 1 def dfs(V): DF..

지금까지 푼 문제 중에는 가장 까다로웠다.. 다이나믹 프로그래밍을 통해 푸는 문제다. 먼저 Bottom-Up 방식으로 dp의 1번 인덱스부터 차근차근 생각해보겠다. 편의상 Pi 카드팩을 i번 카드팩이라고 부르겠다. dp[1] = 1을 만드는 방법 : 1번 카드팩 1개 dp[2] = 2를 만드는 방법 : 2번 카드팩 1개 or 1번 카드팩 2개 중 큰 것 dp[3] = 3을 만드는 방법 : 3번 카드팩 1개 or 1번 카드팩 1개 + dp[2] 중 큰 것 (여기서 1,1,1로 3을 만드는 경우, 1,2로 3을 만드는 경우는 dp[2]에서 처리가 끝난 것이다.) ... dp[n] = n을 만드는 방법 : n번 카드팩 1개 or 1번 카드팩 1개 + dp[n-1] or dp[2] + dp[n-2] or .. ..

n = int(input()) dp = [0] * 1001 dp[1] = 1 dp[2] = 2 for i in range(3, 1001): dp[i] = dp[i-2] + dp[i-1] print(dp[n] % 10007) 처음에는 너무 복잡하게 생각했다. 그냥 간단하게 수열의 점화식을 찾고, 그 값들을 리스트에 저장하는 메모이제이션 방법을 사용해 풀면 되는 것이었다. 나열되는 방법의 수들의 규칙성을 찾고 그것을 점화식으로 표현하면 다음과 같다. dp[i] = dp[i-2] + dp[i-1] 이 점화식을 이용해 리스트에 값들을 메모이제이션하기에 앞서 2x1 크기의 직사각형을 채우는 방법의 수는 1, 2x2 크기의 직사각형을 채우는 방법의 수는 2이므로 dp[1], dp[2]에 각각 1과 2를 먼저 넣는다..

힌트 : 10의 경우에 10 -> 9 -> 3 -> 1로 3번만에 만들 수 있다. 이 문제는 전에 결과를 다음 결과에 이용하는 Dynamic Programming(동적 계획법) 문제이다. 힌트를 보면 정수 X가 10인 경우 10 -> 9 -> 3 -> 1 의 과정으로 1이 된다고 했는데, 10은 정수 X가 9인 경우의 횟수에 +1을 한 값이고 9는 정수 X가 3인 경우의 횟수에 +1을 한 값이고 3은 정수 X가 1인 경우의 횟수에 +1을 한 값이다. 다시 말해서 10을 구할 때는 9의 결과를, 9를 구할 때는 3의 결과를 이용한다. 따라서 아래의 조건을 만족하기 때문에, 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 답은 그것을 포함하는 큰 문제에서도 동일하다. 동적 계획법을 사용..

다이나믹 프로그래밍(동적 계획법)이란 무엇일까? 다이나믹 프로그래밍(동적 계획법)은 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다. 일반적인 분할 정복 기법(ex. 일반적 재귀로 구현한 피보나치 수열 함수)의 경우 동일한 문제를 다시 푼다는 단점을 가지고 있다. 이러한 경우에 하나의 문제를 단 한 번만 풀게해 더 효율적으로 만드는 것이 다이나믹 프로그래밍이다. 다이나믹 프로그래밍은 아래와 같은 가정 하에 사용할 수 있다. 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 답은 그것을 포함하는 큰 문제에서도 동일하다. 이 가정중 두번째가 가장 핵심적인 것이다. 작은 문제에서 구한 정답이 큰 문제에서의 문제와 동일하기 때문에 작은 문제에서 구한 정답을 잠시 배열에 저장을 해놓고 나중..