2022.02.05 ~ 02.09

02.05 토

탐색 & 시뮬레이션

✏️ 사과나무

# 사과나무(다이아몬드)
from sys import stdin

n = stdin.readline()
a = [list(map(int, stdin.readline().split())) for _ in range(n)]

res = 0
s = e = n//2
for i in range(n):
    for j in range(s, e+1):
        res += a[i][j]
    if i < n//2:
        s -= 1
        e += 1
    else:
        s += 1
        e -= 1
         
print(res)

✏️ 곳감(모래시계)

# 곳감(모래시계)
from sys import stdin

n = int(stdin.readline())

a = [list(map(int, stdin.readline().split())) for _ in range(n)]
m = int(stdin.readline())
for i in range(m):
    h, t, k = map(int, stdin.readline().split())
    if t == 0:
        for _ in range(k):
            a[h-1].append(a[h-1].pop(0))
    else:
        for _ in range(k):
            a[h-1].insert(0, a[h-1].pop())

res = 0
s = 0
e = n-1
for i in range(n):
    for j in range(s, e+1):
        res += a[i][j]
    if i < n//2:
        s += 1
        e -= 1
    else:
        s -= 1
        e += 1
print(res)

✏️ 봉우리

all() : 조건이 모두가 참일 때 참이 되는 것

# 봉우리
from sys import stdin

n = int(stdin.readline())
a = [list(map(int, stdin.readline().split())) for _ in range(n)]
a.insert(0, [0] * n)
a.append([0] * n)
for x in a:
    x.insert(0, 0)
    x.append(0)

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

cnt = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        if all(a[i][j] > a[i+dx[k]][j+dy[k]] for k in range(4))
            cnt += 1

print(cnt)

✏️ 스토쿠 검사

# 스토쿠 검사
from sys import stdin

def check(a):
    for i in range(9):
        ch1 = [0] * 10 # 행 체크
        ch2 = [0] * 10 # 열 체크
        for j in range(9):
            ch1[a[i][j]] = 1
            ch2[a[j][i]] = 1
        if sum(ch1) != 9 or sum(ch2) != 9:
            return False
    for i in range(3):
        for j in range(3):
            ch3 = [0] * 10
            for k in range(3):
                for s in range(3):
                    ch3[a[i*3+k][j*3+s]] = 1
            if sum(ch3) != 9:
                return False
    return True


a = [list(map(int, stdin.readline().split())) for _ in range(9)]
if check(a):
    print("YES")
else:
    print("NO")

✏️ 격자판 회문수

# 격자판 회문수
from sys import stdin

board = [list(map(int, stdin.readline().split())) for _ in range(7)]
cnt = 0
for i in range(3):
    for j in range(7):
        tmp = board[j][i:i+5]
        if tmp == tmp[::-1]:
            cnt += 1
        for k in range(2):
            if board[i+k][j] != board[i+5-k-1][j]:
                break
        else:
            cnt += 1

02.26 일

이분 탐색을 공부했다

이분 검색을 결정 알고리즘이라는 방법론에서 사용함.

결정 알고리즘 특징
: 답이 특정 범위 안에 있다는 것을 알 수 있음
: 그 값이 답으로서 유효한지 유효하지 않은지 검사가 필요함

✏️ 이분검색

# 이분검색
from sys import stdin

n, m = map(int, stdin.readline().split())
a = list(map(int, stdin.readline().split()))
a.sort()
lt = 0
rt = n-1
while lt <= rt:
    mid = (lt+rt)//2
    if a[mid] == m:
        print(mid+1)
        break
    elif a[mid] > m:
        rt = mid-1
    else:
        lt = mid+1

✏️ 랜선자르기(결정알고리즘)

# 랜선자르기(결정알고리즘)
from sys import stdin

def count(length):
    cnt = 0
    for x in Line:
        cnt += (x//length)
    return cnt

k, n = map(int, stdin.readline().split())
Line = []
res = 0
largest = 0
for i in range(k):
    tmp = int(stdin.readline())
    Line.append(tmp)
    largest = max(largest, tmp)

lt = 1
rt = largest
while lt <= rt:
    mid = (lt + rt)//2
    if count(mid) >= n:
        res = mid
        lt = mid + 1
    else:
        rt = mid - 1
print(res)

✏️ 뮤직비디오(결정알고리즘)

# 뮤직비디오(결정알고리즘)
from sys import stdin

def count(capacity):
    cnt = 1
    sum_x = 0
    for x in music:
        if sum_x + x > capacity:
            cnt += 1
            sum_x = x
        else:
            sum_x += x
    return cnt

n, m = map(int, stdin.readline())
music = list(map(int, stdin.readline().split()))
maxx = max(music)
lt = 1
rt = sum(music)
res = 0
while lt <= rt:
    mid = (lt + rt) // 2
    if mid >= maxx and count(mid) <= m:
        res = mid
        rt = mid - 1
    else:
        lt = mid + 1

print(res)

✏️ 마구간 정하기(결정알고리즘)

# 마구간 정하기(결정알고리즘)
from sys import stdin

def count(dis):
    cnt = 1
    ep = line[0]
    for i in range(1, n):
        if line[i] - ep >= dis:
            cnt += 1
            ep = line[i]
    return cnt

n, c = map(int, stdin.readline().split())
line = []
for _ in range(n):
    tmp = int(stdin.readline())
    line.append(tmp)
line.sort()
lt = 1
rt = line[n-1]
while lt <= rt:
    mid = (lt+rt)//2
    if  count(mid) >= c:
        res = mid
        lt = mid + 1
    else:
        rt = mid - 1
print(res)

02.07 월

그리디 알고리즘 예제 공부

그리디 알고리즘
: 각 단계에서 가장 좋은것을 선택하는 것
: 대부분 정렬이 동반됨

✏️ 회의실 배정

# 회의실 배정(그리디)
from sys import stdin

n = int(stdin.readline())
meeting = []
for i in range(n):
    s, e = map(int, stdin.readline().split())
    meeting.append((s,e))

meeting.sort(key=lambda x: (x[1], x[0]))
et = 0
cnt = 0
for s, e in meeting:
    if s >= et:
        et = e
        cnt += 1

print(cnt)

✏️ 씨름 선수

# 씨름 선수(그리디)
from sys import stdin
n = int(stdin.readline())
body = []
for i in range(n):
    a, b = map(int, stdin.readline().split())
    body.append((a,b))
body.sort(reverse=True)

largest = 0
cnt = 0
for x, y in body:
    if y > largest:
        largest = y
        cnt += 1

print(cnt)

✏️ 침몰하는 타이타닉

# 침몰하는 타이타닉(그리디)
from sys import stdin
from collections import deque
n, limit = map(int, stdin.readline().split())
p = list(map(int, stdin.readline().split()))
p.sort()
p = deque(p)
cnt = 0
while p:
    if len(p) == 1:
        cnt += 1
        break
    if p[0] + p[-1] > limit:
        p.pop()
        cnt += 1
    else:
        p.popleft()
        p.pop()
        cnt += 1
print(cnt)

✏️ 증가수열 만들기

# 증가수열 만들기(그리디)
from sys import stdin

n = int(stdin.readline())
a = list(map(int, stdin.readline()))
lt = 0
rt = n - 1
last = 0
res = ""
tmp = []
while lt <= rt:
    if a[lt] > last:
        tmp.append((a[lt], 'L'))
    if a[rt] > last:
        tmp.append((a[rt], 'R'))
    tmp.sort()
    if len(tmp) == 0:
        break
    else:
        res = res + tmp[0][1]
        last = tmp[0][0]
        if tmp[0][1] == "L":
            lt += 1
        else:
            rt += 1
    tmp.clear()
print(len(res))
print(res)

✏️ 역수열

# 역수열(그리디)
from sys import stdin

n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
seq = [0] * n
for i in range(n):
    for j in range(n):
        if a[i] == 0 and seq[j] == 0:
            seq[j] = i+1
            break
        elif seq[j] == 0:
            a[i] -= 1

for x in seq:
    print(x, end=' ')

02.08 화

자료 구조 문제 공부

✏️ 가장 큰 수(스택)

# 가장 큰 수 (스택)
from sys import stdin

num, m = map(int, stdin.readline().split())
num = list(map(int, str(num)))
stack = []
for x in num:
    while stack and m > 0 and stack[-1] < x:
        stack.pop()
        m -= 1
    stack.append(x)
if m != 0:
    stack = stack[:-m]

res = ''.join(map(str, stack))
print(res)

✏️ 쇠막대기(스택)

# 쇠막대기
from sys import stdin
s = stdin.readline()
stack = []
cnt = 0
for i in range(len(s)):
    if s[i] == '(':
        stack.append(s)
    else:
        stack.pop()
        if s[i-1] == '(':
            cnt += len(stack)
        else:
            cnt += 1

print(cnt)

✏️ 후위 표기식 만들기(스택)

from sys import stdin

a = stdin.readline()
stack = []
res = ''
for x in a:
    if x.isdecimal():
        res += x
    else:
        if x == '(':
            stack.append(x)
        elif x == '*' or x == '/':
            while stack and (stack[-1] == '*' or stack[-1] == '/'):
                res += stack.pop()
            stack.append(x)
        elif x == '+' or x == '-':
            while stack and stack[-1] != '(':
                res += stack.pop() 
            stack.append(x)
        elif x == ')':
            while stack and stack[-1] != '(':
                res += stack.pop()
            stack.pop()

while stack:
    res += stack.pop()

print(res)

✏️ 후위식 연산(스택)

# 후위식 연산
from sys import stdin

a = stdin.readline()
stack = []
for x in a:
    if x.isdecimal():
        stack.append(int(x))
    else:
        if x == '+':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n2 + n1)
        elif x == '-':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n2 - n1)
        elif x == '*':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n2 * n1)
        elif x == '/':
            n1 = stack.pop()
            n2 = stack.pop()
            stack.append(n2 / n1)
print(stack[0])

✏️ 공주구하기(큐)

# 공주구하기(큐)
from sys import stdin
from collections import deque

n, k = map(int, stdin.readline().split())
dq = list(range(1, n+1))
dq = deque(dq)

while dq:
    for _ in range(k-1):
        cur = dq.popleft()
        dq.append(cur)
    dq.popleft()
    if len(dq) == 1:
        print(dq[0])
        dq.popleft()

✏️ 응급실(큐)

any()
:전달받은 iterable한 element 중 하나라도 True일 경우 True를 돌려준다.
(만약 empty 값을 argument로 넘겨주었다면 False를 돌려준다.)

# 응급실(큐)
from sys import stdin
from collections import deque

n, m = map(int, stdin.readline().split())
q = [(pos, val) for pos, val in enumerate(list(map(int, stdin.readline().split())))]
q = deque(q)
cnt = 0
while True:
    cur = q.popleft()
    if any(cur[1] < x[1] for x in q):
        q.append(cur)
    else:
        cnt += 1
        if cur[0] == m:
            print(cnt)
            break

✏️ 교육과정설계(큐)

# 교육과정설계(큐)
from sys import stdin
from collections import deque
need = stdin.readline()
n = int(stdin.readline())
for i in range(n):
    plan = stdin.readline()
    dq = deque(need)
    for x in plan:
        if x in dq:
            if x != dq.popleft():
                print("#%d NO" %(i+1))
                break
    else:
        if len(dq) == 0:
            print("#%d YES" %(i+1))
        else:
            print("#%d NO" %(i+1))

✏️ 단어찾기(해쉬)

# 단어찾기(해쉬)
from sys import stdin
n = int(stdin.readline())
p = dict()

for i in range(n):
    word = stdin.readline()
    p[word] = 1

for i in range(n-1):
    word = stdin.readline()
    p[word] = 0

for key, val in p.items():
    if val == 1:
        print(key)
        break

✏️ 아나그램(딕셔너리 해쉬)

Dictionary .get()메소드
: 찾고자 하는 키가 정의된 딕셔너리에 없는 경우 원하는 값으로 초기화해주고 만약에 원하는 키가 딕셔너리에 있다면 그에 해당하는 값(value)을 변수에 저장하도록 한다.
ex) str1.get(key, 0) + 1
: key가 없을 경우 0으로 초기화 있을 경우 +1

# 아나그램(딕셔너리 해쉬)
from sys import stdin
a = stdin.readline()
b = stdin.readline()
str1 = dict()

for x in a:
    str1[x] = str1.get(x, 0) + 1

for x in b:
    str1[x] = str1.get(x, 0) - 1

for x in a:
    if str1.get(x) > 0:
        print("NO")
        break
else:
    print("YES")

✏️ 아나그램(리스트 해쉬)

# 아나그램(리스트 해쉬)
from sys import stdin
a = stdin.readline()
b = stdin.readline()
str1 = [0] * 52
str2 = [0] * 52
for x in a:
    if x.isupper():
        str1[ord(x) - 65] += 1
    else:
        str[ord(x) - 71] += 1

for x in b:
    if x.isupper():
        str2[ord(x) - 65] += 1
    else:
        str2[ord(x) - 71] += 1

for i in range(52):
    if str1[i] != str2[i]:
        print("NO")
        break
else:
    print("YES")

✏️ 최소힙

# 최소힙
from sys import stdin
import heapq as hq

a = []
while True:
    n = int(stdin.readline())
    if n == -1:
        break
    if n == 0:
        if len(a) == 0:
            print(-1)
        else:
            print(hq.heappop(a))
    else:
        hq.heappush(a, n)

✏️ 최대힙

# 최대힙
from sys import stdin
import heapq as hq

a = []
while True:
    n = int(stdin.readline())
    if n == -1:
        break
    if n == 0:
        if len(a) == 0:
            print(-1)
        else:
            print(-hq.heappop(a))
    else:
        hq.heappush(a, -n)

02.09 수

상태트리에 대한 공부

✏️ 재귀함수와 스택

선수지식인 재귀함수와 스택에 대해 정리해보겠다

예제 (1)

import sys

def DFS(x):
	if x > 0:
		print(x)
		DFS(x-1)


if __name__=="__main__":
	n = int(input())
	DFS(n)

-> 결과
3
2
1

예제 (2)

import sys

def DFS(x):
	if x > 0:
		DFS(x-1)
		print(x)


if __name__=="__main__":
	n = int(input())
	DFS(n)

-> 결과
1
2
3

이유

✏️ 재귀함수를 이용한 이진수 출력

# 재귀함수를 이용한 이진수 출력
from sys import stdin

def DFS(x):
    if x == 0:
        return
    else:
        DFS(x//2)
        print(x%2, end=' ')

if __name__=="__main__":
    n = int(stdin.readline())
    DFS(n)

✏️ 이진트리 순회(깊이우선탐색)

전위순회

def DFS(v):
    if v > 7:
        return
    else:
        print(v, end=" ")
        DFS(v*2) # 왼쪽노드
        DFS(v*2+1) # 오른쪽노드

if __name__=="__main__":
    DFS(1)

중위순회

def DFS(v):
    if v > 7:
        return
    else:
        DFS(v*2) # 왼쪽노드
        print(v, end=" ")
        DFS(v*2+1) # 오른쪽노드
        
if __name__=="__main__":
    DFS(1)

후위순회

def DFS(v):
    if v > 7:
        return
    else:
        DFS(v*2) # 왼쪽노드
        DFS(v*2+1) # 오른쪽노드
        print(v, end=" ")
        
if __name__=="__main__":
    DFS(1)

✏️ 부분집합 구하기(DFS)

from sys import stdin

def DFS(v):
    if v == n+1:
        for i in range(1, n+1):
            if ch[i] == 1:
                print(i, end=' ')
        print()
    else:
        ch[v] = 1
        DFS(v+1)
        ch[v] = 0
        DFS(v+1)


if __name__=="__main__":
    n = int(stdin.readline())
    ch = [0] * (n+1)
    DFS(1)

✏️ 합이 같은 부분집합(DFS)

# 합이 같은 부분집합(DFS)
from sys import stdin

def DFS(l, sum_n):
    if sum_n > total//2: # 시간 복잡도 줄이기
        return
    if l == n:
        if sum_n == (total - sum_n):
            print("YES")
            sys.exit(0)
    else:
        DFS(l+1, sum_n+a[l])
        DFS(l+1, sum_n)

if __name__=="__main__":
    n = int(stdin.readline())
    a = list(map(int, stdin.readline().split()))
    total = sum(a)
    DFS(0, 0)
    print("NO")

✏️ 전역변수와 지역변수

선수지식 정리

메인 스크립트에 선언되면 전역변수(모든 함수에서 접근 가능한 변수)
함수 내에서 지역변수인지 먼저 확인하고 지역변수가 아니면 전역변수를 찾음
-> 항상 지역변수가 우선이다.

예제 코드

전부 전역변수 호출

def DFS1():
	print(cnt)


def DFS2():
	if cnt==5:
		print(cnt)


if __name__=="__main__":
	cnt = 5
	DFS1()
	DFS2()
	print(cnt)

-> 결과
5
5
5

DFS1()지역변수 호출

def DFS1():
	cnt = 3
	print(cnt)


def DFS2():
	if cnt==5:
		print(cnt)


if __name__=="__main__":
	cnt = 5
	DFS1()
	DFS2()
	print(cnt)

-> 결과
3
5
5

아래와 같은 코드는 에러발생

def DFS1():
	cnt = 3
	print(cnt)


def DFS2():
	if cnt==5:
		cnt = cnt+1
		print(cnt)


if __name__=="__main__":
	cnt = 5
	DFS1()
	DFS2()
	print(cnt)

-> 결과
local variable 'cnt' 관련 Error!

이유는?
cnt = cnt+1 에서 cnt를 지역변수를 만든다고 인식함.
cnt == 5: 에서 cnt가 지역변수이므로 cnt를 선언한적이 없다고 생각하여 에러발생
즉 값이 없는데 참조해버림

cnt 전역 변수로 선언하여 해결

def DFS1():
	cnt = 3
	print(cnt)


def DFS2():
	global cnt
	if cnt==5:
		cnt = cnt+1
		print(cnt)


if __name__=="__main__":
	cnt = 5
	DFS1()
	DFS2()
	print(cnt)

-> 결과
3
6
6

리스트는 전역변수로 잘 작동하는 이유는?

def DFS():
	a[0] = 7
	print(a)


if __name__=="__main__":
	a = [1, 2, 3]
	DFS()
	print(a)

a를 새로 생성하는 게 아닌, 참조하는 것
자동으로 전역 리스트로 인식

그러나 아래 경우는 a리스트를 로컬로 인식.
a리스트를 새로 생성하기 때문 a = []<- 리스트 생성 코드

def DFS():
	a = [7, 8]
	print(a)


if __name__=="__main__":
	a = [1, 2, 3]
	DFS()
	print(a)

아래 같은 경우는 에러
a라는 리스트가 선언된 적이 없기 때문. a = a + [4]
에러 해결하려면 global a를 먼저 선언해주어야함.

def DFS():
	a = a + [4]
	print(a)


if __name__=="__main__":
	a = [1, 2, 3]
	DFS()
	print(a)