전체 글
-
백준 1937 python백준/다이나믹 프로그래밍 2023. 5. 1. 14:45
문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 DFS 알고리즘을 이용한다. 시간 초과를 피하기 위해 방문했던 V 배열은 기존의 순회 정보를 이용한다. (다이나믹 프로그래밍) import sys sys.setrecursionlimit(10**6) [n],*I=[list(map(int, x.split())) for x in [*open(0)]] V=[[0]*n for _ in range(n)] def dfs(x,y): if ..
-
백준 2052 python백준/수학 2023. 4. 24. 18:04
문제 https://www.acmicpc.net/problem/2052 2052번: 지수연산 자연수 N(1 ≤ N ≤ 250)이 주어졌을 때, 2의 -N승을 계산하는 프로그램을 작성하시오. 즉, 1/(2N)을 계산하는 것이다. www.acmicpc.net 풀이 2**-N을 소수점 아래 250자리까지 구한다. 뒤에서 0이 아닌 i 값을 찾는다. o='%.250f'%2**-int(input()) i=len(o)-1 while o[i]=='0': i-=1 print(o[:i+1]) 참조 https://jinho-study.tistory.com/457 백준 알고리즘 2052번 지수연산(python) 10**-4보다 작은 분수는 괜찮은데 그거보다 작은 분수는 1e-05와 같은 방식으로 저장이 되어있어서 따로 처리..
-
순열과 조합 itertools 사용법 정리기타/Python 2023. 4. 10. 18:08
순열 from itertools import permutations for x in permutations([1,2,3,4],2): print(x) // (1,2),(1,3),(1,4),...(4,3) 조합 from itertools import combinations for x in combinations([1,2,3,4],2): print(x) // (1,2),(1,3),(1,4),...,(3,4) 두 경우 모두 튜플로 반환된다. sorted를 사용해 정렬이 가능하다.
-
백준 16943 python백준/브루트포스 알고리즘 2023. 4. 10. 17:59
문제 https://www.acmicpc.net/problem/16943 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0 www.acmicpc.net 풀이 파이썬 내장 순열 알고리즘을 이용해 튜플을 생성한다. 크기 순서대로 정렬하여 조건에 맞는 정답을 찾는다. from itertools import permutations A,B=map(int, input().split()) A=list(map(int, str(A))) o=-1 for num in sorted(permutations(A,len(A))): if num[..
-
백준 1926 python백준/깊이 우선 탐색 2023. 3. 27. 16:45
문제 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 풀이 DFS를 이용한다. 재귀로 풀 경우 메모리 초과가 발생하므로 stack을 이용한다. n,m=map(int, input().split()) I,O=[[*map(int, input().split())] for _ in range(n)],[0,0] def dfs(sx,sy): stack,S=[],0 I[sx][sy]=0 stack.append([sx,sy]) while(len(stack)>0): ..