ALGORITHM78 [BOJ/PYTHON] 11657. 타임머신 (최단 경로 - 벨만포드) 백준 문제 링크: https://www.acmicpc.net/problem/11657 문제 요약 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하기 이동시간이 양수면 그만큼 이동, 0이면 순간이동, 음수면 타임머신으로 시간 되돌아감 핵심 아이디어 시작점, 도착점, 시간이 주어졌기에 정점과 간선의 가중치가 주어진 상황이다. 근데 이 시간이 음수 값도 가능하기에 다익스트라로 풀 수 없다. 벨만포드로 풀면 된다. 풀이 # gold4-11657. 타임머신 import sys input = sys.stdin.readline n, m = map(int, input().split()) # 도시 개수, 버스 노선 개수 edges = [] for _ in range(m): a, b, c = map(int.. 2023. 5. 16. [BOJ/PYTHON] 18223. 민준이와 마산 그리고 건우 (최단 경로 - 다익스트라) 백준 문제 링크: https://www.acmicpc.net/problem/18223 문제 요약 마산(도착지, v번 정점)이 더 가까우면 그냥 마산으로, 최단 경로에 건우가 있으면 겸사겸사 구해줌 민준이가 찾은 최단 경로 위에 건우가 있다면 "SAVE HIM" 을 아니면 "GOOD BYE" 를 출력 핵심 아이디어 그래프 간선에 가중치가 있고, 가중치가 양수이기 때문에 다익스트라 알고리즘을 사용하면 된다. 이때, 건우를 구해준 후 마저 마산까지 가는 거리가 최단경로보다 길어지지 않으면 건우를 구하는 거라 건우를 구하러까지 가는 최단 거리, 구하고 나서 마산까지 가는 최단 거리, 출발지에서 마산까지 직통으로 가는 최단 거리값들이 필요하다. 풀이 # gold4-18223. 민준이와 마산 그리고 건우 impor.. 2023. 5. 16. [Algorithm] 구현 - 완전 탐색(Brute Force), 백트래킹 구현이란 구현: 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 완전 탐색: 모든 경우의 수를 탐색하며 다 계산하는 해결 방법 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 구현 문제 접근법 사소한 입력 조건 등을 문제에서 명시 문제 길이가 긴 편 완전 탐색 완전 탐색 문제의 조건 경우마다 따질 게 명확 특정 상태를 구성하고, 그 상태가 특정 조건을 만족하는지 검토해야 경우의 수가 모두 탐색할 수 있을 만큼 적음 시간복잡도를 생각하지 않으면 완전탐색으로 모든 문제를 풀 수 있으므로, 처음에 완전탐색 풀이를 생각한 후 차츰 최적화하는 방식도 꽤 많은 문제에서 유용함 모든 경우를 탐색하는 풀이를 생각해 봤는데 N(입력)제한이 매우 작다면 완전 탐색을 의심 완전 탐색 문제를 푸는 법 모.. 2022. 11. 13. [Algorithm] 그리디(greedy, 탐욕법) 그리디 알고리즘 그리디: 탐욕법. 어떤 문제가 있을 때 ‘현재 상황에서 지금 당장 좋은 것만 고르는 방법’으로 문제 푸는 것. 현재의 선택이 나중에 미칠 영향은 고려 X 현재 상황에서 가장 좋아 보이는 것만을 선택해도 풀 수 있는 문제 보통 정렬 기준 제시해줌: 큰 순서대로, 작은 순서대로 등 그리디 알고리즘의 정당성 풀이를 위한 아이디어 떠올리고 이것이 정당한지 검토할 수 있어야 부분 문제로 나눠서 구한 답이 전체 문제의 일부 부분적인 최적 전략을 반복적으로 하면 답이 나오는 문제 참고 이것이 취업을 위한 코딩테스트다 2022. 11. 13. [이코테 / GREEDY] 모험가 길드 문제 # 모험가 N명, 공포도 X인 모험가는 반드시 X명 이상으로 구성된 모험가 그룹에 참여해야 # 모험가 몇몇은 마을에 남아있어도 됨. # 여행 떠날 수 있는 모험가 그룹 수 최댓값 구하기 입력 출력 5 2 3 1 2 2 2 생각 '모험가 몇몇은 마을에 남아있어도 된다'는 조건 때문에 공포도가 제일 큰 사람의 경우에 포함하려고 노력 안 하고 버려도 된다. 공포도가 큰 사람은 포함 안 시키는 방향으로 간다면, 오름차순으로 정렬해주고 공포도가 1인 사람의 경우에 혼자 갈 수 있게 해주면 되지 않을까 하는 생각이 들었다. 그래서 오름차순으로 해준 후에 어떻게 할지 고민이 컸다. # 1번째 1, 1+2번째 2, 1+2+3번째가 3이면 그룹 하나씩 만들어질 수 있음. # for i in range(1, n+1).. 2022. 5. 12. [BOJ/PYTHON] 20921. 그렇고 그런 사이 # silver2-20921. 그렇고 그런 사이 import sys put = sys.stdin.readline # 왼쪽 수가 오른쪽보다 큰 경우(그렇고 그런 사이)가 k가지여야 함 n, k = map(int, put().split()) # n명, k개의 경우 만들기 answer = [] visited = [0] * (n+1) maxN = n # 첫 번째 사람한테 n번(제일 높은 값) 쪽지 주면 n-1만큼 생김 while k: if maxN - 1 그다음 제일 큰 수로 갱신 # (if문 x) 생길 수를 1 줄여서 다시 도전 maxN -= 1 for i in range(1, n+1): if not visited[i]: answer.append(i) # 낮은 수부터 순차적 배치 print(' '.join(m.. 2022. 3. 27. 이전 1 ··· 8 9 10 11 12 13 다음