목록2024/05 (3)
체뚱로그
풀이 시간: 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 ≤..