답은 알고리즘 뿐이야!

문제 출처 : https://www.acmicpc.net/problem/14725 풀이 : 문자열로 트리를 구성하는 문제입니다. 문제에서 주어지는 인풋 대로 트리를 채워나가시되 이진 트리가 아닌 N진 트리로 구성하시면 됩니다. 저는 정렬을 하기 위해 처음부터 사전순으로 비교하여 현재 인덱스의 스트링이 사전순으로 뒤에있으면 그 자리에 삽입하고 나머지를 뒤로 푸쉬해주는 방식으로 하였습니다.

문제 출처 : https://www.acmicpc.net/problem/14247 풀이 : 그리디(탐욕법) 문제입니다. 나무를 최대로 잘라가는 문제입니다. 따라서 나무가 자라는 길이가 최소인 애들이 제일 밸류가 떨어지므로 길이가 최소인 애들부터 잘라서 들고가면 됩니다. 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 #include #include #include using namespace std; typedef long long ll; typedef pair p; int n; p arr[100000]; priority_queue q; ll ret; int main() { ios::sync_with_stdio(fals..

문제 출처 : https://www.acmicpc.net/problem/15671 풀이 : 문제 조건이 시키는대로 짜면 되는 문제입니다. (시뮬레이션...? 구현...?) 문제에 주어진 인풋대로 하면 무조건 정상적인 게임으로 성립이 됩니다. 조건 1. 처음 상태는 {{W,B},{B,W}}이다. 2. 돌은 반드시 포위하여 뒤집을 수 있는 곳에 놓아야 한다. 3. 돌을 뒤집을 수 없으면 상대 차례로 넘어간다. 2번 조건이 제일 중요한 조건으로 돌을 놓은 곳부터 2번조건을 성립시킬 수 있는 돌이 있는 곳까지 다 뒤집어 주되, 그 사이에 빈칸이 있으면 안됨을 고려해서 짜면 됩니다. 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 2..

문제 출처 : https://www.acmicpc.net/problem/3006 풀이 : 세그먼트 트리 문제입니다. 각 숫자가 자신의 자리를 찾아가는데 항상 작은 숫자는 왼쪽 큰 숫자는 오른쪽으로 가기 때문에 홀수번째 일때는 왼쪽숫자의 갯수, 짝수번째는 오른쪽 숫자의 갯수로 옮기는 횟수를 쉽게 구할 수 있습니다. 각 숫자의 위치를 따로 저장해주고 세그먼트 트리에 각 숫자의 위치의 값을 1로 채웁니다. 그다음 세그먼트 트리를 활용하여 1. 홀수번째 : 찾으려는 값의 왼쪽 범위의 구간합 2. 짝수번째 : 찾으려는 값의 오른쪽 범위의 구간합 을 구하시면 됩니다. 구하신 후에는 찾으려는 값의 세그먼트 트리에 저장된 정보를 0으로 바꾸고 업데이트 시키시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 ..

문제 출처 : https://www.acmicpc.net/problem/18111 풀이 : 완전 탐색 문제입니다. 각 높이별로 블록이 몇 개 있는지 저장한 후 각 높이를 탐색하여 조건에 맞게 계산한 후 최댓값을 뽑아내면 됩니다. 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 #include using namespace std; int n, m, b, a[257], result = 1e9, hei, i, j, ret, bb; int main() { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); for (cin >> n >> m >> b; i > ..

문제 출처 : https://www.acmicpc.net/problem/6549 풀이 : 스택 or 분할정복 + 세그먼트 트리 로 풀 수 있는 문제입니다. 저는 분할정복 + 세그먼트 트리로 풀었고 세그먼트 트리로 구간의 최솟값의 인덱스를 저장하여 최솟값 왼쪽 구간과 최솟값 오른쪽 구간으로 나누어서 분할 정복을 시행하였습니다. 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include #include #include using namespace std; typedef long long ll; int n, base, hei..

출처 : https://www.acmicpc.net/problem/2094 풀이 : y, x가 주어졌을때 y~x 사이의 범위에서 최댓값이 x이고 두번째로 큰 값이 y인지 묻는 문제입니다. y~x 사이의 범위의 최댓값은 세그먼트 트리로 구하면 되고 그거완 별개로 모든 연도의 강수량 정보가 주어지는 것은 아니기 때문에 y와 x의 강수량이 주어졌는지 확인해주셔야합니다. 따라서 3가지의 케이스를 검사해야합니다. case 1: x년도의 강수량이 있을때 y+1 ~ x-1 사이의 최댓값이 x년도의 강수량보다 작은가 case 2: y년도의 강수량이 있을때 y+1 ~ x-1 사이의 최댓값이 y년도의 강수량보다 작은가 case 3: x년도의 강수량이 있고, y년도의 강수량이 있을때 y ~ x 사이의 모든값이 주어져있는가 ..

문제 출처 : https://www.acmicpc.net/problem/3830 풀이 : disjoint-set (Union-Find) 문제입니다. find를 할때마다 속도를 개선시켜주기 위해 부모를 루트로 지정해주고 무거운 정도를 루트 부터 1촌 부모까지의 차이로 저장해주고, Union 연산을 할때 점화식을 세울때 주의해서 세워주시면 됩니다. 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include typedef long long ll; int n, m, a, b, c, parent[100001],cnt; ll..

문제 출처 : https://www.acmicpc.net/problem/3860 풀이 : 벨만-포드 문제입니다. 1. 입구는 ( 0 ,0 ) 출구는 ( W - 1, H - 1 ) 고정. 2. 묘비가 있는 칸은 이동 불가능 3. 귀신 구멍은 텔레포트 (시간도 이동) 4. 묘지를 벗어날 수 없음 5. 출구에 도착하면 바로 탈출 (출구에서 다른 칸으로 이동하지 않음) 6. 제로 사이클은 신경쓰지 않는다. 위 여섯가지 조건으로 엣지를 구성하여 벡터에 채운다음 총 V * E 번 계산하면서 음의 사이클, 탈출 가능성을 판단 하시면 됩니다. 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 32 33 34 35 36 ..

문제 출처 : https://www.acmicpc.net/problem/11003 풀이 : 슬라이딩 윈도우로 푸는 문제이고 덱으로 풀었습니다. 값을 받아서 덱의 맨 뒤에서 자신보다 큰 수를 다 팝한후 푸쉬합니다. 그 이유는 현재 윈도우에서 현재값보다 큰 수들은 최솟값 후보가 될 수 없기 때문입니다. 최솟값을 출력할 때에는 현재 덱의 맨 앞의 값이 윈도우에 포함되는지 여부를 파악한 후 포함되지 않으면 최솟값이 아니니 팝하고 포함되면 출력합니다. 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 #include #include #include using namespace std; struct num { int v, s; num(int v, ..