18436 수열과 쿼리 37 python https://www.acmicpc.net/problem/18436 18436번: 수열과 쿼리 37 길이가 N인 수열 A1, A2, ..., AN이 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i x: Ai를 x로 바꾼다. 2 l r: l ≤ i ≤ r에 속하는 모든 Ai중에서 짝수의 개수를 출력한다. 3 l r: l ≤ i ≤ r www.acmicpc.net 문제 접근 세그먼트 트리문제 짝수와 홀수를 따로 저장해야할까 고민했는데, 저장할때 2로 나눠서 저장하면 한번에 계산된다는것을 파악했다. 0아니면 1로 저장을 한 다음 구간 합을 구한다. 구하려는 범위의 구간합은 홀수고 범위에서 구간합을 빼면 짝수가 나온다 코드 import sys import math input = sys.stdi.. 2243 사탕상자 python https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 문제 접근 세그먼트 트리로 구현했다. 구간 합에서 개수를 파악하고 좌측과 우측중 어디로 이동할지 판별하면 된다. 현재 노드에서 자식노드중 좌측의 크기보다 현재 접근하려는 개수가 더많으면 우측으로 이동하면 된다. 시간 메모리도 잘나왔고 1트에 코드도 엄청 짧게나와서 만족스럽다 코드 import sys import math input = sys.stdin.readline ".. 10999 구간 합 구하기 2 python https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 접근 세그먼트 트리로 그냥 풀면 틀릴것같아서 좀 찾아봤다. 느리게 갱신되는 세그먼트 트리라는게 있어서 공부했더니 쉽게 풀렸다. 방법은 아래 링크에서 잘알려준다 https://book.acmicpc.net/ds/segment-tree-lazy-propagation 느리게 갱신되는 세그먼트 트리 소스 1void update_ran.. 2024 구간 합 구하기 python https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 접근 세그먼트 트리로 쉽게 풀렸다. 구간 합을 세그먼트 트리의 각 노드에 적으면서 올라가면 쉽게 풀린다. 코드 import sys import math input = sys.stdin.readline """ 1. """ N, M, K = map(int, input().split()) node = 2**math.ceil(math.log.. 13537 수열과 쿼리 1 python https://www.acmicpc.net/problem/13537 13537번: 수열과 쿼리 1 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. www.acmicpc.net 문제 접근 세그먼트 트리에 재미붙어서 풀다가 발견한 문제다. 순서대로 쭉 풀어볼까 싶기도 한 문제인데... 다이아급 문제는 거를거같다. 너무빡새ㅜ 세그먼트 트리로 구현하는데, 부분정렬시키면서 트리를 구현했다. 풀고 알았는데 머지 소트 트리라고 이미 있는 방법이다. 부분정렬 시킨 트리에서 범위에 포함되는 노드들을 선택해서 k보다 큰값을 탐색해서 return하면 된다.. 14427 수열과 쿼리 15 https://www.acmicpc.net/problem/14427 14427번: 수열과 쿼리 15 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 www.acmicpc.net 문제 접근 세그먼트 트리를 이용해서 풀었다. 세그먼트 트리는 구간합을 구하는 문제에서 쓰이지만 아래의 leaf노드가 아닌 다른 노드에는 구간합을 적어두는 방식으로 사용한다. 이 문제에선 구간합이 아닌 최소값을 비교해서 더작은 값을 적어두는 방식으로 진행했고 루트노드에 최소값을 적어두는것으로 해결했다. 세그트리는 다양하게 쓰이는듯 하다. 세그트.. 16637 괄호 추가하기 https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net 문제 접근 괄호를 넣지않고 미리 계산하는 방식으로 dfs를 써서 구현했다. 괄호를 쓰지않는경우, 4칸을 묶는경우, 그 이상 묶는경우 3가지로 구분했다. 괄호를 쓰지않으면 처음 인덱스에서 2칸을 건너가면 된다. 괄호를 쓰는경우 4칸을 건너가서 묶어 계산하면 되고 만약 그이상 묶는경우라면 굳이 6칸을 묶을필요없이 4칸묶고 2칸묶는것과 결과가 같다. 그래서 4칸묶기와 2칸묶기 경우로 나눠서.. 플로이드-워샬 알고리즘 플로이드-워샬 알고리즘 시간복잡도 O(N^3) 정점에서 다른 정점까지 최단거리를 구하는 알고리즘. 다익스트라 알고리즘은 한 정점에서 다른 정점까지 최단거리를 구하는 알고리즘이라면 플로이드-워샬 알고리즘은 모든 정점을 다른정점과 최단거리를 구해주는 알고리즘이다. 방법 꼭지점 k를 중간 노드로 삼아서 모든 그래프가 k를 지나가는 방법과 바로가는 방법중 더 작은 값을 새로 등록한다. 위와같이 있을때 k가 3이라고 가정하면 1->4와 1->3->4로 나눠보고 더 작은값인 1->4의 4를 채택해서 새로 등록한다. 모든 k에 대해서 반복하고 모든 2차원 그래프를 탐색하니 O(N^3)의 시간복잡도가 된다. 코드 for k in range(N): for i in range(N): for j in range(N): ar.. 16566 카드 게임 (python) https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 문제 접근 이분탐색과 분리집합을 섞은 문제 2022.12.10 - [백준/이론_python] - Union & Find 알고리즘 Union & Find 알고리즘 Union & Find union & Find 이라는 알고리즘은 Union과 Find으로 이루어져있다. Union은 합치기 Find는 찾기 두 집합이 같은 집합에 있는지 확인하기위해 트.. 20040 사이클게임 (python) https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 문제 접근 운이 좋았나... 바로 union & find가 떠올랐다. 이었을때 두 점이 둘다 같은 부모를 가르킨다면 사이클이 돌고있다는 뜻. 그때를 출력하면된다 코드는 생각나는대로 쭉 썼는데 시간도 여유롭게 통과됐다 코드 import sys input = sys.stdin.readline """ """ def find(x): if parent[x] != x: parent[x] = find(p.. 15686 치킨 배달 (python) https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 접근 각 치킨집에서 집까지 거리를 BFS로 풀고있었다. 다적고나니 BFS로 풀 필요가 없고 그냥 구할 수 있었다는걸 알았다... 치킨집과 일반 집의 위치를 찾고, 각 거리를 구했다. 그리고 거리들에서 치킨집중 M개만큼 뽑아서 그 중 최소값들을 더한게 도시의 치킨 거리다. 약간의 깡 구현이 있었는 듯 from itertools import combinations는 쓰지않았.. 9663 N_Queen (python) https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 접근 거의 시간 빠듯하게 제출했다. DFS로 깡구현하듯 재귀로 깡구현해버렸다 10초라 넉넉해서 이방식으로 했는데 자칫하면 시간초과할뻔했다... x축이 같거나 대각선에 위치하는지 체크하고 모든 포지션에 둬보고 가능하다면 stack에 넣는 방법으로 구현했다. 코드 import sys input = sys.stdin.readline """ 앞에 stack에 저장된 값과 현재 위치의 차이의 절대값 x==y라면 ㄴㄴ.. 이전 1 2 3 4 ··· 14 다음
