Tag: algorithms

2018
0
computer sciencealgorithms

백준[1759] - 암호 만들기

문제백준 1759 문제 보기 접근 방법이번 문제는 백 트래킹을 활용해 문제를 풀 수 있다. 입력 받은 문자열을 오름 차순으로 정렬한 뒤 백 트래킹을 실시 한다. 조합을 통해 만들어 낸 문자열의 길이가 최종 길이와 같다면 문자열 중복을 set을 활용해 피한다. 코드#include <iostream> #include <vector> #include

0
computer sciencealgorithms

백준[1261] - 알고스팟

문제백준 1261 문제 보기 접근 방법문제의 정답은 벽을 최소로 부수면서 도착지에 도착하게끔 구현해야한다. bfs로도 풀수 있을 것 같긴하나 시간 초과가 발생할 수도 있을것 같다. 따라서 다익스트라 알고리즘을 사용했다. 벽을 부수는 갯수를 해당 좌표까지 이동하는 비용으로 생각하고 문제를 풀었다. 코드#include <iostream> #include

0
computer sciencealgorithms

백준[1238] - 파티

문제백준 1238 문제 보기 접근 방법다익스트라 알고리즘을 사용하되 다시 각자의 마을로 복귀해야 하므로 다익스트라 알고리즘을 한번 더 사용한다. dis_go 배열에는 갈때의 비용을 저장하고 dis_come 배열에는 다시 돌아올때의 비용을 저장한다. 코드#include <iostream> #include <vector> #include <que

0
computer sciencealgorithms

백준[1916] - 최소비용 구하기

문제백준 1916 문제 보기 접근 방법한 정점에서 모든 정점을 최소비용으로 가는 방법을 구하는 문제이므로 이는 다익스트라 알고리즘을 활용해 해결할 수 있다. 즉, 구하고자하는 마을과 버스 노선을 그래프로 그려 이를 활용해 우선순위 큐로 문제를 해결한다. 코드#include <iostream> #include <vector> #include <

0
computer sciencealgorithms

stringstream을 활용하여 문자열 처리하기

들어가기cpp로 알고리즘 문제를 풀다보면 가끔 까다로운 input으로 시간이 오래 걸릴 경우가 있습니다. 그중 최근 겪었던 까다로운 input을 쉽게 해결하는 방법을 알아보겠습니다. 본론문자열을 쉽게 핸들링하는 방법으로 stringstream이 있습니다. 이를 활용하여 입력받은 string input을 구분하여 저장할 수 있습니다. 예를 들어 다음과 같은

0
computer sciencealgorithms

백준[2644] - 촌수계산

문제백준 2644 문제 보기 접근 방법전형적인 bfs 완전 탐색으로 문제를 해결할 수 있다. 각 가족들의 촌수를 양방향 그래프로 벡터에 저장한 뒤, 시작 노드부터 완전 탐색을 시작한다. 코드#include <iostream> #include <queue> #include <vector> using namespace std; // 구조체 작성