전체 글

2108번 파이썬

collections에 있는 counter를 이용함 산술평균의 경우 처음엔 f-string을 썼는데 계속 틀렸다고 해서 round로 바꿨더니 해결됐다..! f-string이 특정 값일때 반올림을 잘 못하는 것 같은데 아마 첫째자리가 5인 음수이지 않을까라는 생각이 든다. counter의 most_common이라는 내장함수는 (숫자, 횟수)를 데이터 갯수가 많은 순으로 리스트로 리턴해준다. 미리 ary를 sort해놨기 때문에 첫번째랑 두번째 횟수가 동일한지만 비교하면 된다.(횟수가 동일하면 앞에꺼가 뒤에보다 더 작은 값임) import sys from collections import Counter input = sys.stdin.readline N = int(input()) a = [int(input()..

5014번 파이썬

처음에 조금 많이 틀려서 문제가 없는데 뭐가 문제인지 찾아봤다. 아무래도 처음 층을 방문 처리를 안해줘서 처음 층으로 돌아왔을 때 문제가 되는 것 같다. for 문도 문제가 되는 것 같아서 if로 바꿔서 했더니 잘됐다. import sys from collections import deque input = sys.stdin.readline f,s,g,u,d = map(int, input().split()) def bfs(s,f): queue = deque([s]) count = [0]*(f+1) count[s]=1 while queue: floor = queue.popleft() if floor == g: print(count[g]-1) return if (floor+u)0 and not count[fl..

1697번 파이썬

bfs를 이용한 문제 import sys from collections import deque input = sys.stdin.readline n, k = map(int, input().split()) queue = deque([n]) count = [0]*100001 while queue: roc = queue.popleft() if roc == k: print(count[k]) break if 0

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랑 연결된 ..