전체 글 (168) 썸네일형 리스트형 백준 1238 파티 https://www.acmicpc.net/problem/1238 1238번: 파티 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 www.acmicpc.net 다익스트라 알고리즘이랑 메모이제이션을 섞어서 풀었다. 이중 배열을 이용한 다익스트라 알고리즘은 시간복잡도가 O(N^2)인데 반해서 우선순위 큐를 이용하면 O(N * log N)까지 줄일 수 있다. 1. 각 점에서 X까지 최단거리를 다익스트라를 이용해서 구한다. 이 때 지나치는 정점을 활용하는 게 중요하다 예를 들어서 1 -- > 2 --> 3 --> X가 경로라면 2 --> X의 비용은 1 .. 백준 9466 텀 프로젝트 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 www.acmicpc.net 그래프 탐색과 DFS의 혼종이다. 그래프에 Cycle이 있는지 점검하는 문제다. 무식하게 풀자면 모든 노드를 DFS 돌려서 자기 자신으로 돌아오는 지 체크하면 된다! 근데 중복이 엄청 많을 것이다. 아무리 시간 복잡도가 3초라도 이런건 무조건 시간초과다 메모이제이션을 통해 최대한 중복 체크를 줄인다! 각 노드의 상태는 둘로 나뉜다. 1. 이전 DFS에서 방문한 노드 - Cycle 못 만든다. 2. 이번.. 백준 14499 주사위 굴리기 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 간단한 구현 문제다. 문제에 주어진 조건을 구현만 하면 된다. 다만 이 문제를 풀려면 제일 중요한 게 있는데 Input으로 들어오는 x,y 값이 반대다. 무슨 말인지는 밑의 코드에서 Input() 부분을 보기를 추천한다... /* 주사위 굴리기 */ #include #define MAX 21 using namespace std; i.. 이전 1 ··· 50 51 52 53 54 55 56 다음
