[파이썬] 백준 22659 : 구간 합 구하기4

[파이썬] 백준 22659 : 구간 합 구하기4 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 실버 3 누적 합 입력받는 리스트의 범위가 100000이나 되므로 반복문으로 단순구현하면 시간초과가 난다. 따라서 각 인덱스까지의 값을 따로 저장할 리스트를 구현하고 필요한 값을 뽑아쓰는 방식으로 접근해야 한다. 반복문을 사용해 이를 만들어 낼 수 있지만, itertools의 accumulate를 사용하면 해당 리스트의 누적합..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 24.
• textsms

[파이썬] 백준 9461 : 파도반 수열

[파이썬] 백준 9461 : 파도반 수열 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 실버 3 수학, DP 숫자들을 쭉 깔아서 보면 바로 규칙이 보일 것이다. 1, 1, 1, 2, 2, 3, 4, 5, 7, 9... i번째의 값은 i-3과 i-2번째의 값의 합으로 이루어져있는 피보나치 수열과 비슷한 규칙을 가지고 있다. import sys; input = sys.stdin.readline T = int(input()) for _ in range(..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 24.
• textsms

[파이썬] 백준 17626 : Four Squares

[파이썬] 백준 17626 : Four Squares https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 실버 4 DP, 브루트포스 접근 DP문제에 대한 자신감을 박살내버리는 문제였다. 다른 사람 풀이를 보고도 좀처럼 이해가 되지 않아 골머리를 앓았다. 문제에 따르면 어떤 수든 간에 최대 4개가지의 제곱수의 합으로 표현이 된다고 해서 1부터 쭉 공책에 써봤다. 1 = 1^2 = 1개 2 = 1^2 * 2 = 2개..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 18.
• textsms

[파이썬] 백준 2630 : 색종이 만들기

[파이썬] 백준 2630 : 색종이 만들기 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 실버 3 분할정복, 재귀 분할정복에서 가장 기본적인 문제라고 한다. 문제에서 4등분을 범위를 어떻게 잡아야하는지 친절하게 알려주고 있었다. 종이들을 2차원 리스트로 입력받도록 하고, 각각의 값들을 돌면서 모두가 통일된 값을 가지고 있는지 확인해야 한다. 각 사각형의 제일 왼쪽 위를 기준점으로 잡고, 나머지 값들이 기준점의 값과 ..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 18.
• textsms

[파이썬] 백준 11279 : 최대 힙

[파이썬] 백준 11279 : 최대 힙 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 실버 2 우선순위 큐, 자료구조 최소 힙을 응용해서 푸는 문제. 파이썬의 heapq모듈은 최소 힙을 구현할 수 있도록 만들어져 있기 때문에 최대 힙을 구하려면 약간의 조작이 필요했다. 코드 import heapq, sys; input = sys.stdin.readline N = int(input()) heap = [] for i in ra..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 15.
• textsms

[파이썬] 백준 1927 : 최소 힙

[파이썬] 백준 1927 : 최소 힙 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 실버 2 우선순위 큐, 자료구조 파이썬의 heapq 모듈이 최소 힙 자료구조를 제공하고 있다. 원소들이 항상 정렬된 상태로 추가되고 삭제되며, 가장 작은 값은 언제나 인덱스 0번째에 위치한다. 또한 모든 원소 k는 항상 2k+1, 2k+2번째 인덱스의 원소보다 크기가 작거나 같도록 정렬된다. 코드 import sys; input = sys...

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 15.
• textsms