KBW's cosmos

사실 이 문제를 볼 때 부분 수열을 만들 때 기존 수열의 순서를 그대로 따라야하는지가 헷갈렸다. 하지만 그렇다면 그냥 set으로 중복을 제거하고 수를 구하면 될 것이다... 그래서 아마 이것은 아니겠지 하고 풀었다. 처음에는 완전 탐색으로 풀 생각을 했다.. """ 1. 아이디어 - 가장 작은 수 하나를 구한다 - 이후 뒤 수열을 for문으로 돌며 큰 수를 찾는다. 2. 시간 복잡도 - 두개의 포인터 : O(N) - 전체 조회 : O(N^2) = 1,000,000 -> 가능 3. 변수 - N : int - A : int[] """ import sys input = sys.stdin.readline N = int(input()) A = list(map(int, input().split())) max_len..

처음에는 백트래킹으로 풀 생각을 했다.. import sys sys.setrecursionlimit(10 ** 6) input = sys.stdin.readline N = int(input()) cnt = 0 def backTracking(depth): if depth == N: global cnt cnt += 1 return elif num[-1] == 0: num.append(1) backTracking(depth + 1) num.pop() elif num[-1] == 9: num.append(8) backTracking(depth + 1) num.pop() else: for i in (num[-1] - 1, num[-1] + 1): num.append(i) backTracking(depth + 1)..

경로를 표현해야해서 처음에는 DFS로 탐색해야하나..? 생각했다 하지만 BFS로도 충분히 해결할 수 있었다. 경로에 대한 배열을 따로 만들어 최단경로에 대한 값을 저장하며 해결하는 것이다. # 아래는 따로 path 배열을 안만들고 파라매터로 받아 처리한건데 시간초과 나온다... # 왜 시간초과가 나올까..? import sys from collections import deque input = sys.stdin.readline N, K = map(int, input().split()) road = [0] * 100001 queue = deque() queue.append([N]) road[N] = 1 while queue: pathList = queue.popleft() popN = pathList[-1..

기존 숨바꼭질 문제에서는 모든 가중치가 1이었다. 이 문제의 차이점은 순간이동하는 경우는 0으로 가중치가 다르다는 것이다. 순간이동은 0초가 걸리고 걷기는 1초가 걸리므로 큐를 2개로 나눠 구현하면 된다. 이때 양방향 큐인 deque를 활용하면 별도의 큐를 더 생성하지 않고 구현할 수 있다. 순간이동하는 경우는 appendleft로 맨앞에 추가해주고 걷는 경우는 append로 뒤에 추가해주면 된다. import sys from collections import deque input = sys.stdin.readline N, K = map(int, input().split()) road = [0] * 100001 queue = deque() queue.append(N) road[N] = 1 while qu..

""" 1. 아이디어 가장 빠른 시간을 출력하고 '방법의 가짓수'도 출력해야하므로 dfs로 탐색해야한다. 최대 수는 동생 위치에서 수빈이의 위치를 뺀 값이고 해당 값에 도달하면 탐색을 마쳐야한다. (그때까지 찾아도 못찾았다는건 최단거리 탐색에 실패한 트리가지인거니까) dfs로 탐색했을 때 동생이 있는 점 K에 도달할 때 도달하는데 걸린 횟수를 저장한다. 그리고 다음에 또 도달하면 둘을 비교해 더 큰 값을 저장한다. 만약 같다면 같은 도달 시간 횟수를 체크한다. bfs로 탐색한다. visited 배열에 걸린 시간을 체크해서 적어두는데 이미 시간이 적힌 배열칸에 다시 접근하기 위해서 or 연산자를 이용해 visited[nextX] == visited[popX] + 1 를 추가한다. 2. 시간복잡도 - 3. ..

""" 1. 아이디어 브루트포스로 다 돌려본다. N이 최대 50이므로 가능하다. 한 위치에서 상하좌우와 바꿀 수 있지만 겹치므로 아래와 오른쪽만 계속해서 바꿔주면 된다. 바꿔준 뒤, 전체 보드에서 먹을 수 있는 사탕의 최대 개수를 구한 뒤 다시 원상복구 해주고 다음 걸로 넘어가 바꿔주고 확인하고를 반복하면 된다. 2. 시간복잡도 - O(N^4) : 50 ** 4 = 6250000 가능 3. 자료구조 N: int; board: str[][]; maxCnt: int; """ import sys input = sys.stdin.readline N = int(input()) board = [list(input()) for _ in range(N)] maxCnt = 0 def check(): glo..

""" 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..