본문 바로가기
728x90
반응형

백준243

[백준] 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.
[백준] 18352번 : 특정 거리의 도시 찾기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제에서 모든 도로의 거리는 1이므로 가중치가 없는 인접 리스트로 그래프를 표현할 수 있다. 인접 리스트(adjacency list)는 파이썬의 리스트를 이용해 그래프를 표현한다. 도시의 개수가 최대 300,000개, 도로의 최대 크기가 1,000,000개이므로 BFS 탐색을 활용해 문제를 시간 복잡도 안에서 해결할 수 있다. 주어지는 도로의 정보를 입력받.. 2024. 2. 2.
[백준] 1033번 : 칵테일 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1033번: 칵테일 august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다. 경근이는 인터넷 검색을 통해서 재료 쌍 N www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제에서 N - 1개의 비율로 N개의 재료와 관련된 전체 비율을 알아낼 수 있다고 한 것으로 보아 해당 문제를 그래프 관점으로 생각하면 사이클이 없는 트리 구조로 이해할 수 있다. 위 내용을 바탕으로 임의의 시작점에서 DFS를 진행하며 정답을 찾으면 해결할 수 있다. 필요한 재료의 질량을 모두 더한 값이 최소가 되어야 하므로 DFS 과정에서 유클리드 호제법을 활용해 비율들의 최소 공배수와 최대 공약수를 구해 정답에 활용한다. .. 2024. 2. 1.
[백준] 1850번 : 최대공약수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제에서 결과는 A와 B 길이의 최대공약수를 나타낸다. 즉, 3, 4의 최대공약수 1은 A(111)와 B(1111)의 최대공약수(1)의 길이로 나타내고 3, 6의 최대공약수 3은 A(111)와 B(111111)의 최대공약수(111)의 길이로 나타낸다. 위 규칙으로 해당 문제를 해결할 때는 최대공약수를 빠르게 계산할 수 있는 유클리드 호제법을 활용한다. 유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘.. 2024. 1. 31.
[백준] 11689번 : GCD(n, k) = 1 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 문제 설명 2. 풀이과정 문제에서 요구하는 GCD(n, k) = 1을 만족하는 자연수의 개수가 오일러 피 함수의 정의이다. 해당 문제는 오일러 피 함수를 잘 구현할 수 있는지 물어보는 문제라고 할 수 있다. 오일러 피 함수 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다. 오일러 피 함수의 원리를 살펴보면, 우선 구하고자 하는 오일러 범위만큼 리스트를 자기 자신의 인덱스 값으로 초기화한다. 이후 2부터 시작해 현재 리스트의 값과 인덱스가 같으면(= 소수) 현재 선택된 숫자(K.. 2024. 1. 30.
728x90
반응형

티스토리툴바