dukongmon

문제 설명n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.제한사항섬의 개수 n은 1 이상 100 이하입니다.costs의 길이는 ((n-1) * n) / 2이하입니다.임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.같은 연결..

[그래프 용어]노드(Node) = 정점 : 그래프에서 동그라미에 해당되는 부분간선(Edge) = 거리(가중치) : 그래프에서 선에 해당되는 부분오른쪽 예시에서는 4개의 노드와 5개의 엣지로 구성됨 1) Union-Find 알고리즘 (합집합 찾기)대표적인 그래프 알고리즘'합집합 찾기' 또는 '서로소 집합(Disjoint-Set) 알고리즘'이라고 불림여러개의 노드가 존재할 때, 2개의 노드를 선택해서 이 두 노드가 현재 서로 같은 그래프에 속하는지 판별하는 알고리즘 위와 같이 아직 연결되지 않은 8개의 노드가 있다고 하자현재는 각 노드가 자기 자신만을 원소로 갖기 때문에 8개의 집합이 생김이를 테이블로 만들면 아래와 같이 만들 수 있음 (= 모든 값이 자기 자신을 가리키도록 테이블 생성)테이블 첫 행은 각 ..

문제 설명n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항선수의 수는 1명 이상 100명 이하입니다.경기 결과는 1개 이상 4,500개 이하입니다.results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다...

그래프 탐색 대표 알고리즘 DFS / BFS탐색(Search)란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정코테에서 매우 자주 등장하는 유형Queue입구와 출구가 모두 뚫려있는 터널과 같은 형태FIFO(First In First Out) 구조 : 먼저 들어온 데이터가 먼저 나가는 선입선출 형식의 자료구조컨베이어 벨트처럼 들어온대로 나가는 구조!EX ) 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()⇒ 5 2 3 7 1 4 List 자료형을 이용해 기능적으로는 큐를 구현할 수 있음But, List는 시간 복잡도가 더 높아서 비효율적으로 동작할 수 있음만약 pop()으로 원소를 꺼내면 그 후에 나머지 원소들의 위치를 조정해줘야 하기 때문에 O..

그래프 탐색 대표 알고리즘 DFS / BFS탐색(Search)란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정코테에서 매우 자주 등장하는 유형Stack리스트의 한쪽 끝에서 수행되는 선형 리스트의 한가지 형태입구와 출구가 동일한 형태LIFO(Last In First Out) 구조 : 선입후출 형태로 스택에 마지막으로 입력된 자료가 제일 먼저 삭제되는 구조깊은 상자라고 생각했을 때 차곡차곡 넣는데, 마지막에 넣은걸 먼저 꺼낼 수 있는 구조!EX ) 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()⇒ 5 2 3 7 1 4 stack = []# 삽입(5)-삽입(2)-삽입(3)-삽입(7)-삭제()-삽입(1)-삽입(4)-삭제()stack.append(5..

자기 자신을 다시 호출하는 함수를 의미DFS, BFS에서 많이 사용함무한히 재귀 함수를 반복하면 어느정도 출력하다 최대 재귀 깊이 초과 메시지 출력됨RecursionError: maximum recursion depth exceeded while calling a Python object더보기추가 설명실제로 컴퓨터 시스템 상에서 함수가 재귀적으로 호출되면 컴퓨터 시스템의 스택 프레임에 함수가 반복적으로 쌓여서 가장 마지막에 호출된 함수가 처리가 된 이후에 그 함수를 불렀던 함수까지 처리되는 방식임 실제로는 스택과 같은 형태로 동작한다고 이해할 수 있음즉, 일종의 스택 자료 구조 안에 함수에 대한 정보가 차례대로 담겨서 컴퓨터 메모리에 올라가게 된다고 이해할 수 있음당연히 컴퓨터의 메모리는 한정된 크기만큼..

문제 설명ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다.따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다.캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다. 첫 번째 방법은 11개의 칸을 ..

문제 설명n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.제한사항노드의 개수 n은 2 이상 20,000 이하입니다.간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.가중치 없는 edge의 최단거리 ->..