답은 알고리즘 뿐이야!

1. 신청하게된 계기 살짝 공부하다가 현타가 온 시기여서 적당히 프로젝트만 하고 있었는데, 졸업반 친구가 이런 특강도 있다고 가서 들어보는게 어떻겠냐고 권해줘서 존재를 알게 되었다. 기초 자료구조나 알고리즘은 탄탄하다고 생각하고 있었기 때문에 중~고급 알고리즘으로 지식의 폭을 확장 시킬 수 있는 좋은 기회라고 생각하여 고민도 하지 않고 바로 신청하였다. 2. 입과테스트 나는 이미 SW 역량테스트 A+형을 보유중이였기 때문에 입과테스트는 따로 치루지 않았고, 바로 신청한 차수에 입과하게 되었다. 3. 배우는 내용 원래 저번 특강까지는 기하도 있고 자구나 알고리즘 기초 같은건 대충 하고 넘어갔다던데 이번 특강에서는 그부분을 좀더 잘? 가르쳐 주기 위해 기하를 빼고 이 시간을 늘렸다고 한다. ( 기하 못배우는..

문제 출처 : 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/3176 풀이 : LCA 문제입니다. LCA를 구하는 과정에 Max값과 Min값을 구하는 과정을 포함시켜 두 도시 사이의 경로 중 최소 최대값을 찾으시면 됩니다. 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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #include #include #include using namespace std; typedef pair pi; int n, k, a, b, c; ..

문제 출처 : 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 ..