Python

7569번 파이썬

처음에 python으로 제출했더니 채점되다가 시간 에러가 뜸 그래서 pypy(반복문이 많을 경우 계산이 빠르다고 함)로 제출했더니 맞았다!! 토마토 문제는 bfs를 이용해서 풀었고 층 수별로 박스가 나눠진 3차원 구조여서 dict를 이용해서 3차원 배열을 저장했다! queue에는 현재 1인 값들 즉 익은 토마토가 있는 것들의 row,col,height을 저장했고 temp에는 queue에 있는 1인 값들의 토마토 주변에 값이 0이어서 하루가 지나면 1이 되는 것들을 넣어서 다시 queue에 넣어줬다, temp에 아무것도 없는 경우 => 익을게 없는 경우 while문 탈출하도록 했다. import sys from collections import deque input = sys.stdin.readline m..

2644번 파이썬

bfs를 deque로 이용해서 문제를 풀음. 처음에 dfs 문제인줄 알고 dfs로 풀었지만 촌수 관계가 없을 때 -1을 출력하도록 하는 예외처리가 힘들어서 bfs를 이용해서 지난간 것은 전 노드에 +1씩 추가하여 목적지 b에는 몇촌 관계인지 표현할 수있도록 하였음. 방문여부는 그 해당 노드의 값이 0인지 아닌지 판별해서 구분!! import sys input=sys.stdin.readline from collections import deque n = int(input()) a,b = map(int,input().split()) m = int(input()) graph={} for _ in range(m): x,y=map(int,input().split()) if x not in graph: graph[..

10844번 파이썬

처음엔 n-1자릿수의 계단 수에 +-1을 더해서 n자리수의 계단 수를 구하는 방식으로 풀었는데 이 방식은 시간 초과뿐만 아니라 메모리도 초과됨... import sys input = sys.stdin.readline n = int(input()) ''' dx = [-1,1] stairs=[1,2,3,4,5,6,7,8,9] if n >= 2: for i in range(2,101): if n-i < 0: break #[i-2] 에 접근 ary=[] for item in stairs: for k in range(2): #끝자리만 확인 s_item=str(item) x = int(s_item[len(s_item)-1])+dx[k] if 0

2667번 파이썬

dfs 방식을 이용해 문제에 접근했고 번지 수를 구분하기 위해서 어떤 한 번지 내를 탐색할 때 번지 내에 있는 단지 수를 세면서 동시에 번지의 값을 다 0으로 바꿔서 다음 번지를 찾을 수 있도록 했다. import sys input = sys.stdin.readline n = int(input()) mat = [list(input()) for _ in range(n)] dx=[-1,1,0,0] dy=[0,0,-1,1] res=[] for i in range(n): for j in range(n): if mat[i][j]=='1': stack=[[i,j]] visited=[] cnt=0 while stack: item = stack.pop() if item not in visited: visited.app..

2606번 파이썬

저번에 풀었던 bfs 방법을 참고해서 풀음! import sys input = sys.stdin.readline from collections import deque v=int(input()) e=int(input()) graph={} for _ in range(e): n1,n2=map(int,input().split()) if n1 not in graph: graph[n1]=[n2] elif n2 not in graph[n1]: graph[n1].append(n2) if n2 not in graph: graph[n2]=[n1] elif n1 not in graph[n2]: graph[n2].append(n1) queue=deque([1]) visited=[] cnt=0 while queue: num =..

2178번 파이썬

dfs가 익숙해서 첨부터 dfs로 풀었는데 vscode상에선 문제없이 잘돌아갔지만 dfs로 풀면 시간 초과가 돼서 계속 답이 틀림... 인터넷 찾아보니 최솟값을 구하는 문제는 bfs로 풀면 훨씬 쉽게 풀린다고 한다. 실제로 저번에 이용했던 deque를 이용해서 구현했더니 코드도 간단해지고 반복문을 여러번 반복하지 않고 최솟값을 금방 구하는것 같다! import sys input = sys.stdin.readline from collections import deque n,m= map(int,input().split()) mat=[list(input()) for _ in range(n)] ''' def dfs1(mat, cnt, row, col,visited): if row == n-1 and col ==..

1260번 파이썬

bfs랑 dfs를 공부했던 블로그를 참고해서 했는데 정점과 간선을 이용한 그래프를 python의 dictionary를 이용하면 편리하게 정점 사이의 연결들을 관리할 수 있는 것 같다. dfs의 경우 stack의 pop과 정렬할 때 reverse 옵션을 true로 했는데 dfs가 깊이 탐색이다 보니 처음에 시작점으로 주어진 v에서 뻗쳐나갈 때 하나의 깊은 가지까지 다 뻗어나가고 나서야 다른 가지를 탐색하기 때문이다. 예를 들어 처음 입출력을 예로 들어 연결된 간선을 dic으로 표현하면 {1:[2,3,4],2:[1,4],3:[1,4],4:[1,2,3]}가 되는데 1번을 시작점으로 잡았을 경우 1(stack 배열이 reverse를 만나면서 [4,3,2]로 바뀜)->2( stack에서 2를 꺼내고 2랑 연결된 ..

1748번 파이썬

import sys input = sys.stdin.readline n = int(input()) a=len(str(n)) cnt=0 for i in range(a): cnt+=i*(10**i-10**(i-1)) cnt+=(n-10**(a-1)+1)*a print(int(cnt))

9095번 파이썬

import sys input = sys.stdin.readline cnt=[] def solution(n,num): if n ==num: cnt.append(1) return elif n

14500번 파이썬

아래 방법은 재귀를 이용해서 그런지 시간이나 메모리 소요가 커서 다른 방법을 생각해봐야함!(백준 pypy로 하면 맞춘걸로 나오긴 함) import sys input = sys.stdin.readline N,M = map(int,input().split()) mat=[list(map(int,input().split())) for _ in range(N)] res=set() def row_p(ary,num,cnt,row,col,n,m): if row < n: if [row,col] in ary: return num+=mat[row][col] ary.append([row,col]) solution(ary,num,cnt+1,row,col,n,m) ary.remove([row,col]) else: return r..