본문 바로가기
반응형

[알고리즘 + 자료구조]43

BFS와 다익스트라의 차이와 다익스트라 분석 BFS와 다익스트라는 최단거리를 구한다는 점에서 의미가 동일하다. 그렇다면 언제 BFS를 쓰고, 언제 다익스트라를 써야할까? BFS는 간선 간의 거리가 모두 같을 때 사용하며, 다익스트라는 간선 간의 거리가 다를 때 사용한다. 주의해야할 점은, 다익스트라 특성상 간선이 음수일 경우에는 알고리즘이 적용될 수 없다. 다익스트라 코드를 보면 크게 두 가지 부류가 있다 #include #include #include #include using namespace std; typedef pair pii; void dijkstra(int start, vector& graph, vector& distance) { int n = graph.size(); priority_queue pq; distance.assign(n,.. 2023. 11. 22.
[알고리즘] Floyd Warshall digraph(방향이 있는 그래프) G에서, A -> B로 가는 경로가 있고, B -> C로 가는 경로가 있다면 A -> C로 가는 경로도 존재한다는 Transitive closure를 계산하는 문제이다. 그래프 G에서 이러한 관계를 모두 연결해 준 그래프를 G* 이라고 부를 때, G*을 G의 transitive Clousre라고 한다. 이는 dfs를 n번 적용하여 문제를 해결할 수도 있지만, 문제가 인접행렬로 주어질 경우, Floyd Warshall 알고리즘을 이용하여 Transitive Closure를 구하는 것이 구현이 쉽다. // i는 phase이다. // 총 N번의 phase가 있는 것이다. for(int i = 0; i < N; i++) { // j는 아래로 쭉 내려가는 인덱스를 의미한다. 내.. 2022. 10. 26.
C++ 2차원 배열 회전하기 이런 방법을 깨닫게 되다니.. 써먹을 일이 많을 것 같다. 이론에 대한 자세한 방식은, 아래 블로그에서 너무나도 잘 설명해 주고 있다! https://taaewoo.tistory.com/10#memmove-%--%EB%B-%B-%EC%--%B-%--A%--%EC%-B%-C%EC%-E%--%--%EC%A-%BC%EC%--%-C%-C%--%EB%B-%B-%EC%--%B-%--B%--%EC%-B%-C%EC%-E%--%--%EC%A-%BC%EC%--%-C%-C%--%ED%--%AC%EA%B-%B-%--- 위 블로그에서는, 시계방향 90도 회전을 다루고 있는데 나는 이를 토대로 반시계방향 90도에 대해서 구현해 보았다. 5 x 5의 A배열을, 반시계방향으로 90도 회전시킨 B배열을 얻고 싶을때 A배열의 1행만 생.. 2022. 10. 6.
[C++] 정규표현식, 정규식 유형 알아보기 [01]{3} : 0이나 1숫자가 3번 \d{3,4} : 정수가 3개나 4개 \d : 정수가 4개 \\d 이런식으로 한 이유는, 문자열 string 내에서 \를 문자 그대로 인식시키기 위해서다. #include #include #include using namespace std; int main() { vector phone = {"010-4234-1144", "010-1424-4423", "012-1423-1424", "010-132-1442", "010-1234-132"}; regex r("[01]{3}-\\d{3,4}-\\d{4}"); smatch match; for(auto a : phone) { if(regex_match(a, match, r)) { // cout 2022. 9. 29.
반응형

티스토리툴바