전체 글

2579번 파이썬

n번째 계단을 밟았을 때 최댓값을 구하는 경우는 1. n-1번째 계단을 밟았을 경우 n-2번째 계단을 밟으면 안되기 때문에 n-3번째 계단까지의 최댓값에 n-1번째 계단값과 n번째 계단값을 더해준다. 2. n-2번째 계단을 밟았을 경우 n-2번째 계단까지의 최댓값에 n번째 계단값을 더해준다. 그리고 n이 1일 경우랑 2일 경우를 구분해주지 않으면 index error가 날 수 있다! import sys input = sys.stdin.readline n = int(input()) ary = [int(input()) for i in range(n)] count = [0]*301 if n == 1: count[1]=ary[0] elif n == 2: count[2]=ary[0]+ary[1] else: cou..

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 ==..