용답노트

미확인도착지 -> 다익스트라로하면 경로가 1개만 저장되고 다른 경로를 체크할수 없음.

알게 된 내용

• deque는 O(1) 로 맨앞에 요소를 추가할 수 있다. q.appendleft(x)
• deque는 정렬기능이 없다. 정렬 불가임.
• 빈 리스트는 list.sort() 동작하지 않는다. a = sorted(list) 이런식으로 써야함.

A = []
B = deque(A.sort()) #불가능
B = deque(sorted(A)) #가능

오답노트

• 문제가 길고 조건이 많아서, 자칫해서 문제를 잘못이해하면 몇시간을 통째로 날릴 수 있음. 코드 작성 전에 아래와 같이 조건을 잘 정리해 두었던 것이 도움이 되었음

#봄: 나이만큼 양분 먹고 / 나이 1 증가 / 여러 나무가 있으면 어린나무부터 양분먹기 / 양분없으면 사망 
#여름: 죽은나무 나이 나누기2 만큼 양분추가(소수점 버림)
#가을: 5의 배수 나이인 경우 나무 번식 / 인접한 8개 칸에 나이 1인 나무 생성
#겨울: 주어진 양분 배급

• 8방향 이동을 r, c 가 0일 때와 n-1 일때 조건을 세워서 풀었음. -> 아래와 같이 작성하면 가독성도 좋고 실수할 가능성도 낮음.

#이동
dx=[-1, 0, 1,-1, 1,-1, 0, 1]
dy=[-1,-1,-1, 0, 0, 1, 1, 1]

for i in range(8):
    nx=r+dx[i]
    ny=c+dy[i]
    if 0<=nx<n and 0<=ny<n:
        tree[nx][ny].appendleft(1)

코드

import sys
from collections import deque
sys.stdin = open("input.txt", "r") 

n, m, k = map(int,sys.stdin.readline().split())
A=[False for _ in range(n)]
for _ in range(n):
    A[_]=list(map(int,sys.stdin.readline().split()))

#현재 양분 값 저장하는 배열
B=[[5 for i in range(n)] for j in range(n)]

#트리 배열 생성
#트리 배열 각 노드의 값 == [1나무의 나이,2나무의 나이,..., x나무의 나이]
tree=[[[] for c in range(n)] for r in range(n)]
for _ in range(m):
    x,y,z = map(int,sys.stdin.readline().split())
    tree[x-1][y-1].append(z)

#처음 한번만 정렬
for i in range(n):
    for j in range(n):
        tree[i][j] = deque(sorted(tree[i][j]))
#이동
dx=[-1, 0, 1,-1, 1,-1, 0, 1]
dy=[-1,-1,-1, 0, 0, 1, 1, 1]

for y in range(k):
    sons=[] #번식하는 나무 담아둘 곳.
    for r in range(n):
        for c in range(n):
            cnt_tree = len(tree[r][c]) #현재 땅의 나무 개수 체크
            if cnt_tree ==0:
                B[r][c]+=A[r][c]
                continue
            #봄
            tmp=deque()
            die=0
            for age in tree[r][c]:
                if age > B[r][c]:# 잔여 양분 체크
                    die+= age//2 #죽은나무 나이 나누기2만큼 양분추가(소수점 버림)
                    continue
                B[r][c]-=age
                tmp.append(age+1)
            tree[r][c]=tmp

            #여름
            B[r][c] += die 
            
            #가을
            for t in tree[r][c]:
                if t%5 == 0: sons.append((r,c))
            #겨울
            B[r][c]+=A[r][c]
    #가을 적용
    for son in sons:
        (r,c) = son
        for i in range(8):
            nx=r+dx[i]
            ny=c+dy[i]
            if 0<=nx<n and 0<=ny<n:
                tree[nx][ny].appendleft(1)
#나무 개수 카운트
ans =0
for i in range(n):
    for j in range(n):
        ans += len(tree[i][j])
print(ans)

궁금한 점

• 파이썬에서 재귀를 하는데 시간이 오래 안걸리는 방법이 있는지? 꼭 찾아보자. c++는 depth 백만까지도 dfs로 풀이 가능하다는데 파이썬도 그런지 확인 필요.

코드1

• dfs 풀이
• 효율성 테스트에서 시간 초과
• 코드 내용
  • dfs함수는 row, col, state 3개 인자를 받는다.
  • state에 따라서 갈 수 있는 주변 노드를 확인하여 해당 노드를 다시 dfs 함수에 넣는다.
  • 함수가 재귀적으로 생성되며, (N,N)에 도달할 경우 ans + 1  

import sys

n= int(sys.stdin.readline())
graph= [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
n-=1
ans = 0
def dfs(r,c,state):
    global ans
    if r==n and c == n: 
        ans += 1
        return 
    
    if state==0:
        if c < n and graph[r][c+1]==0:
            dfs(r,c+1,0) 
            if r < n and graph[r+1][c]==0 and graph[r+1][c+1]==0: dfs(r+1,c+1,2)
    elif state==1:
        if r < n and graph[r+1][c]==0:
            dfs(r+1,c,1)
            if c < n and graph[r][c+1]==0 and graph[r+1][c+1]==0: dfs(r+1,c+1,2)
    elif state==2:
        if c < n and graph[r][c+1]==0: dfs(r,c+1,0)
        if r < n and graph[r+1][c]==0: dfs(r+1,c,1)
        if c < n and r < n and graph[r+1][c+1]==0 and graph[r+1][c] ==0 and graph[r][c+1] ==0: dfs(r+1,c+1,2)

dfs(0,1,0) 
print(ans)

코드2

• dp로 풀이
• 코드 내용
  • dp는 3중 배열
  • dp[r][c]는 (r,c) 위치에 가로, 세로, 대각선으로 올 수 있는 경우의 수
  • dp의 1행에 대해서는 따로 초기화 / dp 1열에 대해서는 따로 초기화
  • dp의 점화식은 가로/세로/대각선 인 경우에 따라 다르게 작성
    • 가로: dp[r][c][0] = dp[r][c-1][0] + dp[r][c-1][2]
    • 세로: dp[r][c][1] = dp[r-1][c][1] + dp[r-1][c][2]
    • 대각선: dp[r][c][2] = dp[r-1][c-1][0] + dp[r-1][c-1][1] +dp[r-1][c-1][2]

import sys
sys.stdin = open("input.txt", "r") 

n= int(sys.stdin.readline())
graph= [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
dp=[[[0 for _ in range(3)] for _ in range(n)]for _ in range(n)]
dp[0][1] = [1,0,0]

for i in range(2,n):
    if graph[1][i]==0:
        dp[0][i][0] = dp[0][i-1][0]

for r in range(1,n):
    for c in range(1,n):
        if graph[r][c]==0:
            dp[r][c][0] = dp[r][c-1][0] + dp[r][c-1][2]
            dp[r][c][1] = dp[r-1][c][1] + dp[r-1][c][2]
            if graph[r][c-1] == 0 and graph[r-1][c]==0:
                dp[r][c][2] = dp[r-1][c-1][0] + dp[r-1][c-1][1] +dp[r-1][c-1][2]

print(sum(dp[n-1][n-1]))

알게 된 내용

• Tuple로 이루어진 리스트(ex. [(1,2,3), (1,4,6), (1,6,9)] 에서 tuple의 n번째 원소끼리만 더하는 방법:
  • sum(i for i,j,k in tuple_list) : 3
  • sum(j for i,j,k in tuple_list) : 12
  • sum(k for i,j,k in tuple_list) : 18

답안

• 다리를 지나고 있는 ing_que 를 만들어서 풀이하였음.

import collections 

def solution(bridge_length, weight, truck_weights):
    answer =0 
    truck_que = collections.deque(truck_weights)
    ing_que =collections.deque()
    
    #초기화
    time =1
    ing_que.append((truck_que.popleft(),1)) #1초에 들어왔음.
    while ing_que:
        time +=1
        #다리 지난 것은 q에서 빼주기
        if time - ing_que[0][1] == bridge_length:
            ing_que.popleft()
        
        #무게 여분 남을 경우 트럭 추가로 올림
        if truck_que and sum(i for i,j in ing_que) + truck_que[0] <= weight:
            ing_que.append((truck_que.popleft(),time))

    return time

https://www.acmicpc.net/problem/2583

문제

• 인접한 노드(모눈종이 빈칸)들을 하나의 '뭉치'라고 했을 때, 몇개의 뭉치가 있는지 세고 각 뭉치의 넓이를 계산하는 문제.
• 백준 1012번 유기농배추와 유사한 문제(참고: https://yong-bro.tistory.com/30)
  • 단, 유기농 배추 문제와 비교했을 때 1)graph의 위 아래가 뒤집혀 있고 2)노드가 모서리 기준이므로 인덱스 계산시에 주의해야 함

오답노트

• x,y 좌표계와 행렬은 반대로 생각해야함. y가 행과 비슷한 성질이므로 행과 열은 좌표계에 올리면 y,x임.
• 좌표로 제시된 이 문제를 코드로 작성하니 결국 graph[y][x] = 1 와 같이 거꾸로 써줘야함. (아니면 애초에 행렬 좌표계로 바꿔서 생각하던가)

답안

• 주어진 사각형 정보를 활용하여 Graph 만들기
  • 인덱스가 직사각형 안에 들어오면 벽 세우기(graph[y][x] = 1)
• BFS 진행
  • 벽이 아닌것중에 방문안한곳 발견
    • cnt  +1
    • 인접한 노드 모두 방문처리. 방문처리 될 때 넓이 1 추가

import sys
import collections 

sys.stdin=open("input.txt","rt") 
m, n, k =  map(int,sys.stdin.readline().split())
graph = [[0]*n for _ in range(m)] # m행 n열
visited = [[0]*n for _ in range(m)]

for _ in range(k):
    x1,y1,x2,y2 = map(int,sys.stdin.readline().split()) #사각형 정보 입력
    for x in range(n):
        for y in range(m):
            if x>= x1 and x<= x2-1 and y >= y1 and y <= y2-1 :
                graph[y][x] =1  # 행/열을 좌표계로 올리면 y,x 꼴이 된다.
cnt =0    
dx =[1,0,-1,0]
dy =[0,1,0,-1]
q = collections.deque()
a = []
for i in range(m): #여기부턴 행/열 좌표계 이므로 위쪽 코드와 m n 순서가 다르다.
    for j in range(n):
        if graph[i][j]==0 and visited[i][j]==0:
            cnt+=1
            visited[i][j] =1
            a.append(1)
            q.append((i,j))
            while q:
                x, y = q.popleft()                
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if nx >= 0 and nx < m and ny >= 0 and ny < n and graph[nx][ny]==0 and visited[nx][ny] ==0:
                        visited[nx][ny]=1
                        a[cnt-1] += 1
                        q.append((nx,ny))

print(cnt)
print(*sorted(a))

https://www.acmicpc.net/problem/1012

문제

• 인접한 노드(배추)들을 하나의 '뭉치'라고 했을 때, 몇개의 뭉치가 있는지 세는 문제

답안

• 노드들을 한차례 씩 돌면서, 방문하지 않은 배추를 찾는다.
• 배추를 발견하면 cnt +1 계산 후, 인접한 배추들을 모두 방문처리 한다.

import sys
import collections

T = int(sys.stdin.readline())
for _ in range(T):
    m, n, k =  map(int,sys.stdin.readline().split())
    visited =[[False]*m for _ in range(n)]
    graph =[[False]*m for _ in range(n)]
    cnt = 0

    for _ in range(k):
        x,y = map(int,sys.stdin.readline().split())
        graph[y][x] =1 
 
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1 and visited [i][j] == 0:
                
                #발견하면 cnt+1, 그리고 그 주변을 모두 방문 시킨다.
                cnt +=1
                q= collections.deque()
                q.append((i,j))
                while q:
                    x, y = q.popleft()
                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if nx < n and ny < m and nx >=0 and ny >= 0 and graph[nx][ny] == 1 and visited [nx][ny] == 0:
                            visited[nx][ny] = 1
                            q.append((nx,ny))
    
    print(cnt)

https://www.acmicpc.net/problem/3986

문제

• N개 줄에는 A와 B로만 이루어진 단어가 주어진다.
• 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓는다. 이때 글자 1개 당 하나의 곡선만 그을 수 있다.
• 만약 선끼리 교차하지 않으면서 모든 글자를 짝 지을수 있다면 '좋은 단어'다.
• 주어진 N개의 단어 중 '좋은 단어'의 개수를 구한다.

나의 풀이

• 이 문제 풀이에 필요한 기본 원칙은 같은 글자 중 서로 완전히 접한 글자 부터 연결해야한다.
• 위의 원칙을 구현하는 가장 좋은 방법은 stack 이다.

import sys
import collections

n = int(sys.stdin.readline().strip())

cnt=0
q = collections.deque()
for _ in range(n):
    input=sys.stdin.readline().strip()
    for s in input:
        if len(q) ==0:
            q.append(s)    
        elif q[-1] ==s:
            q.pop()
        else:
            q.append(s)
        
    if len(q) ==0: #좋은 단어 성공일 경우 cnt + 1
        cnt+=1 
        q.clear()
    else:
        q.clear()
    

print(cnt)

오답노트

• 원칙을 생각해내지 못해서 시간을 많이 빼았겼음. 
• 아직도 왜 저 원칙이 적용되는지 완벽히 이해는 안됨.여러번 봐야할 듯

https://www.acmicpc.net/problem/1940

문제

• 주어진 길이 n의 리스트(ex.2 7 4 1 5 3) 에서 2개를 뽑아 합이 m이 되는 개수를 계산한다.

코드1(조합 활용, 효율성↓)

답은 맞았지만 시간 효율성이 낮았던 풀이

• n 개 중에 2개를 뽑는 리스트를 모두 구한다.
• 그 중에 합이 m이 되는 경우의 개수를 센다.

import sys
import itertools

n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())

lst = list(map(int,input().split()))
combi = itertools.combinations(lst,2)
result=0
for i in combi:
    if i[0]+i[1] == m:
        result +=1
print(result)

코드2(투포인터, 효율성↑) 

• 리스트를 정렬하고, 양 끝에서 부터 합을 계산
• 합이 목표 값보다 낮은 경우, left +1
• 합이 목표 값보다 높은 경우, right -1
• 합이 목표 값과 동일한 경우, left +1 & right -1

import sys

n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())

lst = list(map(int,sys.stdin.readline().split()))
lst.sort()

i_start = 0
i_end = len(lst)-1
cnt =0

while i_start < i_end:
    value = lst[i_start] + lst[i_end]
    if value ==m:
        cnt+=1
        i_start +=1
        i_end -=1
    elif value < m:
        i_start +=1
    elif value > m:
        i_end -= 1

print(cnt)