외우기 쉽게
 
1) 동적 최대 합
def dy_part_max_sum(arr):
temp=[0]*len(arr)
temp[0]=arr[0]
for i in range(0,len(arr)):
temp[i]=max(0,temp[i-1])+arr[i]
return max(temp)
 
scores = [-14, 7, 2, 10, -4, 9, -10]
res=dy_part_max_sum(scores)
print("result:",res) #24
 
2) 동적 구간 합
def dy_part_sum(arr,s,end):
  temp=[0]*len(arr)
  temp[0]=arr[0]
  for i in range(0,len(arr)):
    temp[i]=temp[i-1]+arr[i]
    if i==(s-1):
      s_sum=temp[i]
    elif i==end:
      end_sum=temp[i]
      break
        
  return (end_sum - s_sum)
 
scores = [100, 95, 80, 100, 70, 65]
print("result:",dy_part_sum(scores, 3, 4)) # 235
 
==================================================
 
o 부분합
 
def partial_sum(arr, a, b):
    arr = [0] + arr #초기화
    partial_sum = [0] * len(arr) #초기화
    
    for i in range(1, len(arr)):
        partial_sum[i] = partial_sum[i-1] + arr[i]
        
    partial_sum = partial_sum[1:]
    print("partial_sum", partial_sum)
    
    print("total sum", partial_sum[-1])
    
    return partial_sum[b] - partial_sum[a-1]
 
scores = [100, 95, 80, 100, 70, 65]
print("result:",partial_sum(scores, 3, 5)) # 235
# partial_sum [100, 195, 275, 375, 445, 510]
 
# total sum 510
 
o 연속 구간 부분수열 최대합
 
def partial_sum(arr):
    arr = [0] + arr
    partial_sum = [0] * len(arr)
    
    for i in range(1, len(arr)):
        partial_sum[i] = partial_sum[i-1] + arr[i]
        
    partial_sum = partial_sum[1:]
    print("partial_sum", partial_sum)
    
    max_partial_sum = partial_sum[0]
    
    for b in range(0, len(arr)-1):
        for a in range(0, b):
            print(a, b, partial_sum[b] - partial_sum[a-1])
            max_partial_sum = max(max_partial_sum, partial_sum[b] - partial_sum[a-1])
            
    print("max partial sum", max_partial_sum)
 
scores = [-14, 7, 2, 10, -4, 9, -10]
print("list", scores)
res=partial_sum(scores)
print("result:",res)
 
 
#
list [-14, 7, 2, 10, -4, 9, -10]
partial_sum [-14, -7, -5, 5, 1, 10, 0]
0 1 -7
0 2 -5
1 2 9
0 3 5
1 3 19
2 3 12
0 4 1
1 4 15
2 4 8
3 4 6
0 5 10
1 5 24
2 5 17
3 5 15
4 5 5
0 6 0
1 6 14
2 6 7
3 6 5
4 6 -5
5 6 -1
max partial sum 24
 
o 동적 계획법 최대값
 
def dynamic_partial_sum(arr):
    cache = [0] * len(arr)
    cache[0] = arr[0]
    for i in range(0, len(arr)):
        cache[i] = max(0, cache[i-1]) + arr[i]
        print(i, arr[i], cache)
    print(cache)
    return max(cache)
 
scores = [-14, 7, 2, 10, -4, 9, -10]
print("list", scores)
res=dynamic_partial_sum(scores)
print("result:",res) #24
#
list [-14, 7, 2, 10, -4, 9, -10]
0 -14 [-14, 0, 0, 0, 0, 0, 0]
1 7 [-14, 7, 0, 0, 0, 0, 0]
2 2 [-14, 7, 9, 0, 0, 0, 0]
3 10 [-14, 7, 9, 19, 0, 0, 0]
4 -4 [-14, 7, 9, 19, 15, 0, 0]
5 9 [-14, 7, 9, 19, 15, 24, 0]
6 -10 [-14, 7, 9, 19, 15, 24, 14]
[-14, 7, 9, 19, 15, 24, 14]
 
저작자표시
 
a=[list(input())for i in range(10)]
b,c=map(int,input().split())
 
def DFS(f,b):#기준점. DFS 재귀 될때마다 바뀜
if f<0 or f>9 or b<0 or b>9:#인덱스 에러 안나게 처리
return
elif a[b][f]=="*": #이미 탐색(현재 배열값이 "*"이라면) 재귀 불렀던 줄로 돌아가기
return
a[b][f]="*" #아직 탐색 안했다면(현재 배열값이 "_"인 상태) 현재 배열값을 "*"로 바꿈
DFS(f+1,b) #기준점으로부터 아래 한칸 탐색. 재귀 부르면(f+1,b)가 기준점됨
DFS(f-1,b) #기준점으로부터 위 한칸 탐색.   재귀 부르면(f-1,b)가 기준점됨
DFS(f,b+1) #기준점으로부터 오른쪽 한칸 탐색. 재귀 부르면(f,b+1)가 기준점됨
DFS(f,b-1) #기준점으로부터 왼쪽 한칸 탐색. 재귀 부르면(f,b-1)가 기준점됨
 
DFS(b,c) #첫번째 입력된 기준점 보내기
 
for i in range(10): # 출력
  print(''.join(a[i]))
저작자표시
 
import sys 
sys.setrecursionlimit(10**7)
 
m,n,k = list(map(int, input().split()))
 
arr=[[0]*(n+1) for _ in range(m+1)]
 
for _ in range(k):
  x1,y1,x2,y2= (map(int, input().split()))
  for i in range(y1,y2):
    for j in range(x1, x2):
      arr[i][j] = 1
 
def dfs(x,y):
  if x<0 or x>n-1 or y<0 or y>m-1:
    return 0
 
  if arr[y][x]:
    return 0
 
  arr[y][x]=1
  return 1 + dfs(x-1,y) + dfs(x+1,y) + dfs(x,y-1) + dfs(x,y+1)
 
cnt=[]
 
for i in range(m):
  for j in range(n):
    if arr[i][j] ==0:
      cnt.append(dfs(x=j, y=i))
 
print(len(cnt))
print(*sorted(cnt))
저작자표시
 
from collections import deque
 
def bfs(x,y):
  q=deque()
  q.append([x,y])
  visited[x][y]=1
 
  while q:
    x,y=q.popleft()
 
    for i in range(8):
      nx,ny =x+dx[i], y+dy[i]
      if 0<=nx<h and 0<=ny<w:
        if lack[nx][ny]=='L' and visited[nx][ny]==0:
          visited[nx][ny]=1
          q.append([nx,ny])
 
global w, h
w, h = map(int, input().split())
 
global lack
lack=[]
 
for i in range(h):
  lack.append(list(map(str,input().split())))
 
 
global dx, dy
dx=[0,0,1,-1,1,-1,1,-1]
dy=[1,-1,0,0,1,-1,-1,1]
 
cnt=0
 
global visited
visited=[[0 for x in range(w)] for y in range(h)]
 
for i in range(h):
  for j in range(w):
    if lack[i][j]=='L' and visited[i][j]==0:
      bfs(i,j)
      cnt+=1
 
print(cnt)
저작자표시
 
일단 간단히 하자면, 등고선의 시작에서 나머지는 값을 빼면서 출력함.
단 배열은 0 부터 시작이라서 (x-1, y-1)이고, 시작값이 1이므로 
abs(i-(x-1)) + abs(j-(y-1)) + 1
 
그럼 절대값은 왜 넣었나? 필요하니깐.....중점에서 -값도 나오기 때문이다.
 
 
n = int(input())
x, y = map(int, input().split())
 
for i in range(0, n):
    for j in range(0, n):
        print(abs(i-(x-1)) + abs(j-(y-1)) + 1, end=' ')
    print()
저작자표시
 
dfs의 전형적인 방법으로 
1) 범위먼저 설정
2) 방문가능한지와 맞는 색인지 확인해보고, 
3) 앞뒤좌우에 있으면 cnt를 늘린다.
 
물론 i, j의 for loop로 돌려서 모두 찾아야지요~
 
이 문제를 풀면서 의문점
1. arr에 값을 넣을때 왜 다른가?
1) arr = [list(map(int, input().split())) for _ in range(7)] 
는 ok
2) 
for _ in range(7):
  arr = list(map(int, input().split()))
에서 arr[1][1]의 타잎값은 안나오지???
궁금해...
 
 
arr = [list(map(int, input().split())) for _ in range(7)] 
 
 
#for _ in range(7):
#  arr = list(map(int, input().split()))
 
#print(type(arr))
 
visited=[[0]*7 for _ in range(7)]
 
res=0
 
def dfs(x,y,arr,v,val):
  if x<0 or x>=7 or y<0 or y>=7:
    return 0
  cnt=0
  if v[x][y]==0 and arr[x][y] == val:
    v[x][y] = arr[x][y]
    cnt+=1
    cnt+= dfs(x,y+1,arr,v,val)
    cnt+= dfs(x,y-1,arr,v,val)
    cnt+= dfs(x+1,y,arr,v,val)
    cnt+= dfs(x-1,y,arr,v,val)
  return cnt
 
#print(type(arr[1][1]))
 
for i in range(7):
  for j in range(7):
    if dfs(i,j,arr,visited,arr[i][j]) >= 3:
      res+=1
 
print(res)
 
저작자표시

+ Recent posts

티스토리툴바