solved.ac 티어 : 플래 3 www.acmicpc.net/problem/18407 18407번: 가로 블록 쌓기 가로 블록만 등장하는 테트리스 게임을 해보려고 한다. 가로 블록은 총 N개가 등장할 예정이고, 등장하는 순서대로 1, 2, ..., N번이다. i번 블록의 높이는 1이고, 너비는 Wi이다. i번 블록은 왼쪽 벽 www.acmicpc.net 새로 떨어지는 블록은 자신의 구간에서의 최댓값+1이다. 그러므로 세그레이지로 max를 구해주고 max+1 값을 구간에 저장해준다. 그리고 max값이 최대 높이일 경우 최대 높이를 올려준다음 마지막에 나온 최대 높이를 출력해주면 된다. #include using namespace std; typedef long long ll; struct qu{ ll ..
solved.ac 티어 : 플래 5 www.acmicpc.net/problem/14574 14574번: 헤븐스 키친 남규는 요즘 군입대를 기다리며 하루 종일 유튜브를 본다. 남규가 가장 좋아하는 채널은 ‘Heaven`s kichen’이다. 이 프로그램에서는 N명의 요리사가 매일 둘씩 요리 대결을 펼치고, 승리한 요리사 www.acmicpc.net 모든 간선을 이어주고 가중치는 로 해준다. 그리고 스패닝 트리를 만들어 준다음에 사용한 간선들을 저장해서 트리를 만든 다음 dfs으로 탐색을 하면서 밑에부터 위로 가면서 출력해주면 된다. import sys sys.setrecursionlimit(10**9) m=int(input()) e=[] def find(a): if uf[a]
solved.ac 티어 : 골드 3 www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 이 문제는 각 섬들마다 다리를 이어서 모든 섬을 오갈 수 있게 하면서 다리의 길이가 최소가 되게 해야 된다. 이때 다리의 길이를 두 점의 가중치로 생각하면 최소 스패닝 트리가 된다. 이제 입력을 dfs으로 탐색해서 섬을 나누고 다리를 이은 다음 최소 스패닝 트리를 구해주면 된다. import sys sys.setrecursionlimit(10**9) a,..
solved.ac 티어 : 플래 3 www.acmicpc.net/problem/16404 16404번: 주식회사 승범이네 첫 번째 줄에 승범이를 포함한 판매원들의 수 N(1 ≤ N ≤ 100,000), 명령의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 판매원들은 1번부터 N번까지 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 판 www.acmicpc.net 이문제는 트리에 어떤 노드가 선택되었을 때 그 노드와 노드의 자식들에게 w만큼 값이 더해지는 문제다 대신 이 문제는 다른 평범한 세그먼트 트리처럼 이진트리가 아니다. 그럼 어떻게 할 수 있을까? 예시에 있는 입력을 가지고 트리를 만들면 이렇게 된다.(좀 이상한 건 어쩔 수 없다) A부터 E까지 순서대로 1,2,3,4,5라고 할 때 A..
solved.ac 티어 : 골드 4 www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제는 코드업의 극장 좌석 배치 2를 풀고 하면 쉽게 할 수 있다. codeup.kr/problem.php?id=2652 극장 좌석 배치 2 극장에 nn개의 빈 좌석이 있다. kk명의 관객들이 영화를 보기 위해서 왔다. 이 관객들이 nn개의 좌석에 앉을 수 있는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오. (단, kk명의 사람 codeup.kr 이 문제와 색상환의 다른 점은 색상환은 양..
solved.ac 티어 : 골드 4 www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 이문제는 설명은 길지만 요약하자면 m개의 줄에 2개의 점이 주어질 때 그 2개의 점이 같은 집합에 속하는 번째수를 출력하는 것이다. 이문제는 유니온 파인드로 풀 수 있다. import sys sys.setrecursionlimit(10**9) input=sys.stdin.readline n,m=map(int,input().split()) uf=[-1]*(n+1) def ..
solved.ac 티어 : 골드 2 www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 이문제는 단순하게 입력으로 들어오는 구간마다 하나씩 비교하면서 처리하는 방식은 시간 초과가 난다. 그럼 어떻게 할 수 있을까? 예를 들어 1 2 1 1 2 1 이면 배열이 있고 1 6이라는 입력이 들어왔다. 1 2 1 1 2 1은 팰린드롬이기 때문에 1을 출력해야 한다. 이때 양끝을 제외한 나머지가 팰린드롬이고 양쪽이 같을 경우 팰린드롬이 된다. 이걸 계속 적용한다면 범위의 값이 팰린드롬인지 아닌지를 알 수 있고 ..
solved.ac 티어 : 다이아 4 www.acmicpc.net/problem/16910 16910번: mex와 쿼리 mex는 어떤 수열에 포함되지 않은 수 중에서 가장 작은 자연수를 찾는 함수이다. 예를 들어, mex([1,2,3]) = 4, mex([5,3,1,1,4]) = 2, mex([1,5,2,1,5,2,1,2]) = 3이다. 비어있는 배열 A와 쿼리 N개가 주어졌을 때, www.acmicpc.net 생각보다 간단한 세그레이지이다. 1 l r: 구간 [l, r]에 속하는 모든 자연수를 배열 A에 추가한다. 배열에 이미 있는 자연수는 또 추가하지 않는다. 2 l r: 구간 [l, r]에 속하는 모든 자연수를 배열 A에서 제거한다. 3 l r: 구간 [l, r]에 속하는 모든 자연수 x에 대해서,..
solved.ac 티어 : 플래티넘 2 www.acmicpc.net/problem/1348 1348번: 주차장 세준 주차장은 R*C크기의 직사각형 모양이다. 세준 주차장에는 N개의 차와, M개의 주차 구역이 있다. 그리고, 모든 차는 주차 구역에 주차하려고 한다. 교통 제한 때문에, 차는 주차장의 경계와 평 www.acmicpc.net bfs를 사용해서 각 자동차(C)마다 모든 주차구역(P)과의 거리를 저장해주고 이분 탐색하면서 이분 매칭으로 나올 수 있는 최솟값을 찾아주면 된다. 이분 탐색은 mid가 있을 때 각 자동차마다 주차구역을 가는 거리가 mid이하인 값들만 가지고 이분 매칭을 해주면 된다. 이때 이분매칭 했을 때의 값이 자동차 개수와 동일하다면 mid와 저장되어있는 최솟값을 비교하여 더 작을 ..
- Total
- Today
- Yesterday
- 누적 합
- 선분 교차 판정
- 트리에서의 다이나믹 프로그래밍
- 정렬
- 이분 탐색
- A Dance of Fire and Ice
- 트리
- 이분매칭
- 그래프 이론
- discord bot
- C++
- 느리게 갱신되는 세그먼트 트리
- 최소 스패닝 트리
- KOI
- codeforces
- 개발
- BOJ
- 다이나믹 프로그래밍
- 그리디 알고리즘
- 완전 탐색
- 그래프 탐색
- 알고리즘
- 잡봇
- 자료 구조
- 수학
- 자료구조
- 세그먼트 트리
- 구현
- Python
- 깊이 우선 탐색
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |