kwan's note

난이도: 실버2 번호:9633번 그래프의 DFS BFS탐색에 관한 문제이다. DFS와 BFS의 정의를 알고 구현할 수 있으면 쉽게 풀 수 있는데 bfs를 처음 풀어봐서 왜 queue를 이용해야 하는지 몰라서 오래걸렸다. from sys import stdin import time as t s=t.time() def dfs(node): print(node, end=' ') visitdfs[node] = 1 for i in range(1,N+1): if visitdfs[i] == 0 and matrixmap[node][i] == 1: dfs(i) def bfs(node): tovisit =[node] visitbfs[node]=1 while tovisit: node=tovisit[0] print(tovisi..

난이도: 골드5 번호:9633번 백트래킹문제로 python3는 시간을 만족시키지 못해 pypy3로 제출하여 통과하였다. row를 기준으로 한줄씩 내려가면서 모든 column에 숫자를 넣을 수 있는지 체크하면서 풀어내려갔다. from sys import stdin def queendfs(row): global count if (row==N): count +=1 return for j in range(N): checkpoint = True for n in range(len(queenlist)): if queenlist[n][1] == j or abs(queenlist[n][0] - row) - abs(queenlist[n][1] - j) == 0: checkpoint=False break if checkpo..

문제번호:15651 난이도: 실버3 간단한 dfs 백트래킹 문제이다. 1번의 쉬운버전(check 필요 없음)이다. checklist를 제거하고 동일하게 작성하였다 from sys import stdin def dfs(cnt): if(cnt==M): print(*answer) return for i in range(N): checklist[i]=True answer.append(numlist[i]) dfs(cnt+1) answer.pop() if __name__ == '__main__': N,M= map(int,stdin.readline().split()) numlist = [i+1 for i in range(N)] answer=[] dfs(0)

문제번호:15650 난이도: 실버3 기존 1번문제에서 reminder-by-kwan.tistory.com/47 길이가 이전숫자보다 새로 들어오는 숫자가 커야한다는 조건을 추가하였다 백준-15649번 N과 M (1) 파이썬 (python code) 문제번호:15649 난이도: 실버3 간단한 dfs 백트래킹 문제이다. 삼성 sds 동계알고리즘 특강을 들으며 dfs문제 이해가 오래걸려 기본문제부터 풀어보게 되었다. from sys import stdin def dfs(cnt): if(cnt==M):.. reminder-by-kwan.tistory.com from sys import stdin def dfs(cnt): if cnt == M: print(*answer) return for i in range(N)..

문제번호:15649 난이도: 실버3 입력이 하나일때에 대한 예외처리와 최빈값이 여러개일때의 처리에 유의하면서 풀어보자. from sys import stdin,exit from collections import Counter if __name__ == '__main__': num= int(stdin.readline().rstrip()) mylist=[(int(stdin.readline().rstrip())) for _ in range(num)] mylist.sort() print(round(sum(mylist)/num)) print(mylist[int(num/2)]) cmm=Counter(mylist).most_common() if(len(mylist)>1): print(cmm[0][0] if cmm[0..

문제번호:15649 난이도: 실버3 간단한 dfs 백트래킹 문제이다. 삼성 sds 동계알고리즘 특강을 들으며 dfs문제 이해가 오래걸려 기본문제부터 풀어보게 되었다. from sys import stdin def dfs(cnt): if(cnt==M): print(*answer) return for i in range(N): if(checklist[i]==False): checklist[i]=True answer.append(numlist[i]) dfs(cnt+1) answer.pop() checklist[i]=False if __name__ == '__main__': N,M= map(int,stdin.readline().split()) numlist = [i+1 for i in range(N)] answ..

문제번호:11399 난이도: 실버3 총 대기시간의 최솟값을 계산하는 문제이다. 한번만 생각해보면 제일 짧은사람부터 줄을 서는것이 가장 빠르다는것을 알 수 있다. N명이 있을때 첫번째는 N만큼의 가중치를 가지고 2번째는 N-1의 가중치를 가지는 식이다. 따라서 아래와 같이 작성해보았다. import sys def Sort(number): Sortlist=sys.stdin.readline().rstrip().split(' ') for i in range(number): Sortlist[i]=int(Sortlist[i]) Sortlist.sort() addnum=0 for j in range(number): addnum+=(number-j)*Sortlist[j] print(addnum) if __name__ ..

문제: 백준 2751번 난이도: 실버5 난이도는 실버5지만 파이썬으로는 아주 쉬운 sort문제이다. 다만 첫 시도에서 시간초과가 떠서 다른 코드를 보던중 input()이 아닌 sys.stdin.readline()을 사용하여 통과한것을 봤고 이것만 바꿔서 작성했더니 통과하였다. 이러한 차이는 input과 sys.stdin.readline과의 차이에서 발생했는데 input 은 parameter에 prompt message를 받을 수 있어 입력받기 전 prompt message를 출력한다. 아무것도 적지 않더라도 말이다.​ 하지만, sys.stdin.realine()은 prompt message를 받지 않는다. 여기서 속도차이가 발생한다. 한가지 추가적인 차이점은 ​input()은 입력받은 값의 개행 문자(\..