메모: 파이썬 알고리즘 1차 강의 메모

1. 문자열 역으로 출력하기

 

s = input()
print(s[::-1])

 

 

 

 

 

2. 시간복잡도 O(root(n)) 으로 소수판별하기

 

import math
x = int(input())
answer = False
if x % 2 == 0 and x != 2:
	answer = False
else:
	for i in range(2, int(math.sqrt(x)) + 2):
		if x % i == 0:
			answer = False
			break
		else:
			answer = True
print(answer)

 

 

 

 

 

3. 최대값구하기

 

3

4 1

7 9 2

2 7 9 6

1 9 5

7 3 

9

 

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

n = int(input())
numbers = [[int(i) for i in input().split()] for _ in range(2* n - 1)]
dp = []


for i in range(2 * n - 1):
	if i < n:
		dp.append([0 for _ in range(i + 1)])
	else:
		dp.append([0 for _ in range(2 * n - i - 1,0,  -1)])


dp[0][0] = numbers[0][0]


for i in range(1, 2 * n - 1):
	for j in range(len(numbers[i])):
		
		if i >= n:
			
			max_numbers = max(dp[i - 1][j] + numbers[i][j], dp[i - 1][j + 1] + numbers[i][j])
			dp[i][j] = max_numbers
	
		else: 
        
			if j == 0:
				max_numbers = dp[i - 1][j] + numbers[i][j]
			elif j == len(numbers[i]) - 1:
				max_numbers = dp[i - 1][j - 1] +numbers[i][j]
			else:
				max_numbers = max(dp[i - 1][j - 1] + numbers[i][j], dp[i - 1][j] + numbers[i][j])
			dp[i][j] = max_numbers
	
		
		
print(dp[-1][0])

 

 

 

 

 

4. 괄호 맞추기

 

stack과 딕셔너리 이용

 

#----------중간평가 3번 괄호 짝 맞추기----------
s = input()

a = b = c = 0

answer = True
stack = []

#3가지의 닫는 괄호 각각에 대해서 매칭되는 여는 괄호를 정의한다.
d = { ')':'(', '}':'{', ']':'[' }

for x in s:

#여는 괄호라면 스택에 넣는다.
	if x == '(' or x == '{' or x == '[':
		stack.append(x)
	else:
#닫는 괄호가 나오면 스택에서 여는 괄호를 꺼내서 지금의
#닫는 괄호와 매칭이 되는지 비교한다. 
#매칭 되지 않거나, 스택이 비어 있다면 잘못된 괄호 문자열이다.
		if len(stack) == 0 or stack.pop() != d[x]:			
			answer = False
			break
		
		
#for문이 종료된 후에도
#스택에서 아직 여는 괄호가 남아있다면 잘못된 괄호 문자열이다.
if len(stack) != 0 :
	answer = False

print(answer)

 

파이썬은 null아닌 None