[Algorithm] PS 함수 노트

들어가기 앞서

• PS 시 유용하게 사용되는 함수들을 정리합니다.

2차원 리스트를 왼쪽으로 90도 회전하기

def rotate_the_matrix_90_degree_to_the_left(a):
    n = len(a) # 행 길이 계산
    m = len(a[0]) # 열 길이 계산
    result = [[0] * n for _ in range(m)] # 회전된 결과 리스트
    # 모든 요소값을 90도 회전
    for i in range(n):
        for j in range(m):
            result[m-j-1][i] = a[i][j]
    return result

2차원 리스트를 오른쪽으로 90도 회전하기

def rotate_the_matrix_90_degree_to_the_right(a):
    n = len(a) # 행 길이 계산
    m = len(a[0]) # 열 길이 계산
    result = [[0] * n for _ in range(m)] # 회전된 결과 리스트
    # 모든 요소값을 90도 회전
    for i in range(n):
        for j in range(m):
            result[j][n - i - 1] = a[i][j]
    return result

정수가 정렬된 리스트에서, 특정 범위에 속하는 정수의 개수 구하기

from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value] 범위인 데이터의 개수를 반환하는 함수
def count_by_range(array, left_value, right_value):
    right_index = bisect_right(array, right_value)
    left_index = bisect_left(array, left_value)
    return right_index - left_index

# 정수가 오름차순 정렬된 리스트 선언
a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]

# 정수값이 4인 데이터의 개수 출력
print(count_by_range(a, 4, 4)) # 2

# 정수값이 [-1, 3] 범위에 있는 데이터의 개수 출력
print(count_by_range(a, -1, 3)) # 6

문자열이 정렬된 리스트에서, 특정 범위에 속하는 문자열의 개수 구하기

from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value] 범위인 데이터의 개수를 반환하는 함수
def count_by_range(array, left_value, right_value):
    right_index = bisect_right(array, right_value)
    left_index = bisect_left(array, left_value)
    return right_index - left_index

# 문자열이 오름차순 정렬된 리스트 선언
a = ["aab", "aba", "acd", "cba", "cda", "dac"]

# 문자열이 "acd"인 데이터의 개수 출력
print(count_by_range(a, "acd", "acd")) # 1

# 문자열이 ["aaa", "bbb"] 범위에 있는 데이터의 개수 출력
print(count_by_range(a, "aaa", "bbb")) # 3

특정 자연수의 소수 판별

import math

# 소수 판별 함수
def is_prime_number(x):
    # 2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2, int(math.sqrt(x)) + 1):
        # x가 해당 수로 나누어떨어진다면
        if (x % i == 0):
            return False # 소수가 아님
    return True # 소수임

print(is_prime_number(4))
print(is_prime_number(7))

2부터 N까지의 모든 소수 판별 (에라토스테네스의 체)

import math

# 2부터 1000까지의 모든 수에 대하여 소수 판별
n = 1000

# 처음엔 모든 수가 소수인 것으로 초기화
array = [True] * (n+1)

# 에라토스테네스의 체 알고리즘
for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
    if (array[n] == True): # i가 소수인 경우
        # i를 제외한 i의 모든 배수를 False 처리
        j = 2
        while (i * j <= n):
            array[i*j] = False
            j += 1

# 모든 소수 출력
for i in range(2, n+1):
    if array[i] == True:
        print(i, end = ' ')

참고

• 이것이 취업을 위한 코딩 테스트다. with 파이썬