728x90 반응형 알고리즘39 [백준] 1753번 : 최단경로 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 시작점과 다른 노드와 관련된 최단 경로의 경로값을 구하는 문제이다. 다익스트라 알고리즘의 가장 기본적인 형태를 구현할 수 있는지 물어보는 문제라고 할 수 있다. 다익스트라 알고리즘의 핵심 이론 인접 리스트로 그래프 구현하기 인접 리스트에 연결한 데이터 자료형은 [노드, 가중치] 같은 형태로 선언하여 연결한 점도 잘 봐야 한다. 최단 거리 리스트 초기화하기 출발 노드는 0, 이외의 노.. 2024. 3. 10. [백준] 1948번 : 임계경로 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제에서는 출발 도시와 도착 도시가 주어지기 때문에 일반적인 위상 정렬이 아닌 시작점을 출발 도시로 지정하고 위상 정렬을 수행하면서 출발 도시에서 도착 도시까지 거치는 모든 도시와 관련된 임계 경로값을 구할 수 있다. 단, 해당 문제의 핵심은 1분도 쉬지 않고 달려야 하는 도로의 수를 구하는 것인데, 이를 해결하려면 에지 뒤집기라는 아이디어가 필요하다. (에지 뒤집기 아이디어는 그래프 문제에서 종종 .. 2024. 3. 9. [백준] 1516번 : 게임 개발 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제를 해결하기 위해선 어떤 건물을 짓기 위해 먼저 지어야 하는 건물이 있을 수 있다는 문장에 주목해야 한다. 각 건물을 노드라고 할 때, 그래프 형태에서 노드 순서를 정렬하는 위상 정렬 알고리즘을 사용하는 문제라는 것을 알아야 한다. 건물의 수가 최대 500, 시간 복잡도가 2초이므로 시간 제한 부담은 거의 없다. 입력 데이터를 바탕으로 필요한 자료구조를 초기화한다. 인접 리스트로 그래프를 표현하고 건물의 생산 시.. 2024. 3. 2. [백준] 2252번 : 줄 세우기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 학생들을 노드로 생각하고, 키 순서 비교 데이터로 에지를 만든다고 생각했을 때 노드의 순서를 도출하는 가장 기본적인 문제이다. 답이 여러 개일 때 아무것이나 출력해도 된다는 전제는 위상 정렬의 결괏값이 항상 유일하지 않다는 알고리즘의 전제와 동일하다는 것을 알 수 있다. 위상 정렬(topology sort) : 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 위상 정렬.. 2024. 2. 24. [백준] 1043번 : 거짓말 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제의 핵심은 파티에 참석한 사람들을 1개의 집합으로 생각하고, 각각의 파티마다 union 연산을 이용해 사람들을 연결하는 것이다. 해당 과정을 수행하게 되면 1개의 파티에 있는 모든 사람들은 같은 대표 노드를 가리키게 된다. 이후 각 파티의 대표 노드와 진실을 알고 있는 사람들의 각 대표 노드가 동일한지 find 연산을 이용해 확인하여 과장된 이야기를 할 수 있는지 판별한다. 우선 진실을 아는 사람의 데이터, 파티 데이터, 유니온 파인.. 2024. 2. 16. [백준] 1976번 : 여행 가자 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 도시의 연결 유무를 유니온 파인드 연산을 이용해 해결할 수 있다. 유니온 파인드는 그래프 영역에서 많이 활용되지만, 해당 문제와 같이 단독으로도 활용할 수 있다. 문제에서는 도시 간 연결 데이터를 인접 행렬의 형태로 주기 때문에 인접 행렬을 탐색하면서 연결될 때마다 union 연산을 수행하는 방식으로 문제에 접근한다. 도시와 여행 경로 데이터를 저장하고 각 노드와 관련된 대표 노드를 저장한 리스트를 생성한다. 대표 노드.. 2024. 2. 14. [백준] 1717번 : 집합의 표현 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제에서 최대 원소의 개수 1,000,000과 질의 개수 100,000이 큰 편이므로 경로 압축이 필요한 전형적인 유니온 파인드 문제이다. 유니온 파인드(union-find)는 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성된 알고리즘이다. union 연산 : 각 노드가 속한 집합을.. 2024. 2. 13. [백준] 2251번 : 물통 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 1. 문제 설명 2. 풀이과정 지금까지 접해 봤던 그래프 데이터를 저장하고 저장한 자료구조를 이용하는 방식과 달리, 그래프 원리를 적용해 그래프를 역으로 그리는 방식으로 접근하는 문제이다. A, B, C의 특정 무게 상태를 1개의 노드로 가정하고, 조건에 따라 이 상태에서 변경할 수 있는 이후 무게 상태가 에지로 이어진 인접한 노드라고 생각하고 문제를 해결하면 된다. 처음에는 물통 A, B가 비어 있고, 물통 C는 꽉 차있는 상태이므로 해당 .. 2024. 2. 8. [백준] 1707번 : 이분 그래프 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 1. 문제 설명 2. 풀이과정 노드의 집합을 2개로 나누는데, 인접한 노드끼리 같은 집합이 되지 않도록 적절하게 임의로 분할할 수 있다고 한다. 트리의 경우에는 항상 이분 그래프가 된다는 것을 알 수 있는데, 사이클이 발생하지 않으면 탐색을 하면서 다음 노드를 이번 노드와 다른 집합으로 지정하면 되기 때문이다. 하지만 사이클이 발생했을 때 이분 그래프가 불가능할 수도 있다. 이런 경우에는 기존의 탐색 메커니즘에서 탐색한 노드에 다시 접근하게 되었을 때 현재 노드.. 2024. 2. 6. [백준] 1325번 : 효율적인 해킹 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1325번: 효율적인 해킹첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한www.acmicpc.net 1. 문제 설명2. 풀이과정주어진 제한 시간에 비해 N과 M의 크기가 작은 편이므로 시간 복잡도와 관련된 제약은 크지 않은 편이다.하지만 해당 문제에서 잘 확인해야 할 부분은 신뢰 관계 A, B는 A가 B를 신뢰한다는 것이다.또한 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터는 신뢰를 가장 많이 받는 컴퓨터이다.그래프의 노드와 에지를 기준으로 이해하면 A라는 노드에서 탐색 알고리즘으로 방문하는 노드가 B, C라고 하면 B, C는 A에게 신뢰.. 2024. 2. 5. 이전 1 2 3 4 다음 728x90 반응형
