[2023 알고리즘 스터디] 2조

by

FOSCAR 알고리즘 연구 5주차 그룹 2 블로깅

백준 #23882: 알고리즘 클래스 – 선택 정렬 2

https://www.acmicpc.net/problem/23882

'추천 관련글,

#23882: 알고리즘 수업 – 정렬 선택 2

첫 번째 줄은 배열 A의 크기 N(5 ≤ N ≤ 10,000)과 교환 횟수 K(1 ≤ K ≤ N)를 제공합니다.
다른 배열 A의 요소 A1, A2, …, AN은 다음 줄에 지정됩니다.
(1 ≤ AI ≤ 109)

www.acmicpc.net

# a: 배열 크기 k: k번째 교환
a, k = map(int, input().split())

# 배열 int형으로 저장
num_list = (int(i) for i in input().split())

num_list_sorted = sorted(num_list)

# 교환 횟수
count = 0

for i in range(a-1, 0, -1):
    idx = num_list.index(max(num_list(:i+1)))
    if idx !
= i:
        num_list(idx), num_list(i) = num_list(i), num_list(idx)
        count += 1
        if count == k:
            for j in num_list:
                print(j, end=' ')
                
if k > count:
    print(-1)

베이크준 10989번호: 정렬 번호 3

https://www.acmicpc.net/problem/10989

10989: 분류 번호 3

첫 번째 줄에는 숫자 N(1 ≤ N ≤ 10,000,000)의 개수가 포함됩니다.
번호는 두 번째 줄부터 시작하여 N줄로 제공됩니다.
이 숫자는 10,000보다 작거나 같은 자연수입니다.

www.acmicpc.net

import sys

# 입력 10,000개보다 작거나 같은 자연수
n = int(sys.stdin.readline())
# idx 값이기 때문에 +1해서 10001개 생성
arr = (0)*10001

for _ in range(n):
    num = int(sys.stdin.readline())
    arr(num) += 1

for i in range(10001):
    if arr(i) !
= 0:
        for _ in range(arr(i)):
            print(i)


이 문제의 핵심은 메모리 크기오전. 파이썬에 내장된 함수인 sort() 함수로 문제를 풀면, 기억으로부터답이 틀리게 됩니다.
이 문제 정렬 카운팅해결

베이크준 2751번호: 정렬 번호 2

https://www.acmicpc.net/problem/2751

2751호: 분류번호 2

숫자 N(1 ≤ N ≤ 1,000,000)의 수는 첫 번째 줄에 있습니다.
번호는 두 번째 줄부터 시작하여 N줄로 제공됩니다.
이 숫자는 절대값이 1,000,000보다 작거나 같은 정수입니다.
숫자가 겹치지 않습니다.

www.acmicpc.net

import sys

n = int(sys.stdin.readline())

num_list = ()
for _ in range(n):
    num_list += ((int(sys.stdin.readline())))

for i in sorted(num_list):
    print(i)


충분한 메모리를 제공하는 대신 문제 10989와 비교 시간 제한입력() 함수 대신 sys.stdin.readline() 함수사용되었다 sys.stdin.readline()과 달리 input() 함수는 새 줄이 제거된 값을 프롬프트하고 반환하기 때문에 느립니다.

베이크준 11650굽기: 좌표 정렬

https://www.acmicpc.net/problem/11650

#11650: 좌표 정렬

포인트 수 N(1 ≤ N ≤ 100,000)은 첫 번째 줄에 표시됩니다.
점 i의 위치 xi와 yi는 두 번째 줄부터 N개의 줄에 지정됩니다.
(-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이며 두 점이 같은 위치에 있지 않습니다.

www.acmicpc.net

# n: 점의 개수
n = int(input())

# x, y 좌표 리스트에 담기
xy_list = ()
for _ in range(n):
    a, b = map(int, input().split())
    xy_list += ((a, b))

# xy_list 오름차순으로 정렬
xy_list.sort()

# 정렬된 xy_list에서 x좌표, y좌표 출력
for xy in xy_list:
    print(xy(0), xy(1))

sort()를 사용할 때 배열이 2차원인 경우 첫 번째 키 값이 같으면 다음 키 값은 자동입니다.
정렬 기준