https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 3가지 수정사항을 제외하고 다익스트라 알고리즘을 그대로 활용해 풀이했습니다. (1) 간선이 양방향이므로 graph에 정보를 저장할 때 두 가지 방향을 모두 저장했습니다 (2) 간선에 weight가 없으므로 일괄적으로 1로 통일했습니다 (3) 마지막에 답을 반환할 때 1번 노드를 제외한, 2번에서 마지막 노드까지의 거리 중 최댓값을 구하고, 이 최댓값과 같은 거리를 갖는 노드의 개수를 반환하도록 했습니다 import heapq def..

https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 2가지 수정사항을 제외하고 다익스트라 알고리즘을 그대로 활용해 풀이했습니다. (1) 하나의 도로에서 양방향으로 이동 가능하므로, graph를 만들 때 양방향 정보를 모두 저장했습니다 (2) 마지막에 답을 구할 때 주어진 K 이하의 시간이 걸리는 마을의 개수를 세서 반환했습니다. import heapq def solution(N, road..

https://programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr 먼저 단어의 길이가 key, 해당 길이의 단어들의 리스트를 value로 갖는 word_dict를 생성합니다. 같은 방식으로 단어의 앞뒤를 뒤집은 reversed_word_dict도 생성합니다. matching_dict라는 딕셔너리를 만들어 key는 하나의 쿼리, value는 해당 쿼리에 매칭되는 단어의 개수를 저장합니다. 이후 queries를 하나씩 꺼내면서 현재의 쿼리가 ?로만 이루어져 있으면 해당 쿼리 길이의 단어들의 개수를 matching_dict에 저장합니다. 쿼리가 ?를 접미사로 가지면, 해당 쿼리 길이의 단어들을 array, tar..

https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr DFS를 수행하는 함수 dfs를 정의하고, 모든 컴퓨터를 방문할 때까지 dfs를 반복합니다. 우선 0번째 컴퓨터부터 시작해서 이와 직/간접적으로 연결되어 있는 모든 컴퓨터들 방문합니다. 이후에도 아직 방문하지 않은 컴퓨터가 있으면 answer를 하나씩 증가시키고, 방문하지 않은 컴퓨터 중 번호가 가장 작은 것에서부터 시작해 다시 dfs를 호출합니다. 모든 ..

https://programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 먼저 num2rank 딕셔너리를 정의해 일치한 숫자의 개수를 로또 순위로 매핑할 수 있게 했습니다. sames 변수엔 lottos와 win_nums에서 겹치는 숫자의 개수를, zeros에는 lottos에서 0의 개수를 저장했습니다. 최고 순위는 0이 모두 당첨번호와 일치하는 겨우, 최저 순위는 0이 아무 당첨번호와도..

https://programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr from math import gcd def solution(w,h): # 최대공약수 gcf = int(gcd(w,h)) # 약분 abb_w = w//gcf abb_h = h//gcf # 망가진 사각형 개수 messed_squares = (abb_w + abb_h - 1) * h // abb_h return w * h - messed_..