# 그래프
[그래프] 가장 먼 노드
1\. n개의 노드가 있는 그래프가 있다. 2\. 각 노드는 1부터 n까지 번호가 적혀있고, 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 한다. (가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미)3\. 1번 노드로부터
버스여행 (python)
생각보다 간단한 문제, input이 작아 어렵지 않게 풀 수 있다. DFS를 이용하여 차례로 도착할 수 있는 곳 탐색, 연쇄작용을 하는 유형
-TIL- STACK, QUEUE(자료구조)
-요즘 시대의 자바스크립트를 기반으로 한 웹개발자들에게 당장은 필요 없을 내용 -시간도 많고 자바스크립트 및 프론트 및 서버 및 디비 및 배포 등 여러 분야가 통달되었다 싶을때 학습하길 권장하는 부분 -알고리즘 문제 풀 때 도움 될 내용 -익숙해질 때까지 반복하기
최단 경로 탐색(Dijkstra's Algorithm)
그래프와 우선순위 큐를 활용하여 최단 경로를 산출해내는 다익스트라의 알고리즘에 대해 알아본다.
위상정렬 (Topological Sort)
위상정렬(Topological Sort)이란 싸이클이 없는 방향그래프(Directed Acyclic Graph, DAG)에서 정점들을 선형순서로 나열한 것을 의미한다. 아래 그림과 같이 정점에 대해 순서를 부여하는 것을 위상정렬이라고 하며, 주어진 그래프에 따라 여러
[백준] 4963: 섬의 개수
'4963- 섬의 개수' 문제로 이동! 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한
[백준] 9372: 상근이의 여행
'9372- 상근이의 여행' 문제로 이동! 상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다. 하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려고 한다.이번 방학 동안의 비행 스케줄이 주어졌을
[백준] 1068: 트리
'1068- 트리' 문제로 이동! 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.트리가 주어졌을 때, 노드 중 하나를 제거할 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오.예를 들어, 다음과 같은 트리가 있다고 하자.현재
[백준] 11725: 트리의 부모 찾기
'11725- 트리의 부모 찾기' 문제로 이동! 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에
📊.png?w=768)
[알고리즘][그래프] 그래프의 표현과 정의
그래프 그래프의 정의 정의: 그래프 G(V,E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료구조 그래프의 종류 표현하고자하는 대상에 따라 여러가지 변형된 형태가 있음 i) 정점이나 간선
[백준] 1012: 유기농 배추
'1012- 유기농 배추' 문제로 이동! 👉문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로
[백준] 2468: 안전 영역
'2468- 안전영역' 문제로 이동! 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는
알고리즘 개념 - 깊이우선탐색(DFS)
"깊이우선탐색(Depth First Search) 이란 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. "그래프 탐색이란 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다. 예를 들어
알고리즘 개념 - 너비우선탐색(BFS)
"너비우선탐색(Breadth First Search) 이란 루트 노드에서 시작해서 <span style="color:그래프 탐색이란 \*\*하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다. 예를 들어 특정도시에서 다른 도시로 갈 수 있
[백준] 1260: DFS와 BFS
'1260- DFS와 BFS' 문제로 이동! 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한
알고리즘 문제 해결 전략(문제 ID: SORTGAME)
문제 중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. 그런데, 같은 수열도 두 가지 이상의 방식으로 정렬할 수 있다. 예를 들어 3 4 1 2 는,