본문 바로가기
728x90
반응형

백준243

[백준] 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.
[백준] 2343번 : 기타 레슨 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제에서 블루레이의 크기가 모두 같고 녹화 순서가 바뀌지 않아야 함이라는 문제 조건이 이진 탐색 알고리즘을 사용해야 한다는 힌트가 된다. 블루레이에 첫 레슨부터 마지막 레슨까지 저장하다 보면 지정한 블루레이 크기로 모든 레슨을 저장할 수 있는지 판단할 수 있기 때문이다. 모두 저장할 수 있다면 블루레이 크기를 줄이고 저장할 수 없다면 블루레이 크기를 늘리는 방식으로 블루레이 크기의 최솟값을 구할 수 있다. 사용할 이진 탐색의 시작 인.. 2024. 1. 22.
[백준] 16139번 : 인간-컴퓨터 상호작용 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제를 처음 풀었을 때는 그저 입력을 받고 문자열에서 해당 범위를 추출해 그 범위에서 문자의 개수를 구하는 방식으로 해결하였다. 해당 방법으로 문제를 해결하니 50점이 나왔다. 하여 어떻게 100점으로 문제를 해결할 수 있을까 고민하던 중 누적 합으로 해결하면 시간이 더 단축될 것 같았다. a~z를 0~25번 인덱스로 생각하여 한 행이 26칸이 되도록 2차원 리스트를 생성해 주어.. 2024. 1. 20.
[백준] 1167번 : 트리의 지름 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 가장 긴 경로를 찾는 문제이다. 임의의 정점에서 가장 긴 경로로 연결돼 있는 정점은 트리의 지름에 해당하는 두 정점 중 하나라는 아이디어를 가지고 문제를 해결해 본다. 각 정점에 대한 간선의 정보를 가지고 그래프를 인접 리스트로 저장한다. 인접 리스트로 저장할 때는 [정점, 거리]의 형식으로 그래프에 저장한다. 임의의 정점 중 정점 1에서 탐색을 진행하며 각 정점 별 연결되어 있는 정점의 거리를 기록한다.. 2024. 1. 19.
[백준] 13023번 : ABCDE - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 1. 문제 설명 2. 풀이과정 N의 최대 범위가 2,000이므로 알고리즘의 시간 복잡도를 고려할 때 조금은 자유롭다. 문제에서 요구하는 A, B, C, D, E의 관계는 재귀 함수의 형태와 비슷하기 때문에 주어진 모든 노드에 DFS를 수행하고 재귀의 깊이가 5 이상(5개의 노드가 재귀 형태로 연결)이면 1, 아니면 0을 출력한다. DFS의 시간 복잡도는 O(V + E)이므로 최대 4,000, 모든 노드를 진행했을 때 4,000 * 2,000 즉, 8.000.000이므로 DFS를 사용해도 제한 시간 내에 문제를 해결할 수 있다. 그래프 데이터를 인접 리스트로 저장하고 모.. 2024. 1. 18.
728x90
반응형

티스토리툴바