파이썬/코딩 테스트20

• [Do-it! 코딩 테스트-기초편] 022. 수 정렬하기 3 문제 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 접근 데이터 크기: 10,000,000 시간 제한: 5초 메모리 제한: 8MB 데이터 크기가 크고 시간에 제약이 없다면 카운팅 정렬을 사용하는 것이 좋다. 코드 import sys N = int(sys.stdin.readline()) array = [0] * 10001 for i in range(N): a = int(sys.stdin.readline()) array[a] += 1 for i in range(10.. 파이썬/코딩 테스트 2023. 11. 3.

• [Do-it! 코딩 테스트-기초편] 021. 버블 정렬 프로그램 2 - 미해결 문제 https://www.acmicpc.net/problem/1517 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 접근 코드 설명 파이썬/코딩 테스트 2023. 11. 3.

• [Do-it! 코딩 테스트-기초편] 020. 수 정렬하기 2 문제 https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 접근 데이터 크기: 1,000,000 시간 제한: 2초 정렬 알고리즘 중에 시간 복잡도가 O(N logN) 인 알고리즘 사용 heap sort 와 merge sort quick sort의 평균 시간 복잡도가 O(N logN)이라고는 하지만, 최악의 경우를 고려하면 느린 정렬에 속하기 때문에 시간 초과이다. 코드 import sys def merge_sort(arr): def sor.. 파이썬/코딩 테스트 2023. 11. 3.

• [Do-it! 코딩 테스트-기초편] 019. k번째 수 구하기 문제 https://www.acmicpc.net/problem/11004 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 접근 코드 import sys N, K = map(int, sys.stdin.readline().split(' ')) li = list(map(int, sys.stdin.readline().split(' '))) li.sort() print(li[K - 1]) 설명 def quick_sort(array, start, end): if start >= end: return pivot = start left = start + 1 right = end.. 파이썬/코딩 테스트 2023. 11. 3.

• [Do-it! 코딩 테스트-기초편] 018. ATM 인출 시간 계산하기 문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 접근 데이터 크기: 1,000 시간 제한: 1초 데이터의 크기가 크지 않기 때문에 O(N^2) 정렬을 사용해도 됨. 여기서는 삽입 정렬을 사용 코드 import sys N = int(input()) li = list(map(int, sys.stdin.readline().split(' '))) total = 0 for i in range(1, N): for j in range(i, 0, -1): if li[j] < li[j.. 파이썬/코딩 테스트 2023. 11. 3.

• [Do-it! 코딩 테스트-기초편] 017. 내림차순으로 자릿수 정렬하기 문제 https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 접근 데이터 크기: 10자리 문자열 시간 제한: 2초 데이터의 크기가 작기 때문에 선택정렬 사용 코드 N = list(input()) temp = 0 for j in range(len(N)): max_val = -1 min_index = 0 for i in range(j, len(N)): if int(N[i]) > max_val: max_val = int(N[i]) max_index = i temp = int(N[j]) N[j] = max_val N[max_index] = te.. 파이썬/코딩 테스트 2023. 11. 3.

• [Do-it! 코딩 테스트-기초편] 016. 버블 정렬 프로그램 1 - 미해결 문제 https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 접근 미해결 코드 미해결 설명 미해결 파이썬/코딩 테스트 2023. 11. 3.

• 

  [Do-it! 코딩 테스트-기초편] 015. 수 정렬하기 1 문제 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 접근 데이터 크기: 1,000 시간 제한: 1초 나열된 수를 정렬하는 방법은 여러가지가 있다. 가장 직관적이고 쉬운 방법인 버블정렬은 O(N^2)의 시간 복잡도를 갖는다. 문제의 데이터의 크기가 1,000이기 때문에 버블정렬을 사용해도 충분하다. 그리고 파이썬 list에 내장된 메서드 sort()와 비교해보도록 한다. 코드 버블정렬 N = int(input()) li = [0] * N temp = .. 파이썬/코딩 테스트 2023. 10. 30.

• 

  [Do-it! 코딩 테스트-기초편] 014. 절대값 힙 구현하기 문제 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 접근 코드 설명 알고리즘 2023.10.27 - [파이썬/알고리즘] - [자료구조] 파이썬 Queue 라이브러리 [자료구조] 파이썬 Queue 라이브러리 파이썬에서 미리 정의된 Queue 클래스를 사용할 수 있다. 총 3가지 유형의 Queue를 사용할 수 있는데, 각각 FIFO 큐, LIFO 큐, 우선순위 큐 라고 한다. Queue() 일반적인 큐, FIFO import.. 파이썬/코딩 테스트 2023. 10. 27.

• 

  [Do-it! 코딩 테스트-기초편] 013. 카드 게임 문제 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 접근 데이터 크기: 500,000 시간 제한: 2초 반복문 안에서 리스트 insert() 메서드를 사용하거나 리스트 조작을 하면 시간이 초과될 수 있다. 큐와 스택의 성질을 사용하면 쉽게 시간에 제약을 받지 않고 구현할 수 있다. 큐와 스택의 성질을 동시에 사용이 가능한 덱(Deque)을 사용해보자. 코드 from collections import deque N = int(input()) d.. 파이썬/코딩 테스트 2023. 10. 27.

• 

  [Do-it! 코딩 테스트-기초편] 011. 스택으로 수열 만들기 문제 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 접근 데이터 크기: 100,000 시간 제한: 2초 스택을 사용하는 문제이다. 어떤 수열이 입력되면, 스택 동작 push, pop 만으로 만들어질 수 있는 수열인지 알아보는 문제이다. 스택에 push되는 값은 오름차순이어야한다. 코드 N = int(input()) from_list = list(range(N, .. 파이썬/코딩 테스트 2023. 10. 26.

• 

  [Do-it! 코딩 테스트-기초편] 010. 최소값 찾기 1 - 시간초과 문제 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 접근 데이터 크기: 5,000,000 시간 제한: 2.4초 O(N^2) 무조건 시간 초과. O(NlogN)도 나오면 안됨. O(N)으로 해결 가능? 슬라이딩 윈도우 사용 윈도우의 크기는 L로 고정되어있지만 위도우 크기보다 작은 범위를 탐색하는 경우를 고려해야함. 코드 import sys N, L = map(int, sys.stdin.readline().spli.. 파이썬/코딩 테스트 2023. 10. 26.