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문을 돌릴 때 마지막으로 선택한 선수보다 높은 번호의 선수들을 대상으로 한다. - 전체를 대상으로 돌리는게 아니라 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]..

사실 이 문제를 볼 때 부분 수열을 만들 때 기존 수열의 순서를 그대로 따라야하는지가 헷갈렸다. 하지만 그렇다면 그냥 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..

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

처음에는 백트래킹으로 풀 생각을 했다.. 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)..

from collections import deque def solution(begin, target, words): answer = 0 wordsNum = len(words) visited = [0 for _ in range(wordsNum)] queue = deque() queue.append(begin) while queue: popWord = queue.popleft() if popWord == target: answer = visited[words.index(target)] break for i in range(wordsNum): if visited[i] == 0: # 아직 방문하지 않은 단어만 방문함 check = 0 for j in range(len(popWord)): if popWord[j..

경로를 표현해야해서 처음에는 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..