알고리즘/BOJ 썸네일형 리스트형 1761번 1761번 - 정점들의 거리 이 문제 역시 LCA(lowest common ancestor) 를 이용해서 풀 수 있는 문제였다. 일단 간선들을 입력받고, bfs를 통해서 하나의 루트를 정해서 깊이를 체크해준다. 그다음 lca 를 구하는 방법대로 , 첫번째로 높이를 맞추고, 두번째로 높이가 맞으면 두 노드가 같아질 때 까지 반복한다. 이 때, 높이를 맞추고, 같아질 때까지 반복할때마다 간선의 가중치를 더해주면 답을 구할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828.. 더보기 11437번 11437번 - LCA 가장 가까운 공통 조상을 찾는 문제, LCA를 찾는 방법은 첫번째, 두 노드의 깊이가 같을 때까지 맞춘다 두번째, 두 노드가 같아질 때까지 함께 위로 올린다. 처음에는 bfs를 안 쓰고 union-find 를 사용했는데, 기존에 사용했던 것보다 좀 고쳐서 써야할 점이 많았고, 입력이 내 입맛대로 들어오지 않아서 시간초과가 발생했다. 한번 전부 입력받고, bfs를 통해서 각 노드들의 깊이를 다시 만들어줬다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828.. 더보기 9372번 9372번 - 상근이의 여행 문제를 자세히 읽어보면, 종류를 구하기 때문에, 모든 정점에 갈 수 있는 간선의 최소갯수를 구하면 된다. 항상 n-1개를 구해야 최소 간선 갯수가 된다.. 123456789101112131415161718192021#includeusing namespace std; int main(){ int tc; cin >> tc; while (tc--) { int n, m; cin >> n >> m; for (int i = 0; i> a >> b; } printf("%d\n", n - 1); } return 0;}cs 더보기 1197번 1197번 - 최소 스패닝 트리 이전 문제에서 MST 를 multimap 을 이용해서 풀었고, 이번 문제에서는 MST 를 우선 순위 큐를 이용해서 문제를 풀었다. 우선 순위 큐는 큰 수 부터 나오기 때문에, -1을 곱해서 작은 수 부터 나오게 해서 정답을 구했다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495#include#include#include#includeint p[10001];int r[10001];using names.. 더보기 1922번 1922번 - 네트워크 연결 MST 를 공부하면서 크루스칼 알고리즘을 배우고 풀어보았다. 크루스칼을 공부하고, sorting을 따로 하지 않으려고 map 과 iterator 를 이용해서 문제를 풀었다. 처음에는 간선이 N-1 개 일때 나와야하는데 M-1 일때 나오는 조건문을 써서 틀렸다. 두번째에는 map 은 중복적용이 되지 않는 다는 점을 잊고 map 을 사용하다가 틀렸습니다가 나왔다. 그래서 중복을 허용하는 multimap 을 이용해서 문제를 풀어서 맞을 수 있었다. 그 과정에서 구조체를 써서 문제를 풀어보았다. 평상시에 구조체를 잘 안쓰는데, 쓰면 편리한거 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424.. 더보기 14582번 14582번 - 오늘도 졌다. 정답률이 30퍼정도여서 많이 어려울거라는 생각과 다르게 쉬운 문제였다. 모든 회에서 합산값을 따지되, 울림팀은 전부다, 다른 팀은 1회 전의 합산 점수를 따지면 되는 거였다. 모든 총합은 결국 울림팀이 지기 때문에, i를 9까지만 체크해주면 됐고, 0회에는 둘다 0점으로 처리해서 1회때를 따로 예외처리 하지 않고 풀 수 있었다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include using namespace std; int a[10];int b[10];int main(){ bool ans = false; for (int i = 1; i 더보기 14726번 14726번 - 신용카드 판별 그냥 자릿수를 파악하면서 단순 계산을 통해 풀 수 있는 문제, 처음에는 string 변수를 이용해서 풀려다가, long long 으로 16자리 충분히 커버가 되므로 그냥 숫자를 이용해서 문제를 풀었다 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include#includeusing namespace std; int main(){ int tc; scanf("%d", &tc); while (tc--) { long long n; scanf("%lld", &n); long long ans = 0; int i = 0; while (n > 0) { i++;.. 더보기 10159번 10159번 - 저울 저울의 크기 비교하는 문제인데, 노드로 나타내면, 방향 그래프로 나타낼 수 있다는 점을 알 수 있다. 따라서 각 쌍이 연결이 되어있는지 여부를 파악하는 플로이드 알고리즘을 통해 풀 수 있다. 플로이드 알고리즘에서 for문 3개 중, 가장 바깥 쪽이 k 인데, 맨 처음에 풀 때, 가장 안쪽을 k 로 해서 틀렸었다. 플로이드 알고리즘 정확히 기억하기! 123456789101112131415161718192021222324252627282930313233343536373839404142#include#include using namespace std;const int INF = 987654321;int main(){ int n, m; scanf("%d%d", &n, &m); vector .. 더보기 이전 1 ··· 14 15 16 17 18 19 20 ··· 40 다음