체뚱로그

풀이 시간: 23m38s12(초기 풀이) + 3h(오류 찾기)시간 복잡도: O(QlogQ + QlogN)공간 복잡도: O(Q + N)문제입력출력문제 풀이우선 본 문제를 크루스칼 알고리즘을 사용해 풀었다.이 문제는 다른 최소 스패닝 트리 문제와는 다르게 시간이 추가가 된다. 따라서, 코드가 약간 변형이 된다. 우선, 비용이 작은 순서대로 나열을 한다. 그리고 시간 상관없이 일단 비용을 다 더하고 모두 부모 노드를 합쳐준다. 사실 난 초반에 아주 어리석게도 비용 > 시간 > 위치 순서대로 차례대로 정렬이 되니까 어련히 그냥 tAns(출력할 시간 값)를 지금 탐색 중인 시간으로 갱신해주면 되겠지 하고 다음과 같이 구현했었다.tAns = arr[i].first.second;하지만 이는 정답이 아니었다. 일단 비..

풀이 시간: 3h57m12s90시간 복잡도: O(3^16)공간 복잡도: O(1)문제 입력첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.출력상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.문제 풀이우선 내 초기 문제 풀이는 이러하다. (오류)상어는 현재 방향의 물고기가 있는 모든 칸을 이동할 수 있다는 점에 있어서, dfs 백트래킹을 사용해야겠다고 생각했다.// 물고기 구조체 { 위치(x, y), 방향, 생존 여부 }struct ..

풀이 시간: 46m30s00시간 복잡도: O(N + MlogM + MlogN) // 입력 + 정렬 + 부모노드찾기공간 복잡도: O(N+M)참고 자료: https://medium.com/@lifthus531/%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C%EC%99%80-%EC%B5%9C%EC%86%8C-%EC%8B%A0%EC%9E%A5-%ED%8A%B8%EB%A6%AC-63053849b989문제입력입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 줄에 u v d가 주어지며 u학교와..

풀이 시간: 35m34s75(초기 코드) + 14m(시간 초과 수정)시간 복잡도: O(N*M^4)공간 복잡도: O(N+M)문제BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.- A는 B와 친구다.- B는 C와 친구다.- C는 D와 친구다.- D는 E와 친구다.위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오. 입력첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤..