baekjoon73

• 

  baekjoon: 10989번, 수 정렬하기3(Python) 문제 정보 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 핵심 해당 문제는 시간, 메모리 제한이 걸려있는 문제이며 일반적인 입출력 함수를 사용해서는 쉽게 풀 수 없는 문제이다 따라서 sys 라이브러리를 사용하여 입출력을 진행하거나, 아니면 open(0) 처럼 표준 입출력 함수를 사용하여 문제를 풀어야 할 것이다 이번 고찰에서는 이와 같은 표준 입출력 함수에 대하여 간단하게 설명하도록 하겠다 풀이 a = [None] * 10001 b = map(int, open(0)) next(b) for i in b: if a[i] is Non.. 알고리즘/Python 2023. 5. 17.

• 백준 알고리즘: 2750번 수 정렬하기 (Python) 문제 정보 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 핵심 사실 이 문제의 핵심이 있을까? 정렬 알고리즘이 최악의 경우에도 O(N^2) 이고, 문제에서 주어진 N의 최대 개수는 1,000에 불과하므로 최악의 경우 1,000,000 (백만 번)만 반복하면 되니까 아마 최악의 경우에서도 성공이 가능하지 않을까 싶다 하지만, Java도 그랬지만 Python도 .sort() 함수를 사용하면 평균 O(NlogN)의 시간복잡도로 정렬을 수행할 수 있기 때문에 정렬 함수를 따로 구현하거나 하지 않아도 되는 쉬운 문제였던 것.. 알고리즘/Python 2023. 5. 16.

• 백준 알고리즘: 1920번 수 찾기 (Python) 문제 정보 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 핵심 단순 탐색 문제이나, 두개의 배열의 길이가 100,000으로 제한되어 있음 만일 순차 탐색으로 이 문제를 풀 경우 최대 100,000^2 번의 탐색이 필요할 수 있으므로 비효율적임 따라서 이진 탐색(Binary Search) 알고리즘을 활용하여 문제를 풀이함 풀이 # 수 찾기 N = int(input()) A = list(map(int, input().split())) A.sort() M = int.. 알고리즘/Python 2023. 5. 15.