[파이썬] 11054 가장 긴 바이토닉 부분 수열
2022. 2. 11. 00:15
프로그래밍/파이썬
11053 문제에이어 나오는 문제이다 11053에서는 예시인 [1 5 2 1 4 3 4 5 2 1] 에서 증가하는 수열인 [1 2 3 4 5] 를 찾는거였다면 이번에는 5까지 증가 후 줄어드는 2, 1까지 포함시켜 [1 2 3 4 5 2 1]을 찾는 문제이다 경우의 수는 2가지가있다 [1 5 2 1 4 3 4 5 2 1] [1 5 2 1 4 3 4 5 2 1] 위는 7, 아래는 6이다 사실 우리는 한방에 찾을 필요가 없다 증가하는 최댓값 + 감소하는 최댓값을 하면 그게 답이다 일단 코드를 보자 n=int(input()) ary=list(map(int, input().split())) dp=[1]*n r_dp=[1]*n ans = [0]*n for i in range(n): for p in range(i)..
[파이썬] 9020 골드바흐의 추측
2022. 2. 8. 07:30
프로그래밍/파이썬
사실 좀 미루고 미뤘던 문제이다 문제 자체는 쉬운데 어떻게 뽑아낼지가 약간 고민인 문제였다 오늘 한 번 풀어보자라는 생각으로 시도했는데 그 결과들은 처참했다.. 사실 4개는 같은 코드이다 뭔가 잘못 적혔나..? 하면서 바꾸다 보니 저리 나왔는데.. 여하튼 문제점은 하나다 일단 문제가 된 코드를 보자 import sys input = sys.stdin.readline ary = [False]*10001 for i in range(2, 10001): cnt =0 for p in range(2, int(i**0.5)+1): if i%p ==0: cnt=1 if cnt ==0: ary[i]=True num = int(input()) cnt == False for i in range(int(num)): cnt =..
[파이썬] 1759 암호 만들기 feat. 백트래킹
2022. 2. 7. 09:25
프로그래밍/파이썬
[파이썬] 15649 N과 M (1) feat 띠용하다! 오늘은 백트래킹을 풀어보기로 했다 사실 dfs 가 적혀있어서 그래프를 마치고 하려 했는데 dfs만으로도 풀 수 있는데 왜 묵히고 있었을까!라는 마음에 그냥 들어가 보기로 했다 문제는... 사실 for hbyun.tistory.com 저번 글을 읽고 자신감이 붙어서 이번에는 골드5가 적힌 백트래킹 문제로 가보았다 결론은 n, k 그리고 k 만큼의 알파벳이 주어지고, 그 알파벳들을 n개 만큼의 길이를 가진 리스트로 쭉 정렬해서 출력하는 것이다 근데 막상 보니 15649 문제와 매우 비슷하다 이전 15649 문제를 이해했다면, 금방 풀 수있다.. 라고 생각했다 각 문자를 그냥 숫자처럼 다루면 풀 수있다 ! 라는 생각으로 배열에 알파벳들을 넣고 풀트래킹을..
[파이썬] 15649 N과 M (1) feat 띠용하다!
2022. 2. 4. 04:08
프로그래밍/파이썬
오늘은 백트래킹을 풀어보기로 했다 사실 dfs 가 적혀있어서 그래프를 마치고 하려 했는데 dfs만으로도 풀 수 있는데 왜 묵히고 있었을까!라는 마음에 그냥 들어가 보기로 했다 문제는... 사실 for문으로 풀까 생각했다 근데 그러면 백트래킹이 아니라 브루트 포스가 아닌가! 결국 for문을 적절하게 제어할만한 방법이 필요하다 거기서 dfs를 쓴다는 것을 알게 되었다 사실문제 보고 답이 없어서 구글링을 하면서 수십 개의 답을 봤다 결국 메커니즘은 같았는데 이러하다 1. 숫자 2개를 받아 dfs 시작 2. 4, 4일 경우 1부터 시작해서 4까지 가면서 배열에 for숫자를 넣어준다 근데 여기서 for 숫자 하나에 각각 dfs를 걸어준다 예를 들어서 for i==1일 때 dfs를 걸어 다시 1부터 시작하게 한다 ..