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

정점과 간선은 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. 작은 문제에서 구한 답은 그것을 포함하는 큰 문제에서도 동일하다. 동적 계획법을 사용..

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 리스트에 넣고 마지막에 출력하는 방식..

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] == "D": if cursor 0: string.pop(cursor-1) cursor -= 1 elif command[0] == "P": string.insert(cursor, command[1]) cursor += 1 for s in string: print(s, end='') 처음에 위와 같..

N = int(input()) coList = list(map(int, input().split())) # 중복 값 제거한 후 정렬 coList_sort = sorted(list(set(coList))) for coordinate in coList: print(coList_sort.index(coordinate), end=' ') 처음에 이렇게 풀었으나 시간 초과가 났다. 리스트.index(i)의 시간 복잡도는 O(N)이다. 인덱싱을 방법 중 더 낮은 시간 복잡도의 방법은 딕셔너리를 이용하는 방법이다. (O(1)) N = int(input()) coList = list(map(int, input().split())) # 중복 값 제거한 후 정렬 coList_sort = sorted(list(set(coL..