본문 바로가기
728x90
반응형

Python169

2022.03.07 [백준] (python 파이썬) 구간 합 구하기 4 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 풀이 이 문제는 주어진 범위를 for문을 돌며 합을 구하면 시간초과가 발생한다. 그래서 다른 배열에 각 인덱스 까지의 합을 저장한 후, i~j까지 합을 sums[i]-sums[j-1]처럼 누적합을 이용하여 구하면 시간초과를 피할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 import sys input=sys.stdin.readline n,m=.. 2022. 3. 7.
2022.03.06 [백준] (python 파이썬) Four Squares https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 풀이 이 문제는 다이나믹 프로그래밍을 이용해서 0~n까지 필요한 제곱수의 갯수를 더한 값을 저장했다. n보다 작거나 같은 제곱수를 찾고 n-제곱수의 인덱스의 값에 +1을 해주었다. 만약 26이면 26보다 작거나 같은 제곱수를 25이고 26-25는 1이다. 이때 인덱스 1의 값은 1이다. 그래서 1+1을 해주면 2가 된다. 1 2 3 4 5 6 7 8 9 10 1.. 2022. 3. 6.
2022.03.06 [백준] (python 파이썬) 비밀번호 찾기 https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 풀이 이 문제는 주소와 비밀번호를 함께 저장 후, 주소로 비밀번호를 찾아야 한다. 그래서 딕셔너리를 이용해 키에 주소, 값에 비밀번호를 저장해서 원하는 주소의 비밀번호를 찾았다. 1 2 3 4 5 6 7 8 9 10 11 12 13 import sys input=sys.stdin.readline n,m=map(int, input().split()) id_pass={}.. 2022. 3. 6.
2022.03.06 [백준] (python 파이썬) DSLR https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 코드를 작성 할 때, D,S,L,R상황을 모두 생각해 주어야한다. 그래서 각 상황을 함수로 만들었다. 이 후 x가 y가 되기 위한 최소한의 움직임을 저장해야 하기 때문에 deq에 (바뀐 숫자, 수행한 연산)을 저장해 연산을 하게 되면 숫자와 연산을 업데이트해 deq에 저장해주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2.. 2022. 3. 6.
728x90
반응형

티스토리툴바