728x90 반응형 코딩테스트39 [백준] 2343번 : 기타 레슨 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제에서 블루레이의 크기가 모두 같고 녹화 순서가 바뀌지 않아야 함이라는 문제 조건이 이진 탐색 알고리즘을 사용해야 한다는 힌트가 된다. 블루레이에 첫 레슨부터 마지막 레슨까지 저장하다 보면 지정한 블루레이 크기로 모든 레슨을 저장할 수 있는지 판단할 수 있기 때문이다. 모두 저장할 수 있다면 블루레이 크기를 줄이고 저장할 수 없다면 블루레이 크기를 늘리는 방식으로 블루레이 크기의 최솟값을 구할 수 있다. 사용할 이진 탐색의 시작 인.. 2024. 1. 22. [백준] 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. [백준] 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. [백준] 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. 이전 1 2 3 4 다음 728x90 반응형
