1. 아이디어 ▪ 단어를 입력받은 단어로 변환할 수 있는지 확인하는 함수 작성 - for 문 돌리면서 한 글자씩 제거하고 비교했을때 같으면 True, 다르면 False ▪ target이 words에 포함되어 있지 않으면 0 return ▪ target이 words에 포함되어 있으면 dfs ▪ dfs - begin과 target이 같으면 결과리스트에 단계수 append - 아니면 for문으로 변환 가능한 단어 찾고 방문하지 않았을 경우 - 방문여부 리스트에 추가 - answer += 1 하고 변환한 단어로 dfs - 방문여부 리스트에서 제거 2. 시간복잡도 ▪ O(V+E) = O(V+V*10) 3. 변수 ▪ 방문여부 리스트: str[] ▪ 변환 단계수 저장할 리스트: int[] Code def change..

1. 아이디어 ▪ 일의 작업량 리스트를 최대 heap에 넣기 ▪ n이 0일 때까지 while문 반복 - 최대 heap에서 일의 작업량 중 가장 큰 값 꺼내기 - 꺼낸 작업량에 -1하고 다시 최대 heap에 넣기 - n -= 1 ▪ 남은 작업량의 제곱합 구해서 야근 지수 구하기 2. 시간복잡도 ▪ O(nlogm), m = works의 길이 3. 변수 ▪ 최대힙: heap Code import heapq def solution(n, works): answer = 0 q = [] for x in works: heapq.heappush(q,x*-1) while n > 0: work = heapq.heappop(q)*-1 heapq.heappush(q,(work-1)*-1) n -= 1 while q: work ..

1. 아이디어 ▪ 방문여부 리스트 초기화 ▪ for 문 돌면서 해당 컴퓨터에 방문하지 않았으면 - 네트워크 개수 += 1 - 방문여부 갱신 - 큐에 해당 컴퓨터 인덱스 넣어주기 - bfs ▪ bfs - 큐에서 값하나 꺼내오기 - 반복문 돌면서 해당 컴퓨터와 연결되어 있고, 아직 방문하지 않은 컴퓨터 찾기 - 방문 여부 갱신 - 큐에 해당 컴퓨터 인덱스 추가하기 2. 시간복잡도 ▪ O(n^2) 3. 변수 ▪ 인접행렬: int[][] ▪ 방문여부: bool[] ▪ 네트워크의 개수: int Code def solution(n, computers): chk = [False] * n answer = 0 q = [] for i in range(n): if chk[i] == False: answer += 1 chk[..

1. 아이디어 ▪ 최대 heap, 최소 heap, 이중우선순위큐에 해당 원소가 몇개 있는지 기록할 딕셔너리 초기화 ▪ operations를 하나씩 받아서 다음을 수행 - ' I 숫자'를 입력 받았을 경우 - 최대 heap과 최소 heap에 push - 해당 숫자가 이중우선순위큐에 몇개 있는지 갱신 - 'D 1'를 입력 받았을 경우 - 최대 heap에서 최대값 pull하는 while문 반복 - 꺼낸 최대값이 이중우선순위큐에 1개 이상 존재하면 해당 원소 개수 -1하고 break - 'D -1'를 입력 받았을 경우 - 최소 heap에서 최소값 pull하는 while문 반복 - 꺼낸 최소값이 이중우선순위큐에 1개 이상 존재하면 해당 원소 개수 -1하고 break ▪ 이중우선순위큐에 있는 원소만 추출해서 최대값..

1. 아이디어 ▪ 비용 리스트 0으로 초기화, 가장 처음 값은 삼각형의 꼭대기 값으로 초기화 ▪ 2중 for 문 돌면서 해당 위치 기준으로 오른쪽 아래, 왼쪽 아래 값 비용 값 갱신 - 현재 저장된 비용 값과 현재 위치에서 해당 위치로 가는 경로값을 비교한 후에 큰 값으로 갱신 ▪ 비용 리스트의 가장 마지막 행의 최대값 return 2. 시간복잡도 ▪ O(N^2) 3. 변수 ▪ 거리 비용 리스트: int[][] Code def solution(triangle): rs = [] for ls in triangle: rs.append([0] * len(ls)) rs[0][0] = triangle[0][0] for j in range(len(triangle)-1): for i in range(len(triang..

1. 아이디어 ▪ 모든 점에서 모든 점 최단 경로 -> 플로이드 ▪ 거리 비용 리스트 INF로 초기화 - 이때 자기 자신으로 가는 값은 0으로 초기화 ▪ 간선 정보 입력 받아서 거리 비용 갱신 ▪ for 문 3번 돌리면서 거쳐서 가는 비용이 작을 경우 갱신 - for 거치는 노드 - for 시작 노드 - for 끝 노드 2. 시간복잡도 ▪ O(V^3) 3. 변수 ▪ 거리 비용 리스트: int[][] Code import sys input = sys.stdin.readline INF = sys.maxsize n = int(input()) # 도시의 개수 m = int(input()) # 버스의 개수 rs = [[INF]*(n+1) for _ in range(n+1)] for i in range(n+1): ..

1. 아이디어 ▪ 시작점에서 다른 모든 점으로 최단 경로 -> 다익스트라 ▪ 간선 정보 인접리스트에 저장 ▪ 거리배열 INF로 초기화 ▪ 시작점(0,1) heap에 넣기 ▪ heap이 빌때까지 while문 반복 ▪ heap에서 꺼내온 받아온 edge가 최신 값인지 확인 - 최신값 아니면 continue - 최신값이면 - 해당 노드를 거쳐서 인근 노드로 가는 비용이 작으면 - 인근 노드로 가는 비용 갱신 - heap에 인근 노드 넣기 2. 시간복잡도 ▪ log(ElogV) 3. 변수 ▪ 최단 경로값 저장할 리스트: int[] ▪ 간선정보 인접리스트(가중치,다음노드): (int,int)[][] ▪ (가중치, 다음노드)를 저장할 heap Code import sys import heapq input = sys..

1. 아이디어 ▪ 간선을 인접리스트에 넣기 ▪ heap에 시작점 (0,1) 추가하기 ▪ heap이 빌때까지 노드를 꺼내서 다음을 반복 - 힙의 최소값을 꺼내고, 해당 노드를 방문하지 않았으면 - 방문여부 갱신 - 가중치 합 갱신 - 방문하지 않은 간선들 heap에 추가 2. 시간복잡도 ▪ O(ElogE) 3. 변수 ▪ 간선의 정보를 저장할 인접리스트 (가중치,다음노드): (int,int)[][] ▪ 방문 여부: bool[] ▪ 가중치의 합: int ▪ (가중치,노드)를 저장할 heap 4. 오답노트 ▪ 인접 리스트 만들때 양방향으로 만들어야함 Code import sys import heapq input = sys.stdin.readline V,E = map(int, input().split()) edg..