본문 바로가기
728x90
반응형

파이썬438

[백준] 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.
[백준] 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.
728x90
반응형

티스토리툴바