[백준 1054] 특정한 최단 경로 - c++ 최단 경로 알고리즘 구현
문제 개요문제 번호: 1054제목: 특정한 최단 경로난이도: 골드 4링크: 백준 1504번문제 설명무방향 그래프가 주어진다.정점 1에서 정점 v1과 정점 v2를 통과해 정점 N으로 최단거리로 이동했을때의 거리 값을 구해야한다.지났던 정점과 간선은 다시 지나갈 수 있다.정점의 갯수 N(1 정점 a에서 정점 b의 거리의 길이 c (1 반드시 거쳐야하는 정점 v1 (v1 != N), v2 (v2 != 1) (v1 != v2)하나의 정점과 또다른 하나의 정점 사이 간선은 하나만 존재한다.접근 방법정점 1에서 정점 V1과 V2중 가장 짧은 거리인 곳으로 이동 후 해당 정점에서 시작해 선택되지 않은 정점V(1~2)로 이동하고 나서 정점 N으로 이동하는 방식을 생각했다.이때 최단거리 알고리즘인 다익스타 알고리즘을 사..
[백준 13418] 학교 탐방하기 - c++로 구현한 최소 스패닝 트리
문제 개요문제 번호: 13418제목: 학교 탐방하기난이도: 골드 3링크: 백준 13418번문제 설명학교안에 있는 모든 건물에 대한 이동 경로를 짜는 코드를 작성해야한다.최소한의 길을 선택해 모든 건물을 방문해야한다.길의 종류: 오르막길과 ( 0 ) 내리막길 ( 1 )입구 번호는 0번오르막길을 K번 오르면 피로도는 K^2피로도 계산은 최초 계산될 때 한번만 반영건물의 갯수: N (1 도로의 갯수: M (1 A 건물에서 B 건물까지 C (0은 오르막길 1은 내리막길)최악의 경로를 이용했을때 피로도와 최적의 경로를 이용했을때 피로도의 차이를 구해라접근 방법모든 건물을 방문하는 경로를 이어야하기 때문에 최소 스패닝 트리를 이용한다.간단하게 Union-Find를 이용한 크루스칼 알고리즘을 사용했다.이때 가중치는 ..
[백준 3986] 좋은 단어 - c++로 구현한 스택 (해설 O)
문제 개요문제 번호: 3986제목: 좋은단어난이도: 실버 4링크: 백준 3986번문제 설명같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓는다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 좋은단어의 갯수를 찾는 문제선을 그었을 때 교차하지 않으면 좋은 단어이다.선을 그었을 때 교차하면 좋은 단어가 아니다.접근 방법단어를 순회한다스택이 비어있다면 push지금 단어가 스택의 top에 있는 문자와 같다면 pop모든 조건이 다르다면 push단어 순회가 끝났는데 스택이 비어있다면 좋은단어구현 코드#include#include#define endl "\n"using namespace std;int main(){ i..
[백준 6198] 옥상 정원 꾸미기 - C++로 구현한 스택
문제 개요문제 번호: 6198제목: 옥상 정원 꾸미기난이도: 골드 5링크: 백준 6298번문제 설명도시에는 N개의 빌딩이 있다.i번째 빌딩의 키가 h-i이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우 = = = = - = = = = -> 관리인이 보는 방향 = - = = = = = = = = = 10 3 7 4 12..