반응형 알고리즘80 [Python] Baekjoon - 10971. 외판원 순회 2 외판원 순회 문제는 TSP(Traveling Salesman Problem)라고 불리며 CS 분야에서 중요하게 취급된다. 백준 10971번 외판원 순회 2 문제는 TSP의 가장 일반적인 형태이다. 백트래킹과 브루트 포스 알고리즘을 통해 해결할 수 있으며 난이도는 실버 2이다. 백준 10971번 외판원 순회 2 문제 정보 알고리즘 분류 - 백트래킹, 브루트포스 난이도 - 실버 2 외판원 순회 2 문제 요약 양방향 가중치 그래프에 대해, 시작점에서 다른 모든 노드를 거쳐 다시 시작점으로 돌아오는 최단거리를 구하는 문제다. 문제 풀이 과정 DFS를 사용하여 모든 노드를 방문하고, 마지막에 다시 시작점으로 돌아오는 거리를 합하여 최단거리를 찾음 중간에 더 이상 갈 수 있는 곳이 없으면 (현재 노드에서 다른 방문.. 2021. 7. 14. [Python] Baekjoon - 8980. 택배 백준 8980번 택배는 직선 위의 마을을 순서대로 운행하는 트럭이 상자를 총 몇 개 배달하는지 맞히는 문제다. 현재 마을에서 상자를 최대한 효율적으로 담아가야 하기 때문에 그리디 알고리즘을 사용하여 해결할 수 있다. 난이도는 골드 3이다. 백준 8980번 택배 문제 정보 알고리즘 분류 - 그리디 알고리즘 및 정렬 난이도 - 골드 3 택배 문제 요약 왼쪽 첫 번째 마을부터 맨 오른쪽 마지막 마을까지 순서대로 운행하는 트럭이 있다. 각 마을에서 보낼 상자의 개수(출발 마을, 도착 마을, 개수)와 트럭의 용량이 주어질 때, 마지막 마을까지 도착한 후 배달한 총 상자의 개수를 구하는 문제다. 문제 풀이 과정 현재 마을에서 상자를 최대한 효율적으로 담아가는 그리디 알고리즘을 사용한다. 더 가까운 도착지 우선으로 .. 2021. 7. 14. [Python] Baekjoon - 1931. 회의실 배정 백준 1931번 회의실 배정 문제를 파이썬을 이용해 풀어보았다. 그리디 알고리즘을 이용한 가장 기본적인 문제이며 정렬도 이용해야 한다. 문제는 N개의 회의가 1개의 회의실을 사용하려고 할 때, 진행할 수 있는 회의의 최대 개수를 구하는 문제다. 1931번 회의실 배정 문제 정보 알고리즘 분류 - 그리디 알고리즘 및 정렬 난이도 - 실버 2 회의실 배정 문제 요약 1개의 회의실을 예약한 N개의 회의 스케줄이 주어졌을 때, 진행할 수 있는 회의의 최대 개수를 구하는 문제다. 문제 풀이 과정 가장 기본적인 그리디 알고리즘 문제이다. 전체 회의 스케줄을 끝나는 시간이 이른 회의 순으로, 끝나는 시간이 같다면 시작 시간이 이른 순으로 정렬한다. 끝나는 시간이 이른 회의 먼저 회의 가능 여부를 판단하고 회의가 가능.. 2021. 7. 13. [Python] Baekjoon - 9205. 맥주 마시면서 걸어가기 백준 9205번 맥주 마시면서 걸어가기는 그래프 탐색 알고리즘 중 BFS를 이용하여 해결할 수 있는 문제이다. 2차원 좌표평면 상에서 상근이가 맥주를 마시면서 축제장소까지 갈 수 있는 지를 구하는 문제다. 난이도는 실버 1이다. 맥주 마시면서 걸어가기 문제 정보 알고리즘 분류 - 그래프 탐색 - BFS 난이도 - 실버 1 맥주 마시면서 걸어가기 문제 요약 2차원 좌표평면 상에 상근이의 집, 축제장소, 그리고 N개의 편의점의 좌표가 주어진다. 상근이는 맥주 20병을 담을 수 있는 상자를 들고 출발하는데, 맥주 한 병을 마시면 50m를 갈 수 있다. 가다가 맥주가 모자라면 편의점에서 맥주를 구매하여 빈병을 맥주로 바꿀 수 있다. 상근이가 맥주를 마시면서 축제장소까지 갈 수 있는지의 여부를 구하여라. 문제 풀.. 2021. 7. 13. 이전 1 ··· 16 17 18 19 20 다음 반응형
