Algorithm [25-26 March]

Python Coding Test

1

import math

W, R = map(int, input().split())
result = math.trunc(W * (1 + R / 30))
print(result)

2

import sys
input = sys.stdin.readline

N = int(input())

for i in range(N):
	for j in range(N):
		print("*", end="")
	print()

3

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

for _ in range(N):
	for _ in range(M):
		print("*", end="")
	print()

4

# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean
from sys import stdin
input = stdin.readline

N, M, X = map(int, input().split())
H = list(map(int, input().split()))
Q = int(input())
D = input().split()

total = 0
position = X - 1
# 가장 최근 벌목 시점의 높이를 저장해 지나간 시간과 함께 현재 높이를 측정
last_cut = [0] * N 

# 매 벌목때마다 모든 나무를 계산하면 시간적 효율성이 떨어지므로 현재 위치의 나무만 계산하고
# 다음 위치의 나무 높이는 지나간 시간만큼 그때 그때 처리하면 효율적으로 보임
for time in range(Q):
	current_height = H[position] + time - last_cut[position]
	
	if current_height >= M:
		total += current_height
		H[position] = 0
		last_cut[position] = time
		
	if D[time] == 'R':
		position = (position + 1) % N
	elif D[time] == 'L':
		position = (position - 1 + N) % N
		
print(total)

Sorting Algorithms

Algorithm	Description	Time Complexity	Best Use Case
Bubble Sort	Repeatedly swaps adjacent elements if they are in the wrong order	O(n²) / O(n²)	Simple and small datasets, easy to implement
Selection Sort	Finds the smallest element and swaps it with the first unsorted element	O(n²) / O(n²)	When memory swaps are expensive but comparisons are not
Insertion Sort	Builds a sorted array one element at a time by inserting it into the correct position	O(n²) / O(n²)	Small or nearly sorted datasets due to its adaptive nature
Merge Sort	Divides the array into halves, sorts them, and merges them back	O(n log n) / O(n log n)	Large datasets, stable sorting, linked lists.
Quick Sort	Picks a pivot, partitions elements around it, and recursively sorts	O(n log n) / O(n²)	Fast in practice, best for general-purpose sorting
Heap Sort	Uses a binary heap to repeatedly extract the smallest/largest element	O(n log n) / O(n log n) Priority queues, when sorting in-place is required
Counting Sort	Uses an auxiliary array to count occurrences of each element.	O(n + k) / O(n + k)	Small integer ranges, when stable sorting is needed
Radix Sort	Sorts numbers digit by digit using a stable sorting algorithm	O(nk) / O(nk)	Large integers or fixed-length strings
Bucket Sort	Divides elements into buckets and sorts each bucket separately	O(n + k) / O(n²)	Uniformly distributed floating-point numbers

1

import sys
input = sys.stdin.readline

arr = [1, 5, 2, 7, 6, 2]

# sorted() 함수를 사용한 정렬
# sorted() 함수는 원본 리스트를 변경하지 않고 정렬된 새로운 리스트를 반환합니다.
sorted_arr = sorted(arr)


# 리스트의 sort() 메소드를 사용하여 직접 정렬
# sort() 메소드는 원본 리스트 자체를 정렬하여 변경합니다.
arr.sort()
print(*arr) 


arr2 = [1, 5, 2, 7, 6, 2]
#sort() 메소드에 정렬 조건(키)를 지정하여 정렬하기
# 아래 예제는 내림차순 정렬을 위해 각 요소에 -1을 곱하는 람다 함수를 사용합니다.
arr2.sort(key = lambda x : -x)
print(*arr2)

2

import sys
input = sys.stdin.readline

arr = [[1, 1], [2, 3], [3, 1], [4, 3], [5, 2], [6, 4]]
# arr1 = sorted(arr, key = lambda x : (-x[1], x[0]))
# print(*arr1)
'''
배열의 두 번째 요소가 더 클 수록 우선 순위가 높고, 그 값이 간다면 첫 번째 요소가 더 작을 수록 우선 순위가 높게 정렬하시오.
'''
arr.sort(key = lambda x : (-x[1], x[0]))
print(*arr)

3

import sys
input = sys.stdin.readline

N = int(input())
islands = []
for i in range(N):
	x, y = map(int, input().split())
	islands.append(((x, y), i))

# 좌표를 기준으로 오름차순 정렬했을 때, 뒤쪽에 위치한 섬들을 약탈할 수 있다.
# print(islands)
islands.sort()
# print(islands)
# 1번부터 차례대로 결과를 출력해야 하기 때문에, 결과를 저장할 배열을 만들어 준다.
res = [0] * N

# 정렬한 섬 순서대로, 자신보다 뒤쪽에 위치한 섬들의 개수를 res에 섬의 인덱스의 맞게 저장한다.
for i in range(N):
	(x, y), idx = islands[i]
	res[idx] = N - i - 1

for i in range(N):
	print(res[i])

4

import sys
input = sys.stdin.readline

# 10진수 n을 2진수로 나타냈을 때의 1의 개수를 반환하는 함수
def count_one(n):

	# 10진수 n을 2진수로 변환할 때는 n이 0이 될 때까지 2로 나누면서
	# 나오는 나머지들을 거꾸로 나열해야 한다.
	# 이때, 단순히 2진수로 변환했을 때의 1의 개수를 구해야 하므로
	# n이 0이 될 때까지 2로 나누면서 나오는 나머지들을 더해주면, 1의 개수가 된다.
	ct = 0 # 1의 개수
	while n:
		ct += n % 2
		n //= 2
	return ct

N, K = map(int, input().split())
a = list(map(int, input().split()))

# 정렬할 때, 1의 개수가 1순위이며 원래 10진수의 크기가 2순위가 된다.
# 그러므로 1의 개수와 10진수로 묶어서 한 배열에 전부 담은 다음에 내림차순으로 정렬하면 된다.
lst = []
for i in range(N):
	lst.append((count_one(a[i]), a[i]))

# 
lst.sort(key = lambda x:(-x[0], -x[1]))
# K번째에 위치한 수를 출력한다.
print(lst[K - 1][1])

Recursion

1

import sys
sys.setrecursionlimit(1000)
# Python3의 경우 재귀 제한을 풀어줘야한다.
# 기본은 1000인 경우가 있고, 넉넉하게 1_000_000 정도로 숫자를 조정해주면 좋다.

def countdown(N):
	if N == 0:
		return
	print(N)
	countdown(N-1)

countdown(10)

2

import sys
input = sys.stdin.readline
from math import inf

# A의 원소로 이루어져 있으며 K보다 큰, 최솟값 찾기
def solve(now):
	global ans
	
	if now > K: # 현재 숫자가 K보다 크다면 더이상 진행할 이유가 없다. 정답을 갱신하고 중단
		ans = min(ans, now)
		return
	
	if now == 0:
		for i in range(N):
			if A[i] != 0:
				solve(A[i])
	else:			
		for i in range(N):
			# 다음 숫자를 구한다.
			next_number = now * 10 + A[i]
			if next_number > now:
				solve(next_number)

N = int(input())
A = list(map(int, input().split()))
K = int(input())

ans = inf # 초기 정답 값은 무한대로 잡는다.
solve(0)
print(ans)

3

# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean

def hanoi_top(n, start, mid, end, k):
	global count, result
	
	if count == k:
		return
	
	if n == 1:
		result[start] -= 1
		result[end] += 1
		count += 1
		return
	
	# From start to middle bar
	hanoi_top(n - 1, start, end, mid, k)
	
	if count == k:
		return
	
	# From start to end bar / the biggest one
	result[start] -= n
	result[end] += n
	count += 1
	
	if count == k:
		return
	
	# From mid to end bar
	hanoi_top(n - 1, mid, start, end, k)
	
K = int(input())
DISK_NUMBER = 20
BAR_NUMBER = 3
count = 0
result = [0] * BAR_NUMBER # start, mid, end
result[0] = sum(range(1, DISK_NUMBER + 1)) # all disks are located in the start bar

hanoi_top(DISK_NUMBER,0, 1, 2, K)

print(*result)