KBW's cosmos

처음에는 백트래킹으로 접근하려고 했다. """ 1. 아이디어 - 백트래킹으로 탐색하며 벽을 뚫을 때와 안뚫을 떄를 구분하여 전체 가지수를 탐색한다. 2. 시간 복잡도 - O(N * M) : 1000 * 1000 = 1,000,000 -> 가능 3. 변수 - N, M : int - map : int[][] - visit : bool[][] """ import sys sys.setrecursionlimit(10 ** 6) INF = sys.maxsize input = sys.stdin.readline N, M = map(int, input().split()) map = [list(map(int, input().rstrip())) for _ in range(N)] visit = [[False] * M for ..

처음에는 플로이드로 풀었다. """ 1. 아이디어 - 플로이드로 전체 마을 사이의 최단 경로를 구한다. - 이중 for문으로 도로의 길이의 합이 가장 작은 사이클을 찾는다. 2. 시간 복잡도 - O(V^3 + V^2) : 400 ^ 3 ~= 6억 3. 변수 - V, E : int - dist : int[][] - min_dist : int """ import sys INF = sys.maxsize input = sys.stdin.readline V, E = map(int, input().split()) dist = [[INF] * (V + 1) for _ in range(V + 1)] for l in range(1, V + 1): dist[l][l] = 0 for _ in range(E): a, b, c..

최초의 풀이는 조금 복잡하게 접근하였다. """ 1. 아이디어 - 백트래킹으로 전수를 조사한다. - for문을 돌릴 때 마지막으로 선택한 선수보다 높은 번호의 선수들을 대상으로 한다. - 전체를 대상으로 돌리는게 아니라 N/2만큼 돌린다. (대칭이므로) - 깊이가 N/2에 도달하면 선택한 팀 구성을 대상으로 각각 팀의 능력치를 구한다. - 비교하여 현재 갖고 있는 최소값보다 작으면 교체한다. 2. 시간 복잡도 - NCN/2 * (N ** 2) = (N! / ((N - N/2)! * (N/2)!)) * (N/2 ** 2) ~= 70,000,000 -> 가능 3. 변수 - N : int - S : int[][] - 선택한 팀원 리스트 : int[] - 능력치 차이 최소값 : int """ import sys..

""" 1. 아이디어 - 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간 -> 다익스트라 2. 시간 복잡도 - O(ElgV) : 6000 * lg(500) ~= 16000 -> 가능 3. 변수 - N, M : int - 인접 리스트 : (이동 시간, 도착 도시)[][] - 최단 거리 배열 : int[] - 갈 수 있는 도시들 : heap """ import sys import heapq INF = sys.maxsize input = sys.stdin.readline N, M = map(int, input().split()) edge = [[] for _ in range(N + 1)] for _ in range(M): A, B, C = map(int, input().split()) edge[A]..

""" 1. 아이디어 - 우선 반드시 지나야 하는 두 정점 사이의 최소 거리를 구한다. (다익스트라) - 그리고 1번 정점과 v1, v2 / N번 정점과 v1, v2 사이의 거리를 구한 뒤 더 짧은 거리를 선택한다. 2. 시간 복잡도 - O(3 * ElgV) = 5 * 200000 * lg(800) =~ 2,903,089 -> 가능 3. 변수 - 정점의 개수, 간선의 개수 : int - 힙 : (비용, 노드번호) - 거리배열 : int[] - 인접 간선 리스트 : (비용, 노드번호)[] """ import sys import heapq INF = sys.maxsize input = sys.stdin.readline N, E = map(int, input().split()) edge = [[] for _ ..

""" 1. 아이디어 - 한점 시작, 모든 거리 : 다익스트라 - 간선, 인접리스트 저장 - 거리배열 무한대 초기화 - 시작점 : 거리배열 0, heap에 넣어주기 - 힙에서 빼면서 다음의 것들 수행 - 최신값인지 먼저 확인 - 간선을 타고 간 비용이 더 작으면 갱신 2. 시간복잡도 - 다익스트라 : O(ElgV) - E : 3e5 (문제에서 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..