python 코테 준비 기본 복습 5

1085_직사각형에서 탈출

import sys
x, y, w, h = sys.stdin.readline().split()
a = [int(x), int(y), int(w) - int(x), int(h) - int(y)] 
#리스트에 append하지 말고 바로 대입하기.

• min 함수의 활용

x,y,w,h=map(int,input().split())
print(min(x,y,w-x,h-y))

15649_N과M(1)

• list를 str으로 합쳐 출력 (out이 리스트)

print(' '.join(map(str,out)))

• 리스트에 있는 모든 요소 출력

Print(*list1)

• 리스트를 sorted한 것을 스트링에 삽입.

out_str = ' '.join(map(str, sorted(out)))

10844_쉬운 계단수

• 다이나믹 프로그래밍은 배열을 쓴다. 어떤 경우에는 2차원 배열이 필요한 경우도 있음.

import sys
n=int(sys.stdin.readline())
stair_numbers=[[0 for i in range(10)] for _ in range(101)] 
#1의자리수 :각 인덱스
stair_numbers[1]=[1,1,1,1,1,1,1,1,1,1]
for i in range(2,101):
    for j in range(10):
            if 1 <= j <= 8:
                stair_numbers[i][j] = stair_numbers[i-1][j-1] + stair_numbers[i-1][j+1]
            elif j == 0:
                stair_numbers[i][j] = stair_numbers[i-1][1]
            elif j == 9:
                stair_numbers[i][j] = stair_numbers[i-1][8]


print(sum(stair_numbers[n][1:10]) % 1000000000)

11053_가장 긴 증가하는 부분 수열

• 나는 dp[i]=dp[j]+1로 풀었는데, 이렇게 풀면 계속해서 작은 값마다 더해줘서 올바른 값이 안나옴. 따라서 max함수를 써서 값이 한 번만 나오게 해야함.

for i in range(0,n):
    for j in range(0,i):
        if a[j]<a[i]:
            dp[i]=max(dp[i],dp[j]+1) 
           

1931_회의실 배정

• 이중리스트에서 for문 활용하기

for i,j in a: 
	# a=[[1,2],[2,2],[1,4],[3,4],[3,5]] 일때 
	# 1,2/ 2,2/ 1,4 각각 활용
   if i>=last:
        cnt+=1
        last=j

print(cnt)

9012_괄호

• 알고리즘 ->단순히 나는 ‘(‘개수와 ‘)’개수가 같으면 된다고 풀었다. 이러면 안됨. 반례:))((

def solve(string):
    stack=[]
    for i in string:
        if i=='(':
            stack.append(i)
        else:
            if len(stack)==0:
                return 'NO' # ')' 한 개 있는 경우 예외 처리.
            else:
                stack.pop() # ’)’이 나오면 ‘(‘를 제거한다.

    if len(stack)==0:
        return "YES"
    else:
    `	return "NO"

2164_카드 2

• while문 실수

while len(q)!=1: # len(q)==1이 됐을 시 while문 탈출
       	q.popleft()
        a1=q[0]
        q.popleft()
        q.append(a1)

1021_회전하는 큐

• deque(덱) 모듈 선언

from collections import deque

q=deque()->활용

• deque은 바뀌면 안되므로 deque을 리스트로 변환해서 요소 값을 꺼내야 함.
  (Reference: https://security-nanglam.tistory.com/451)

que= deque([9, 10, 4, 5, 8])

for j in list(que): 
	if i==j:
    que.popleft()
    break
 

• 덱 or 리스트의 뒷 부분의 요소서부터 탐색하는 법
  ( for i in reversed(list) )

for k in reversed(list(que)): 
	if i==k:
		que.pop()
        break

• deque의 rotate 기능

deque([4, 0, 1, 2, 3])
d.rotate(1)
print('Deque.rotate(1): ', d)

#Deque.rotate(1):  deque([3, 4, 0, 1, 2])
 
d.rotate(-1)
print('Deque.rotate(-1): ', d)

#Deque.rotate(-1):  deque([4, 0, 1, 2, 3])