용답노트

문제

• https://www.acmicpc.net/problem/6987

오답노트

• 첫 풀이
  • 제시된 월드컵 대진에서 팀별로 1씩 빼보는 방식으로 모든 경우를 탐색하여 그러한 대진표가 가능한지를 판단하려고 했음.
  • 해당 풀이대로 하면 팀별로(6) * 승무패에 대해서(3) * 다른 팀과 대진(6) 했을 경우에 수 에 대해서 뻴 수 있는게 있는지 모두 확인해보면서 최종적으로 15전 이 되었을 때 모두 0이 되는지 확인하기 때문에 (6*3*6)^15 라는 매우 큰 시간 복잡도를 가진다. 
  • 다만, (6*3*6)^15를 모두 확인하는 것은 아니고 1) 15전이 되지 않았더라도 뺄수 있는게 없으면 멈추고, 2)정답을 찾으면 바로 멈춘다 는 것을 고려해서 진행하였음.
  • 이렇게 할 경우, 입력으로 가능한 대진이 들어왔을 경우에는 금방 YES라고 출력하지만, 입력으로 불가한 대진이 들어올 경우에는 NO를 출력할 때까지 어마어마한 시간이 걸린다.
• 개선
  • 시간 복잡도를 대략으로라도 계산해보고, 15전이 되지 않아서 멈추는 경우의 수가 있다고 하더라도 너무 경우의 수가 많으니 다른 방법을 고안해 봤어야한다.
  •  1)15전이므로 모든 월드컵 대진에 대해서 3가지(승무패)에 대해서 탐색하되, 2)해당 대진이 주어진 입력과 요소가 하나라도 다르면 무조건 멈춤
  • 이렇게 하면 가능한 대진 and 요소와 일치하는것에 대해서만 탐색이 진행되기 때문에 훨씬 적은 시간 복잡도로 해결 가능(15개의 대전만 뽑아서 진행하기 때문에 이전 풀이에서 처럼 불가능한 대진에 대해서 탐색하는 시간이 자연스럽게 사라짐)

코드1(시간 초과)

import sys
sys.stdin=open("input.txt","rt") 
readl = sys.stdin.readline

def DFS(start, graph,matchCnt,ans,tc):
    if ans[tc]!=-1: return
    if matchCnt ==15:
        for i in range(6):
            if sum(graph[i]) > 0 :
                ans[tc]=0
                return
        ans[tc]= 1
        return
    for i in range(start, 6): #각 팀에 대해서 하나씩 빼보며 확인(앞팀부터 순차대로)
        for j in range(3): #승무패
            if graph[i][j] : #0이 아닌 경우에만
                graph[i][j]-=1
                for k in range(6): #본인 제외한 다른 5개팀에서 뺄수있는게 있는지 확인.
                    if i ==k: continue
                    #승무패 경우에 따라 나누기
                    if j == 0 :
                        if graph[k][2]: 
                            graph[k][2] -=1
                            DFS(start, graph, matchCnt+1, ans, tc)
                            graph[k][2] +=1
                    elif j == 1:
                        if graph[k][1]: 
                            graph[k][1] -=1
                            DFS(start, graph, matchCnt+1, ans, tc)
                            graph[k][1] +=1
                    elif j == 2:
                        if graph[k][0]: 
                            graph[k][0] -=1
                            DFS(start, graph, matchCnt+1, ans, tc)
                            graph[k][0] +=1
                graph[i][j]+=1
    return



ans = [-1,-1,-1,-1]
graph=[]
for tc in range(4):
    test = list(map(int, readl().split()))
    for cal in range(6):
        graph.append(test[3*cal:3*(cal+1)])
    for i in range(6):
        if sum(graph[i]) > 5 :
            break
    else:
        DFS(0, graph,0,ans, tc)
    graph=[]
    

print(*ans)

코드2 (정답)

import sys
import itertools
sys.stdin=open("input.txt","rt") 
readl = sys.stdin.readline

teamList =[0,1,2,3,4,5]
matchList = list(itertools.combinations(teamList,2))

#matchList = [ab ac ad ae af bc bd be bf ... ...]
#borad: graph와 일치하는지 확인을 위한 이중리스트
#matchCnt: 경기 진행 횟수, DFS가 끝나면 1이 추가됨. 15가 되는순간, 15번의 경기를 치룬 이후이므로 종료.
#tc: testcase number
def DFS(board,matchCnt,tc):
    if ans[tc] != -1:
        return
    if matchCnt == 15:
        ans[tc] = 1
        return
    team1 = matchList[matchCnt][0]
    team2 = matchList[matchCnt][1]

    #승,무,패 한 경우에 대해서
    for i in range(3): 
        board[team1][i] += 1
        board[team2][2-i] += 1 
        #graph와 일치하는지 확인
        if board[team1][i] <= graph[team1][i] and  board[team2][2-i] <= graph[team2][2-i]: 
            DFS(board,matchCnt+1,tc)
        board[team1][i] -= 1
        board[team2][2-i] -= 1

ans = [-1,-1,-1,-1]
for tc in range(4):
    graph=[]
    board=[[0 for i in range(3)] for j in range(6)]
    tmp = list(map(int, readl().split()))
    for cal in range(6):
        graph.append(tmp[3*cal:3*(cal+1)])
    for i in range(6):
        if sum(graph[i]) > 5 :
            break
    else:
        DFS(board, 0, tc)

for i in range(4):
    if ans[i] == -1:
        ans[i] = 0
print(*ans)

문제

• https://www.acmicpc.net/problem/11501

알게 된 내용

• 리스트의 최대(or 최소)값을 가지는 index를 획득하는 방법(풀이1으로 풀면서 필요했던 내용)

 index_max = max(range(len(values)), key=values.__getitem__)

풀이1(로직 개선 필요)

• 전체 range에서 최대값의 index를 확인 및 저장
  • 처음~해당 index까지 주식 모아서 판매.
• 저장된 최대index~끝 을 확인하여 최대값의 index 확인
  • 자기 자신일 경우 넘어감.
  • 아닐경우
    • 현재index~최대값의 index까지 주식 모아서 판매.

풀이2(정답)

• 맨 뒤에서 부터 확인한다.
• 맨 뒤의 값을 max에 저장
• 하나씩 앞으로 가면서 값을 확인
  • 현재 max보다 클 경우, max 값 갱신
  • 현재 max보다 작을 경우, 현재 max 값과의 차이 만큼 수익에 더함

미확인도착지 -> 다익스트라로하면 경로가 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)