[백준 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를 이용한 크루스칼 알고리즘을 사용했다.이때 가중치는 ..
[백준 1647] 도시 분할 계획 - cpp로 구현한 최소 신장 트리
문제 개요문제 번호: 1647제목: 도시 분할 계획난이도: 골드 4링크: 백준 1647번문제 설명N개의 집이 있는데 연결되어있는 도로를 없애 N개의 집들을 2개의 마을 집단으로 분할해야한다.접근 방법도로를 지우는 것이 아닌 주어지는 M개의 도로에서 비용이 적은 도로를 선택한다.이때 마을1과 마을2는 서로 도로가 연결 되어 있으면 안된다. 즉 처음에 N개의 집을 각각의 집합으로 지정하고 도로를 연결할때 마다 집합을 합하여 2개의 집합으로 만들면 된다.이때 사용되는 알고리즘은 Union-Find를 이용한 크루스칼 알고리즘을 이용한다. 구현 코드#include#include#includeusing namespace std;int n, m;tuple edge[1000005];int p[100005];int fi..
[백준 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..
[백준 5397] 키로거 - C++로 구현한 연결리스트
문제 개요문제 번호: 5397제목: 키로거난이도: 실버 2링크: 백준 5397번문제 설명창영이라는 나쁜 친구가 강산이의 번호를 훔치기위해 키로거를 강산이 컴퓨터에 설치했다. 이 키로거는 강산이가 입력하는 입력 문자와 방향키(), 백스페이스(-)를 추적한다. 한줄에 입력되는 입력을 통해 강산이의 비밀번호를 알아내는 문제다.접근 방법문자열을 입력받아 문자열을 순회하면서 다음과 로직을 만든다1. ': 커서를 왼쪽으로 미룬다. -> cursor--2. '>'인 경우: 커서를 오른쪽으로 미룬다. -> cursor++3. '-'인 경우: 커서 기준으로 왼쪽 문자를 지운다.4. 문자인 경우: 커서 기준으로 오른쪽에 문자를 삽입하고 커서를 오른쪽으로 미룬다.문제 조건에서 문자열 길이가 최대 1,000,000일 수 있다..
[C++] 알고리즘을 위한 표준 입출력
scanf와 printf scanf (Scan Formatted)scanf는 표준 입력에서 형식화된 데이터를 읽어들이는 입력함수다.int a;double b;scanf("%d %lf", &a, &b);형식 지정자를 통해 입력 데이터의 타입을 지정변수의 주소를 인자로 받아 해당 메모리에 직접 값을 저장 printf (Print Formatted)scanf는 형식화된 데이터를 표준 출력으로 내보는 출력함수다.int a = 10;double b = 3.14;printf("정수: %d, 실수: %.2f\n", a, b);형식 지정자를 통해 출력 형식을 지정변수의 값을 직접 인자로 전달주요 형식 지정자:%d: 정수%f: 부동소수점 수%c: 문자%s: 문자열cin과 cout cin (Console Input)cin..