반응형 코테34 99클럽 코테 스터디 16일차 TIL - MST (프로그래머스 '섬 연결하기') 항해99 코테 스터디 16일차 문제인 프로그래머스의 '섬 연결하기'는 섬들을 모두 연결하기 위해 필요한 다리들의 최소 비용을 구하는 문제다. 난이도는 레벨3이며 최소신장트리 알고리즘을 통해 해결할 수 있다. 오늘의 문제 - 섬 연결하기 문제 정보문제 키워드- Greedy, MST난이도- Level 3 문제 요약섬을 연결하기 위한 다리의 건설 비용 배열이 주어진다.모든 섬이 연결되기 위해 지어야 하는 다리들의 최소 건설 비용을 구하여라. 문제 풀이 과정 그래프에서 모든 노드를 연결하는 최소 비용의 간선트리를 '최소신장트리(MST)'라고 한다.최소 신장 트리를 구하는 알고리즘 중 하나인 크루스칼 알고리즘을 이용해 문제를 풀었다.크루스칼 알고리즘은 엣지 리스트를 기반으로 트리를 병합해가므로, 먼저 주어진 비.. 2024. 6. 4. 99클럽 코테 스터디 15일차 TIL - 프로그래머스 '네트워크' 항해99 코테 스터디 15일차 문제인 프로그래머스의 '네트워크'는 노드와 엣지로 구성된 컴퓨터 네트워크 그래프에서, 연결된 네트워크의 개수를 구하는 문제다. 난이도는 레벨3이며 DFS/BFS를 통해 해결할 수 있다. 오늘의 문제 - 네트워크 문제 정보문제 키워드- DFS/BFS 난이도- Level 3 문제 요약전체 컴퓨터의 개수 n과, 각 컴퓨터간의 연결 정보 행렬 computers가 주어진다.서로 연결되어있는 컴퓨터 그룹을 하나의 네트워크라고 할 때, 몇개의 네트워크가 존재하는지를 구하여라. 문제 풀이 과정 DFS 또는 BFS를 사용하면 한 노드와 연결된 다른 노드들을 확인할 수 있다는 점을 이용하였다.아직 방문하지 않은 노드에서부터 BFS를 수행하여 연결된 노드들을 방문 표시하며, 네트워크의 개수를.. 2024. 6. 3. 99클럽 코테 스터디 12일차 TIL - DFS 항해99 코테 스터디 12일차 문제인 프로그래머스의 '여행경로'는 주어진 티켓을 가지고 모든 도시를 순회하는 경로를 구하는 문제다. 난이도는 레벨3이며 DFS나 BFS를 통해 해결할 수 있다. 오늘의 문제 - 여행경로 문제 정보문제 키워드- DFS/BFS난이도- Level 3 문제 요약티켓 정보(출발지-도착지)를 담은 배열이 주어진다.ICN(인천공항)에서 출발하여 모든 티켓을 사용해 모든 도시를 순회하는 경로를 구하여라.단, 정답이 여러개일 경우 사전순으로 더 빠른 경로를 선택해야 한다. 문제 풀이 과정 티켓 정보를 그래프라고 생각하고, ICN에서 출발하여 사전순으로 더 빠른 티켓부터 사용해가며 도시를 순회한다.사전순으로 더 빠른 티켓부터 방문하기 위해, 각 출발지에 대한 도착지 리스트를 사전순으로 정.. 2024. 5. 31. 99클럽 코테 스터디 11일차 TIL - 그래프 탐색(DFS/BFS) 항해99 코테 스터디 11일차 문제인 프로그래머스의 '퍼즐 조각 채우기'는 테이블 위의 퍼즐 조각으로 보드의 빈칸에 최대한 채우는 문제다. 난이도는 레벨3이며 DFS 및 BFS를 통해 해결할 수 있다. 오늘의 문제 - 퍼즐 조각 채우기 문제 정보문제 키워드- DFS/BFS난이도- Level 3 문제 요약퍼즐 조각들이 놓여진 테이블 배열과, 빈칸들이 뚫려있는 보드판 배열이 주어진다.퍼즐로 빈칸을 채우는데, 채울 때 모양과 크기가 딱 맞는 빈칸만 채울 수 있다. (퍼즐 회전 가능)최대로 채웠을 때 재워지는 빈칸의 칸수를 구하라. 문제 풀이 과정 먼저 퍼즐 조각과 빈칸 조각들의 개수와 크기를 구하였다.이를 구하기 위해, BFS를 사용하여 어떤 좌표가 포함된 블록의 크기를 구하는 메서드를 구현했다.각 퍼즐 조.. 2024. 5. 30. 이전 1 2 3 4 5 6 7 ··· 9 다음 반응형
