본문 바로가기
728x90
반응형

백준243

[백준] 2023번 : 신기한 소수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 재귀 함수에 자릿수 개념을 붙여 DFS를 구현하고 문제 조건에 맞도록 가지치기를 하며 문제를 해결한다. 제일 앞자리부터 모든 수가 소수이어야 하므로 우선 자릿수가 한 개인 소수 2, 3, 5, 7로 시작하는 수를 탐색한다. 두 자릿수 이상부터는 해당 수의 마지막 자릿수가 짝수이면 무조건 소수가 아니므로 짝수를 가지치기한다. 현재 수 * 10 + 새로운 자릿수를 계산하여 해당 수가 소수인지 판단하고 소수이면 재.. 2024. 1. 17.
[백준] 1517번 : 버블 소트 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제의 제목은 버블 소트이지만 N의 최대 범위가 500,000이므로 버블 정렬을 사용하면 제한 시간을 초과하게 된다. 하여 해당 문제는 버블 정렬이 아닌 O(nlogn) 시간 복잡도를 가지는 병합 정렬을 사용해야 한다. 병합 정렬에서 두 그룹을 병합하는 과정에 버블 정렬의 swap이 포함되어 있으므로 병합 정렬을 사용해 문제를 풀어도 문제의 정답인 swap 횟수를 구할 수 있다. 병합 정렬로 정렬을 하는.. 2024. 1. 16.
[백준] 11004번 : K번째 수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제을 퀵 정렬을 구현해 주어진 수를 오름차순으로 정렬하고 K번째 수를 출력하는 방법으로 해결한다면 우선 퀵 정렬에서 가장 중요한 pivot을 정하는 방법을 알아야 한다. 만약 pivot이 K라면 K번째 수를 찾은 것이다. 만약 pivot이 K보다 크다면 pivot의 왼쪽 부분에 K가 있으므로 왼쪽(s ~ pivot - 1)만 정렬을 수행한다. 만약 pivot이 K보다 작다면 pivot의 오른쪽 부분에 K가 있으므로 오른쪽(pivot + 1 ~ e)만 정렬을 수행한다. 제일 처음에.. 2024. 1. 15.
[백준] 1377번 : 버블 소트 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 버블 정렬의 swap이 한 번도 일어나지 않는 루프가 언제인지 알아내는 문제이다. 버블 정렬의 이중 for 문에서 안쪽 for 문 전체를 돌 때 swap이 일어나지 않았다는 것은 이미 모든 데이터가 정렬되었다는 의미이다. 해당 경우에는 반복을 종료하여 시간 복잡도를 줄일 수 있다. 해당 문제의 N의 최대 범위가 500,000이므로 버블 정렬로 문제를 풀면 시간을 초과할 수 있기 때문에 다른 방법으.. 2024. 1. 13.
[백준] 2559번 : 수열 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 1. 문제 설명 2. 풀이과정 문제에서 주어진 시간 제한은 1초이고 N의 최댓값은 100,000이다. 연속적인 날짜의 수가 따로 주어져 해당 날짜의 온도 합이 최대가 되는 값을 구해야 하는 문제이므로 매번 날짜의 온도 합을 구하려면 많은 시간이 소요될 것이다. 하여 투 포인터를 활용해 날짜의 온도 합을 단순 사칙연산으로 빠르게 구할 것이다. 연속적인 날짜의 시작과 끝 위치를 각각 지정하여 구간을 지정한 뒤, 첫 번째 구간의 온도 합을 저장한다. 이후.. 2024. 1. 13.
[백준] 11286번 : 절댓값 힙 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 1. 문제 설명 2. 풀이과정 N의 최대 범위가 100,000이므로 O(nlogn) 시간 복잡도 알고리즘으로 해결할 수 있다. 데이터가 새로 삽입될 때마다 절댓값과 관련된 정렬이 필요하므로 우선순위 큐를 활용해 문제를 해결한다. 하지만 해당 문제는 절댓값에 대한 정렬이 필요하므로 우선순위 큐의 정렬 기준을 직접 정의해야 한다. X = 0일 때, 큐가 비어 있으면 0을 출력한다. X = 0일 때, 큐가 비어 있지 않으면 큐에서 절댓값이 최소인 .. 2024. 1. 12.
[백준] 17298번 : 오큰수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1. 문제 설명 2. 풀이과정 N의 최대 크기가 1,000,000이므로 반복문을 사용해 오큰수를 찾으면 제한 시간을 초과하게 된다. 하여 스택을 활용해 문제를 해결하고자 한다. 오큰수가 존재하지 않는 수는 -1을 출력하므로 오큰수를 저장할 리스트를 -1로 초기화한다. 오큰수는 해당 수 다음 수들에서 찾아야 하므로 숫자들의 인덱스를 저장할 스택을 생성한다. 스택에 원소가 있고 스택의 제일 마지막 인덱스 위치의 값이 현재 인덱스 위치의 값보다 작으면(오른쪽에 있으면서 해당 값보다 큰 수 중 가장 왼쪽에 있는 수) 오큰수를 저장하는 리스트에서 스택의 제일 마지막 원소인 인덱스 위치에 해당 값을 저장한다. 현재 인덱스를 스택의 제일 마지막 원소로 추가한다. 해당 과정을 제일 마지막 인덱스까지 반복하며 오큰수를 .. 2024. 1. 11.
[백준] 11003번 : 최솟값 찾기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 일정 범위 안에서 최솟값을 구하는 문제로 슬라이딩 윈도우와 정렬을 사용하면 된다. 윈도우의 크기는 문제에서 최솟값을 구하는 범위가 i - L + 1부터 i까지이므로 L로 생각하면 된다. 최솟값을 찾기 위한 정렬을 O(nlogn)의 시간 복잡도를 가지므로 N과 L의 최대 범위가 5,000,000인 해당 문제에서는 정렬을 사용할 수 없다. O(n)의 시간 복잡도로 해결하기 위해 덱(deque).. 2024. 1. 10.
[백준] 12891번 : DNA 비밀번호 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 1. 문제 설명 2. 풀이과정 P와 S의 길이가 1,000,000으로 매우 크기 때문에 O(n)의 시간 복잡도 알고리즘으로 문제를 해결해야 한다. 부분 문자열의 길이가 P이므로 슬라이딩 원도우의 개념을 이용해 문제를 쉽게 해결할 수 있다. 슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하며 문제를 해결하는 알고리즘이다. 먼저 문자열의 시작 위치에 포인터를 하나 두고, 부분 문자열의 길이만큼 뒤에 포인터.. 2024. 1. 10.
[백준] 1253번 : 좋다 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 1. 문제 설명 2. 풀이과정 N의 개수가 2,000이라고 가정하면 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 N^2보다 작아야 한다. 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 최소 O(nlogn)이어야 한다. 하여 정렬, 투 포인터 알고리즘을 사용하여 문제를 해결할 수 있다. 단 정렬된 데이터에서 자기 자신을 좋은 수 만들기에서 제외해야 한다. 수를 입력받아 리스트 A에 저장한 후, 오름차순으로 정렬한다. 투 포인터 s, e를 배열 A 양쪽 끝에 위치시키고 A[s] + A[e]가.. 2024. 1. 9.
728x90
반응형

티스토리툴바