백준30 [백준/C++] #14284 간선 이어가기 2 (Dijsktra) 문제https://www.acmicpc.net/problem/14284 풀이간선 정보들 연결리스트로 관리하고, 최단 경로 길이 배열에 저장하고, 최단 경로 구할때 시간복잡도 줄이기 위해 우선순위 큐를 쓰는.. 가장 전형적인 다익스트라 문제였다.다익스트라 문제들은 거의 풀이 형태가 같으니 한번 제대로 익혀놓는걸 추천한다!#include #include #include #define INF 987654321using namespace std;/*특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되도록 추가하는 간선의 순서를 조정-> 최솟값은? */int n; // 정점의 개수int m; // 간선 리스트의 수int s, t;vector>.. 2024. 11. 11. [백준/C++] #11057 오르막 수 (DP) 문제https://www.acmicpc.net/problem/11057 풀이1. 팩토리얼 사용해서 integerOverflow 발생한 코드: 팩토리얼을 계산하는 과정에서 숫자가 매우 커지기 때문에 long long으로도 수를 감당할 수 없게 되어 integerOverflow 발생 사용할 수의 개수만큼 0~9중에 고르기 & 마지막 자릿수 제외한 자릿수 중에 어디"까지" 특정 수가 나올지 고르기이렇게 두 로직을 combination으로 계산할 수 있다. 예를 들면, 수의 길이가 4라고 하자. 길이가 4인 수는 숫자 4개 혹은 3개 혹은 2개 혹은 1개로 오르막 수를 구성할 수 있다. 숫자 4개를 이용하는 수를 만들기 위해서는 0~9 수들 중 중복되지 않는 수 4개를 고르고(10 C 4), 마지막 자리를 제.. 2024. 11. 11. [백준/C++] #1525 퍼즐 (BFS) 문제https://www.acmicpc.net/problem/1525 구상빈칸을 움직여서 배열의 상태가 원하는 상태로 나오게끔 하는데, 이때의 최소 이동 횟수를 구하는 문제였다. 최소 이동 횟수를 구하는 것이다 보니 bfs를 이용하는 문제라는 건 인지했지만, 원하는 상태로 바꾸는 데에 있어서 빈칸을 언제까지 움직여볼 것인가에 대한 고민이 들었다. 단순하게 방문했는지의 여부를 판단하기에는 빈칸을 움직이는 순서에 따라서 상황이 다양하게 바뀔 수 있었다. 그래서 그 이전에 해당 상황에 도달한 적이 없다면, 큐에 넣는 방식을 택했다. *map의 find(key) 결과값이 map.end()값과 같다면, 원소가 없다는 뜻이다. *만일 원소가 있다면, map::iterator 를 반환하고, iterator는 -> 연.. 2024. 9. 1. [백준/C++] #4195 친구 네트워크 (Union Find) 문제https://www.acmicpc.net/problem/4195 구상친구 관계가 주어지고, 친구 네트워크에 몇 명이 있는지 구해내는 문제였다. 그래서 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하는 Disjoint Set 자료구조를 사용해야겠다 싶었고, Disjoint Set를 표현하기 위해서 Union Find 알고리즘을 사용해야했다. Union Find에서 집합(네트워크)을 구현할 때 벡터, 배열, 맵 등의 자료구조를 이용할 수 있는데, 나는 unordered map을 선택했다. 처음에 벡터를 이용하는 방식으로 구현했었는데, 불필요하게 벡터의 크기가 커졌다. 그래서 네트워크를 표현하는 딱 필요한 연결리스트만 표현하기 위해서는 map을 사용하면 좋겠다는 생각이 들었고, 데이.. 2024. 8. 28. 이전 1 2 3 4 ··· 8 다음
