체뚱로그

풀이 시간: 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 ≤..

풀이 시간: 1h23m18s29 + 1h20m44s32 + 42m34s25시간 복잡도: O(NMH) // H: 집의 개수공간 복잡도: O(N^2)참고 자료: https://yabmoons.tistory.com/50문제입력첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다. 둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다. 도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.출력첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.문제 풀이초기 고민..

풀이 시간: 2h12m17s71시간 복잡도: O(N^2*L)공간 복잡도: O(N^2)문제입력첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.출력첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.문제 풀이전체 코드#include #include #include using namespace std;int N, L, ans = 0;vector cnt1, cnt2;int arr1[101][101] = { 0, };int arr2[101][101] = { 0, };vector isRoad(int arr[][101]) { vector cnt(N, true); // 각각의 길을 지나갈 수 있는..