오랜만에 알고리즘을 잡으니 최소경로와 최소신장이 헷갈리고 기억도 잘 안나서 정리를 해본다. # 용어 최소경로 가중치가 없다 bfs 가장 먼저 도착하는게 최단 도착하자마자 끝내면 된다 가중치가 있다(완탐) 하나의 시작 정점에서 끝 정점까지의 최단 경로 다익스트라(dijkstra) 음의 가중치 허용x 벨만 포드(Bellman-Ford) 음의 가중치 허용 모든 정점들에 대한 최단 경로 플로이드-워샬(Floyd-Warshall) 따지고보면 다익스트라를 N만큼 반복해줘도 된다 실제로 시간복잡도도비슷하게 나옴 다익스트라Dijkstra 방식 그리디하게 진행된다. 시작점으로부터 가장 저비용인 곳을 선택하면서 최단 경로를 알아낸다. 그리디하게 해결 가능한 이유 음의 가중치가 없는 경우에 한하기 때문 배열 사용 map을 ..

3달정도 알고리즘에서 플젝하느라 알고리즘에서 거의 손을 떼고 있었더니 감이 많이 떨어졌다. 같이 플젝하던 팀원이 자기도 감이 떨어졌다면서 추천해준 문제인데 정말 화가 난다... 진짜... 오랜만에 알고리즘 푸는 사람들이 풀어야할 문제이자 너무 화가나는 문제다. 1. 문제 https://www.acmicpc.net/problem/24392 2. 문제 분석 처음엔 DFS로 풀었다. 시간 오버일 건 알고있었지만 오랜만에 DFS연습겸 + 사실 난 틀려야 제약조건이 눈에 들어온다... 역시나 시간초과. 어떻게할까 고민했다. 집 지붕 색칠문제 같은 걸로 두세번 풀어본 유형인 건 알겠는데 방법이 뭐였는지 생각이 안난다. 그리고 1000000007로 나머지 연산을 하란 것도 걸린다. 그래도 우선은 시간초과부터 해결하자..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 이해 : 백준이는 오늘로부터 N+1일에 퇴사할 예정. 남은 N일간 최대한 많이 상담을 할거다 => N일동안 최대한 벌고 나가겠다. 입력 - N(일 할 수 있는 일수) (1~15) - Ti(상담 기간) (1~5) - Pi(상담에 따른 금액) (1~1000) 시간제한이나 입력값 크기를 보면 뭘 하든 시간 제한이나 메모리 제한에 걸리진 않을 것 같다. 부분 집합으로 완전탐색을 돌릴 수도 있다. 백준의 분류로는 다이나믹으로 되어있긴한데 이번주는 순열, 조합, 부분집합 돌리는 날이라 그냥 부분집합을 썼다. 결과 출력 백준이가 얻을 수 있..