Algorithm283 [BOJ]1753번: 최단경로 문제: https://www.acmicpc.net/problem/1753 한 정점으로부터 나머지 정점까지 최단 경로를 구해야 하니 다익스트라 문제입니다. 노드가 20,000개이니 인접행렬말고 인접리스트를 사용해야 합니다. "서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다"라는 조건은 신경쓰지 않아도 됩니다. 어차피 여러 개의 간선 중에 최소값으로 모든 경로가 갱신될테니까요. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1753.cc 2020. 7. 8. [코딩테스트 연습]다리를 지나는 트럭 문제: https://programmers.co.kr/learn/courses/30/lessons/42583 시뮬레이션 문제이므로 문제의 제약 조건만 잘 구현하면 됩니다. 1. 총 루프횟수: 다리를 통과한 트럭의 갯수 == 총 트럭의 갯수 2. 매 초마다 다리를 빠져나가는 트럭이 있는지, 대기열에 있는 트럭이 다리에 올라갈 수 있는지 체크해줍니다. 중요한 건 트럭이 여러 대 다리에 올라갈 수 있을 때 어떻게 처리하는지가 중요합니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG42583.cc 2020. 7. 7. [BOJ]4179번: 불! 문제: https://www.acmicpc.net/problem/4179 시뮬레이션 문제입니다. 같은 시점에 지훈이와 불은 같은 좌표에 있을 수 없기에, 큐에 불을 먼저 넣고, 지훈이의 좌표를 넣어줘서 불이 있는 좌표는 지훈이가 방문하지 못하도록 했습니다. R,C 제한이 크므로 BFS를 한 번만 돌아서 해결해야하는 문제입니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ4179.cc 2020. 7. 2. [BOJ]14501번: 퇴사 문제: https://www.acmicpc.net/problem/14501 모든 경우를 다 구해봐야 하므로 DP 문제입니다. 제가 세운 점화식은 다음과 같습니다. dp[day][revenue]: 특정 DAY까지 revenue를 벌었을 때의 상태를 저장했습니다. dp[day][revenue] = max(특정 day 일을 하거나, 특정 day 일을 안하거나) 이렇게 나눌 수 있습니다. 특정 day 상담 일을 한다면 다음 날짜는 day 상담기간만큼 JUMP 할 것이고 특정 day 상담 일을 안한다면 day + 1 상담을 할 지 말지 결정하는 로직으로 넘어가면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ14501.cc 2020. 7. 2. 이전 1 ··· 48 49 50 51 52 53 54 ··· 71 다음
