본문 바로가기

baekjoon

 (55)
15684번 사다리 조작 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 백트래킹, 구현 문제이다. 1. 문제 조건에서 3 이상이면 -1을 출력하면 되기 때문에 사다리를 각각 0, 1, 2, 3개씩 놓을 수 있다고 가정한다. 2. 사다리가 연속되면 안되므로 사다리를 놓을 때 고려해줘야 한다. 3. 사다리가 정해준 만큼 놓아지면 i번째 사다리가 i번째로 돌아오는지 확인한다. #include #define l long long #define INF 2e9 #define ..
15685번 드래곤 커브 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 구현 문제이다. 먼저 예시를 보면 규칙이 있다. 0세대 0 1 세대 01 2세대 01/21 3세대 0121/2321 0세대를 뒤집고 + 1 씩 하면 1세대고 1세대를 뒤집고 + 1씩 해주면 2세대가 된다. 이런 형태로 문제를 구현하면 된다. #include #define l long long #define INF 2e9 #define p pair #define vc ve..
14499번 주사위 굴리기 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 구현 문제이다. 나 같은 경우는 아래와 같이 풀었다. 1. (북·남), (서·동)으로 움직일 때 양옆은 생각 안 해도 된다. 2. (북·남) 움직일 때의 함수 하나 만들고 (서·동) 움직일 때 함수를 따로 만들어 준다. 3. 북 또는 남으로 움직일 때 x 좌푯값을 갱신해주고 x가 board를 초과하면 주사위를 굴리지 않는다. 4. ..
7662번 이중 우선순위 큐 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 우선순위 큐와 map을 이용하여 풀었다. 가장 먼저 maxQ와 minQ를 모두 만들어 데이터를 넣은 후 데이터를 삭제 할땐 maxQ와 minQ모두 삭제 해야 하므로 map을 이용하여 if(map == 0)일때 데이터를 삭제해줬다. #include #define l long long #define INF 2e9 #define p pair #define vc vector #define F firs..
17404번 RGB거리 2 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net RGB거리 1과 유사한 문제지만 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다. 밑줄 친 부분의 조건이 추가되었다. 따라서 DP의 초깃값을 정할 수 없으므로 1번 집을 빨간색으로 고정, 초록색으로 고정, 파란색..
2887번 행성 터널 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 최소 스패닝 트리 문제이다. 모든 경로의 거리를 배열에 담아두면 100,000 * 100,000이므로 메모리 초과가 난다. 따라서 x,y,z를 따로 두어 비용이 가장 가깝도록 각 좌표마다 정렬을 시킨다. 예를 들어 x의 좌표가 3(A) 2(B) 10(C) 5(D)였다면 x 좌표를 정렬 시킨 후 2(B) 3(A) 5(D) 10(C)가 되고 B -> A로 가는 비용 1..
4386번 별자리 만들기 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 0....n-1까지 모든 거리를 dist 배열에 담아주고 정렬시켜 크루스칼 알고리즘을 썼다. #include #define l long long #define INF 2e9 #define p pair #define vc vector using namespace std; int root[101]; int Find(int x){ if(root[x] == x) return x; else return ro..
1647번 도시 분할 계획 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 마을을 두개로 분할해야하며 각 마을은 서로 길이 이어져야한다. 여기서 중요한 점은 마을에 집이 하나 이상 있어야 한다는 것이다. 이게 뭘 뜻하냐면 예를 들어 길을 연결하는 비용을 오름차순으로 연결했다고 치자 그러면 마지막 길 연결 비용이 가장 클 것이다. 따라서 마지막 길만 다른 마을로 보내면 그 길을 연결해도 되지 않으므로 마을 연결 비용이 최솟값이 된다. ..
1753번 최단 경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 다익스트라 알고리즘의 기초 문제이다. #include #define l long long #define INF 2e9 #define p pair #define vc vector #define X first #define Y second using namespace std; int V,E,k,u,v,w; vc arr[200001]; int dist[200001]..
1197번 최소 스패닝 트리 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 크루스칼 알고리즘을 이용해 구현하였다. 비용을 오름차순으로 정렬시키고 부모노드가 같은지 확인하면서 최소 비용을 더해가면 된다. #include #define l long long #define INF 2e9 #define p pair #define vc vector using namespace std; int root[10001]; int Find(i..
14428번 수열과 쿼리 16 https://www.acmicpc.net/problem/14428 14428번: 수열과 쿼리 16 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 www.acmicpc.net 14427번과 똑같은 문제이다. 다만 구간이 추가된다. #include #define l long long #define INF 2e9 #define p pair #define vc vector using namespace std; p init(int st,int en,int node,vc &v,vector &tree..
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 기본적인 세그먼트 트리 문제이다. 특별한 점은 최솟값의 인덱스를 출력해야 한다. tree를 pair로 만들어서 가장 작은 값 저장, 인덱스값 저장해주면 된다. #include #define l long long #define INF 2e9 #define p pair #define vc vector using namespace std; p in..
18917번 수열과 쿼리 38 https://www.acmicpc.net/problem/18917 18917번: 수열과 쿼리 38 3번째 쿼리가 끝난 이후 배열의 상태는 [0, 3, 1, 4]이다. 6번째 쿼리가 끝난 이후 배열의 상태는 [0, 3, 1, 4, 1]이다. 10번째 쿼리가 끝난 이후 배열의 상태는 [0, 3, 1]이다. www.acmicpc.net 누적 합을 써서 푸는 문제이다. xor 특성상 자기 자신과 XOR 하면 0이 되기 때문에 2번 연산으로 삭제 시킬 때 한 번 더 XOR 해주면 된다. #include #define l long long #define INF 2e9 #define p pair #define vc vector using namespace std; int main(){ ios_base::sync_w..
18436번 수열과 쿼리 37 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 ≤ www.acmicpc.net 2일땐 [i,j]에서 짝수의 개수, 3일땐 [i,j]에서 홀수의 개수를 구하면 된다. 먼저 나는 짝수의 개수와 홀수의 개수을 각각 담을 수 있도록 vector tree로 지정했다. 그러고 난 후 짝수의 개수 누적 합과 홀수의 개수 누적 합을 트리에 저장시켜주면 된다 #include #define l long long #define I..
5676번 음주 코딩 https://www.acmicpc.net/problem/5676 5676번: 음주 코딩 각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다. www.acmicpc.net 세그먼트 트리를 이용해 곱을 구하는 문제이다. 하지만 모듈러 연산이 적용 안 되기 때문에 곱을 구하면 오버플로가 난다. 따라서 문제의 답을 잘 보면 양수 일 땐 +, 음수 일 땐 -, 0일 땐 0을 출력하는 것이므로 연산을 다 하지 않고 값이 들어왔을 때 음수인지 양수인지 0인지만 판단 해주면 된다. #include #define l long long #define INF 2e9 #define..
2268번 수들의 합 7 https://www.acmicpc.net/problem/2268 2268번: 수들의 합 7 첫째 줄에는 N(1 ≤ N ≤ 1,000,000), M(1 ≤ M ≤ 1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다. 첫 번째 숫자는 어느 함수를 사용했는 www.acmicpc.net 기본적인 세그먼트 트리 합 구하는 문제이다. 주의해야 할 점은 i > j일때 [j,i]의 합을 구해야 한다. #include #define l long long #define INF 2e9 #define p pair #define vc vector using namespace std; l Sum(int st,int en,int node,int L,int R,v..
12837번 가계부 (Hard) https://www.acmicpc.net/problem/12837 12837번: 가계부 (Hard) 살아있는 화석이라고 불리는 월곡이는 돈에 찌들려 살아가고 있다. 그에게 있어 수입과 지출을 관리하는 것은 굉장히 중요한 문제이다. 스마트폰에 가계부 어플리케이션을 설치해서 사용하려 www.acmicpc.net [p,q]구간의 합을 구하면 된다. 주의해야 할 점은 값을 `바꾼다`는 개념이 아니라 `추가`한다는 개념이기 때문에 Update를 할 때 조심해줘야 한다. #include #define l long long #define INF 2e9 #define p pair #define vc vector using namespace std; l Sum(int st,int en,int node,int L,int..
14438번 수열과 쿼리 17 https://www.acmicpc.net/problem/14438 14438번: 수열과 쿼리 17 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을 www.acmicpc.net 세그먼트 트리를 이용해 [i,j]구간의 최솟값을 찾으면 된다. #include #define l long long #define INF 2e9 #define p pair #define vc vector using namespace std; l init(int st,int en,int node,vc &v,vc &tree..
1275번 커피숍2 https://www.acmicpc.net/problem/1275 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net 세그먼트 트리를 이용해 [x,y]구간까지의 합을 구하면 된다. 주의해야 할 점은 if(x > y) true 일때 [y,x]구간을 구해야한다. #include #define l long long #define INF 2e9 #define p pair #define vc vector using namespace std; l init(int st,int en,int nod..
2357번 최솟값과 최댓값 https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 10868문제와 똑같다. 최솟값 저장 트리 하나, 최댓값 저장 트리 하나를 만들어서 구하면 된다. #include #define l long long #define INF 2e9 #define p pair #define vc vector using namespace std; vc MaxTree(100000*4),MinTree(100000*4),v; int Ma..
10868번 최솟값 https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 기본적인 세그먼트 트리 문제이다. [a,b]구간중에 제일 최솟값을 트리에 넣으면 된다. #include #define l long long #define INF 2e9 #define p pair #define vc vector using namespace std; int init(int st,int en,int node,vc &v,vc &tree){ if(st ..
11505번 구간 곱 구하기 https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 세그먼트 트리의 가장 기본적인 문제이다. 다만 주의해야 할 점은 숫자가 너무 커져 오버플로우 날 수 있으므로 mod를 잘 적용해야 한다. #include #define l long long #define INF 2e9 #define p pair #define vc vector using namespace std; const int mo..
2042번 구간 합 구하기 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 세그먼트 트리를 이용한 가장 기본적인 문제이다. 다만 주의해야 할 점은 long long을 써야한다. #include #define l long long #define INF 2e9 #define p pair #define vc vector using namespace std; l init(int st,int en,int node,vc &..
1655번 가운데를 말해요 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 백준 2696번과 같은 문제이다. 다만 짝수일때 중앙값은 두개의 값중 작은것으로 출력해야한다. ex) 1 2 3 4일때 2 3중 작은게 중앙값 #include #define l long long #define INF 2e9 #define p pair using namespace std; priority_queue MinQ; priority_queue MaxQ; int main() ..
2696번 중앙값 구하기 https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 중앙값 : 정렬된 숫자중에 중앙에 있는 숫자. 해결법 : 우선순위 큐 2개를 이용해 풀기 1 2 3 일때 2가 중앙값, 1 2 3 4 5 일때 3이 중앙값, 1 2 3 4 5 6 7 일때 4가 중앙값 따라서 내림차순 큐와 오름차순 큐를 이용 해 중앙값 찾기. 1. max큐는 내림차순이며 top값이 항상 중앙값이 된다. 2. min큐는 오름차순이며 max큐의 top값보다..

티스토리툴바