생각하는 아져씨

플로이드 와샬(Floyd-Warshall)동작 과정A → 1번 노드 → B 로 가는 최단 거리 비용은?점화식시간복잡도코드참조 플로이드 와샬(Floyd-Warshall)모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용할 수 있는 알고리즘이다. 👉 최단경로를 구하는 다익스트라와 다른점은?다익스트라는 ‘한 지점에서 다른 특정 지점까지의 최단 경로’를 구하는 알고리즘인 반면, 플로이드 와샬은 모든 노드에 대한 최단 경로를 찾는 것이 목적이다.또한 다익스트라는 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾아야 하는데, 플로이드 와샬은 찾지 않아도 된다.마지막으로, 다익스트라는 최단거리를 1차원 리스트에 저장하는데, 플로이드 와샬은 2차원 리스트에 저장한다는 특징이 있다. ..

문제 정의접근 방법문제 해설풀이정리참조 https://school.programmers.co.kr/learn/courses/30/lessons/49191 문제 정의선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 returnresults 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미이다. 접근 방법순위가 정해지는 의미가 어떤 것인지 잘 파악해야 한다. 👉 순위가 정해진다 == 나 제외 모든 선수와 경기를 해서 승패가 갈렸다. 또한 i가 k를 이기고, k가 j를 이기면 i가 j를 이긴다는 연쇄적인 특징을 반영해 그래프를 업데이트 해야한다.플로이드 와샬 알고리즘을 활용해 풀 수 있다. 문제 해설[딕셔너리 사용할 경우..

https://school.programmers.co.kr/learn/courses/30/lessons/49189문제 정의n개의 노드가 있고 간선에 대한 정보가 주어진다.간선은 양방향이며, 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하려고 한다.가장 멀리 떨어진 노드란? → 최단 경로로 이동했을 때 간선의 개수가 가장 많은 노드를 의미한다. 접근 방법가장 멀리 떨어진 노드의 개수를 구하는데 최단 경로로 이동했을 때 가장 멀리 떨어진 노드이다.따라서 가장 멀리 떨어진 노드까지 최단경로로 이동 했을 때 얼만큼 떨어져있는지?를 알아야 한다. 예를 들면 소요된 거리 또는 비용이라던가? 여기서는 간선에 대한 비용이 주어져있지 않으므로, 간선의 비용을 1로 설정해서 소요 비용을 구할 수 있다.문제에서 최단경로..

14502번: 연구소https://www.acmicpc.net/problem/14502 문제 정의연구실의 바이러스 확산을 막기 위해 연구소에 벽을 세워야 한다. 연구소는 N*M 인 직사각형이고 1*1의 정사각형으로 나뉘어있다고 가정한다.연구소는 빈 칸, 벽으로 이루어져 있는데 일부 칸은 바이러스가 존재한다.0이라면 빈 칸, 1이라면 벽, 2는 바이러스가 존재함을 나타낸다.이 때 안전한 영역 크기의 최댓값을 구해야 한다. 벽은 꼭 3개만 사용할 수 있다. 접근 방법안전 영역은 벽이 세워져서 빈 칸으로 남을 수 있는 ‘0’의 개수를 세면 된다.가장 최댓값의 0의 개수를 찾아서 결과를 출력하면 된다. 일단, 벽 3개가 세워질 위치 3곳을 정해야 하는데 이것은 ‘완전탐색’으로 접근했다. 어차피 N과 M의 크기가..

트리의 순회(Tree Traversal)트리 순회 예시전위 순회(pre-order traverse): 루트를 먼저 방문한다.중위 순회(in-order traverse): 왼쪽 자식을 방문한 뒤에 루트를 방문한다.후위 순회(post-order traverse): 오른쪽 자식을 방문한 뒤에 루트를 방문한다.트리 순회 구현하기참조트리의 순회(Tree Traversal)트리 자료구조에 포함된 노드를 특정한 방법으로 한번씩 방문하는 방법이다.트리의 정보를 시각적으로 확인할 수 있다. 대표적인 트리 순회 방법은 다음과 같다.전위 순회(pre-order traverse)중위 순회(in-order traverse)후위 순회(post-order traverse) 트리 순회 예시 전위 순회(pre-order travers..

그래프 이론의 기초정점과 간선→ 정점과 간선들로 이루어진 집합을 “그래프(Graph)” 라고 한다.트리트리의 특징이진트리(Binary Tree)정 이진 트리(Full Binary Tree)완전 이진 트리(Complete Binary Tree)포화 이진 트리(Perfect Binary Tree)이진탐색트리(Binary Search Tree)이진탐색트리의 시간 복잡도는?그래프 구현과 탐색인접행렬간선 정보로부터 인접행렬 구현하기 (무향 그래프 == 양방향 그래프)인접 리스트간선 정보로부터 인접리스트 구현하기(무향 그래프)인접행렬 VS 인접리스트공간복잡도시간복잡도그래프가 희소할 때는 인접리스트, 조밀할 때는 인접행렬!맵과 방향벡터코딩테스트 문제에서 맵으로 표현된 그래프!상하좌우(4방향) 탐색과 방향 벡터방향 벡..