본문 바로가기
728x90
반응형

알고리즘39

[백준] 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.
[백준] 1016번 : 제곱 ㄴㄴ 수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 1. 문제 설명 2. 풀이과정 min의 최댓값이 1,000,000,000,000으로 매우 큰 것 같지만 실제로는 min과 max 사이의 수들 안에서 제곱이 아닌 수를 구하는 것이므로 최대 1,000,000의 데이터만 확인하면 된다. 제곱수 판별을 일반적인 반복문으로 구하면 시간 초과가 발생하므로 에라토스테네스의 체 알고리즘 방식을 제곱수 판별할 때 적용해 문제를 해결한다. 2의 제곱수인 4부터 max 값까지 제곱수를 찾는다. 제곱수를 찾을 시작 .. 2024. 1. 29.
[백준] 1747번 : 소수&팰린드롬 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 1. 문제 설명 2. 풀이과정 에라토스테네스의 체를 이용하여 최대 범위에 해당하는 소수를 모두 구해 놓고 소수인 수들 중 N보다 크거나 같으면서 팰린드롬 수인 것을 찾아내면 되는 문제이다. 소수를 구하는 것은 에라토스테네스의 체로 쉽게 구할 수 있지만 팰린드롬 수를 판별할 때는 숫자의 값을 각 자릿수 별 리스트의 형태로 바꿔 판별해야 한다. N의 범위는 1~1,000,000인데, 정답은 N보다 같거나 커야 한다. 최대 범위를.. 2024. 1. 28.
[백준] 1456번 : 거의 소수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 최대 범위에 해당하는 모든 소수를 구해 놓고, 구한 소수들의 N제곱값이 입력된 A와 B 사이에 존재하는지 판단해 문제를 해결할 수 있다. 입력에서 주어진 범위의 최댓값 10^14의 제곱근인 10^7까지 최대로 소수를 탐색해야 하는데 에라토스테네스의 체를 이용하여 빠르게 소수를 먼저 구한다. 이후 구한 소수들의 N제곱값이 A와 B 범위 안에 존재하는지 판별해 거의 소수의 개수를 구하면 문제를 해결할 수 있다. 슈도코드 A(시작 수).. 2024. 1. 26.
[백준] 1744번 : 수 묶기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 1. 문제 설명 2. 풀이과정 문제에서 N의 최대 범위가 10,000이므로 시간 복잡도와 관련된 제약은 적다. 문제의 핵심을 생각해 보면 가능한 큰 수들끼리 묶어야 최종 결괏값이 커진다는 것을 알 수 있다. 또한 음수가 들어올 수 있으므로 음수와 음수를 곱하면 양수가 되는 것도 잘 고려해야 한다. 입력으로 들어오는 수를 총 4가지로 구분해 보면 [음수, 0, 1, 양수]로 구분할 수 있다. 1을 따로 구분한 이유는 1을 포함하여 수를 묶는 것보다 1을 따로 더.. 2024. 1. 25.
[백준] 1715번 : 카드 정렬하기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1. 문제 설명 2. 풀이과정 문제를 잘 생각해 보면 먼저 선택된 카드 묶음이 비교 횟수에 더 많은 영향을 미치는 것을 알 수 있다. 따라서 카드 묶음의 카드 개수가 작은 순서대로 먼저 합치는 것이 전체 비교 횟수를 줄일 수 있는 방법이다. 두 개의 카드 묶음을 하나의 카드 묶음으로 합치는 것이므로 현재 카드 묶음의 카드 개수 중 가장 작은 두 카드 묶음을 선택하여 하나의 카드 묶음으로 합치고 이를 다시 현재 카드 묶음들에 포함시킨다. 위 기준으로.. 2024. 1. 24.
[백준] 1300번 : K번째 수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제에서 K의 범위가 1~min(10^9, N^2)이므로 시간 복잡도가 N^2인 알고리즘을 사용할 수 없다. 해당 문제를 이진 탐색 알고리즘으로 해결하여 중앙값보다 작은 수의 개수를 세면서 범위를 절반씩 줄이는 방법으로 K번째 수를 구한다. 중앙값보다 작은 수의 개수가 K - 1개인 중앙값이 K번째 수가 되는 것이다. 2차원 리스트는 N행이 N의 배수로 구성되어 있으므로 2차원 리스트에서의 K번째.. 2024. 1. 23.
728x90
반응형

티스토리툴바