solved.ac 티어 : 골드 3 www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 태그는 bfs(너비 우선 탐색)이 붙어있긴하지만 bfs를 안쓰고 dfs와 몇번의 전체 탐색만 해주면 된다. 탐색해서 알아내야할 정보는 한 위치로부터 x축으로 가장 가까운 섬과의 거리,그 위치로부터 y축으로 가장 가까운 섬과의 거리, 섬의 번호, 한 위치로부터 가장 가까운 섬의 번호 이렇게 4개를 알아내면 된다. 입력 예시로 예를 들면 # # # 1 2 2 1 # # # # # # ..
solved.ac 티어 : 골드 4 www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 문제보면 바로 다익스트라인걸 알수있다. 다익스트라를 구현해주고 출력하면 된다. import sys,math input=sys.stdin.readline n,m=map(int,input().split()) adj=[[]for i in range(n)] inf=math.inf for i in range(m):a,b,c=..
solved.ac 티어 : 골드 4 www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 이문제는 의외로 간단한데 어떤 노드에서 와 연결된 노드들 중에 재일 마지막 노드까지의 거리가 첫 번째로 큰 값과 두 번째로 큰 값의 합이 그 노드를 포함했을 때 가장 긴 길이이다. 이걸 dfs으로 탐색하면서 노드별로 가장 긴 길이 중에서도 가장 긴 길이를 출력하면 된다 . 예시로 봤을 때 4번 노드를 포함하는 최대 길이는 8이다. 4의 자식 노드를 포함하는..
solved.ac 티어 : 골드 4 www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net bfs으로 (1,1)부터 탐색을 해주는데 기회가 남아있을 때 벽을 만났다면 기회를 없애고 벽 위치를 스택에 추가해주면서 탐색을 하다가 (n, m)에 도착했을 때의 횟수를 출력하면 된다. import sys from collections import deque input=sys.stdin.readline a,b=map(int,input().split()..
solved.ac 티어 : 골드 3 www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 어느 한 위치를 선택했을 때 그 위치에서 최대로 갈 수 있는 개수를 저장하고 dfs를 돌면 된다. 최대 개수 구하는 방법은 한쪽으로 쭉 내려가고 더이상 내려갈 수 없을 때부터 +1씩 해주면 된다. import sys sys.setrecursionlimit(10**9) input=sys.stdin.readline a=int(input()) l=[list(map(int,..
solved.ac 티어 : 플래 3 www.acmicpc.net/problem/18437 18437번: 회사 문화 5 총 N명의 직원이 재직 중인 회사가 있고, 각 직원은 1번부터 N번까지 번호가 매겨져 있다. 이 회사는 수직적인 구조를 가지고 있고, 대표를 제외한 모든 직원은 한 명의 직속 상사를 갖고 있다. www.acmicpc.net 컴퓨터가 켜져 있는 상태를 1, 컴퓨터가 꺼져있는 상태를 0으로 두고 구간을 1 또는 0으로 변경한 뒤 구간 합을 출력하면 된다. #include using namespace std; typedef long long ll; typedef pair nod; const ll N=1000000; ll n,m; vector graph[N]; nod Qu[N]; ll cnf=0..
solved.ac 티어 : 플래 3 www.acmicpc.net/problem/14288 14288번: 회사 문화 4 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 이 문제는 회사 문화 2, 회사 문화 3를3을 합친 문제인데 회사 문화 2를 저장하는 트리와 회사 문화 3을 저장하는 트리를 만들고 각각 업데이트를 해준 뒤 출력할 때 회사 문화 2의 출력 값+회사 문화 3의 출력 값을 해주면 된다. BOJ 14268(회사 문화 2)풀이 solved.ac 티어 : 플래티넘 3 www.acmicpc.net/problem/14268 14268번..
solved.ac 티어 : 플래티넘 4 www.acmicpc.net/problem/14287 14287번: 회사 문화 3 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 이 문제는 다른 회사 문화 문제와는 다르게 위에서 아래로 값을 더해주는 것이 아닌 밑에서 위로 값을 더해주는 문제이다. 이 문제의 풀이는 생각보다 간단하다. dfs으로 새로 해당 구간을 만들고 그 구간에 대한 이진트리를 그리고 x노드의 값에 w를 더한다고 해보자. 그러면 x를 가지고 있는 구간에만 변경이 생긴다. 그러므로 구간이 (x,x)인 위치에 w를 더해주면 x를 포..
solved.ac 티어 : 플래티넘 3 www.acmicpc.net/problem/14268 14268번: 회사 문화 2 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 회사 문화 1과 같은 문제인데 1은 마지막에 모든 정점마다 합을 구해주는 거고 2는 2가 들어올 때마다 구간의 합을 구해주는 것이다. BOJ 14267(회사 문화 1)풀이 solved.ac 티어 : 골드 4 www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가..
solved.ac 티어 : 골드 4 www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net dfs으로 각 위치마다 구간을 새로 저장해준 뒤 입력으로 들어오는 값의 구간에다가 w를 더해주고 마지막에 1부터 n까지 i번째점의 구간 합을 출력해주면 된다. #include using namespace std; typedef long long ll; typedef pair nod; const ll N=1000000; ll n,m; vector graph[N]; nod Qu..
- Total
- Today
- Yesterday
- KOI
- 개발
- 그래프 탐색
- BOJ
- 자료 구조
- 자료구조
- 다이나믹 프로그래밍
- 수학
- 이분 탐색
- 세그먼트 트리
- codeforces
- 트리에서의 다이나믹 프로그래밍
- discord bot
- 트리
- 정렬
- 잡봇
- 그리디 알고리즘
- 이분매칭
- 최소 스패닝 트리
- 그래프 이론
- C++
- Python
- 구현
- 완전 탐색
- A Dance of Fire and Ice
- 누적 합
- 깊이 우선 탐색
- 알고리즘
- 느리게 갱신되는 세그먼트 트리
- 선분 교차 판정
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |