KBW's cosmos

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억보다 작으므..

하노이 탑의 해결 방법을 생각해보면 재귀적이다. 위의 gif처럼 1~6번 원판을 첫 번째 장대에서 세 번째 장대로 옮기기 위해서는 먼저 1~5번 원판을 두번째로 옮긴 후 6번 원판을 세 번째 장대로 옮겨야한다. 이렇게 되면 문제는 1~5번 원판을 두 번째 장대에서 세 번째 장대로 옮기는 문제로 바뀐다. 즉, 재귀는 자기보다 작은 규모의 문제를 먼저 해결하고 그것을 자기의 문제에 이용하는 것이다. 재귀는 Base Case + Recursive Case로 이루어져있다. Base Case는 if문 안의 부분이며 바닥에 닿았을 때 재귀를 끝내는 경우이다. Recursive Case는 else 안의 부분이며 재귀적으로 반복하게 하는 경우이다. 위 용어를 바탕으로 정리하면, 1. Recursive Case의 경우 ..

정점과 간선은 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. 작은 문제에서 구한 답은 그것을 포함하는 큰 문제에서도 동일하다. 이 가정중 두번째가 가장 핵심적인 것이다. 작은 문제에서 구한 정답이 큰 문제에서의 문제와 동일하기 때문에 작은 문제에서 구한 정답을 잠시 배열에 저장을 해놓고 나중..

https://kbwplace.tistory.com/87 [Python/파이썬] 백준 알고리즘 1406번 - 에디터 string = list(input()) N = len(string) M = int(input()) cursor = N for _ in range(M): command = input().split() if command[0] == "L": if cursor > 0: cursor -= 1 elif command[0].. kbwplace.tistory.com 여기서 풀었던 방법을 응용했다. 문제의 시간 제한이 0.5초로 빡빡한 편이라 시간 단축을 위해서 insert와 같은 high cost의 함수는 사용하지 않고 append, pop 함수만으로 구현해야한다. 이것을 구현하는 방법은 위의 140..

N, K = map(int, input().split()) circular_queue = [i for i in range(1, N+1)] cursor = K-1 result = [] while circular_queue: result.append(str(circular_queue.pop(cursor))) # 순서 중요! N 감소가 cursor 이동보다 선행되어야 함. N -= 1 if N > 0: if (cursor + K) % N == 0: cursor = N - 1 else: cursor = (cursor + K) % N - 1 print("") 처음에 저 N -= 1을 뒷 순서에 놔서 애먹었다.. 커서를 이동시켜가며 해당 인덱스에 도달했을때 pop해 result 리스트에 넣고 마지막에 출력하는 방식..