알고리즘
-
1197알고리즘/acmicpc 2015. 6. 27. 10:53
반성해야하는 문제다 너무 문제에 성급하게 접근했다. 최소스패닝트리는 kruskal이든 prim이든 둘 중 하나를 이용해서 풀면된다. 나는 kruskal을 사용했는데 여기서 각각의 클라우드를 병합하는 과정에서 실수가 있었다. 이것은 union find라는 자료구조를 이용해서 해결해야하는데 나는 두 노드중 발견된 것들을 제외한 것만 본다고 했으니 당연히 틀릴 수밖에 없다. (아마 이 글을 읽는 사람은 뭔말인지 모를 것이다 나만 이해할 수 있는 문장..) 프림알고리즘을 사용했으면 틀리지 않았을 것 같다... #include #include #include using namespace std; int height[100001]; int par[100001]; struct Node{ int con_a, con_b..
-
2268알고리즘/acmicpc 2015. 6. 26. 11:54
집가기 전에 하나 풀고 가겠다고 성급하게 덤볐다가 쓸데없이 두 번 틀린 문제다. 펜윅트리를 다시 정의해서 풀면 된다. update를 이전 값에서 차이값을 갱신해주면 된다. #include #define MaxVal 1049577 int tree[MaxVal]; int data[MaxVal]; int read(int idx) { int sum = 0; while(idx > 0){ sum += tree[idx]; idx -= (idx & -idx); } return sum; } void update(int idx, int val) { while(idx
-
2357알고리즘/acmicpc 2015. 6. 25. 16:10
각 구간별로 최소값과 최대값을 구하는 문제 가장 쉽게 생각하면 매번 구간이 주어질 때마다 최대값과 최소값을 구하는 방법이 있겠으나 그렇게 쉽게 문제를 냈을 리가 없다. 방법은 Min Max Tree를 만드는 것이다 옛날 자료구조 시간에 Tree의 존재를 배우기는 했으나 직접 구현하지는 않아봐서 이번에 구현하는데 시간이 좀 걸렸고,,, 구간 부분을 지정해주는 것도 꽤 힘들었다. (이거 진짜 귀찮은 작업이다...) 하지만 한번에 맞춰서 기분이 좋다 나의 미천한 코딩실력도 조금씩 상승하는 것 같은 느낌이다. #include #include #include #include #include using namespace std; int minTree[20][100000]; int maxTree[20][100000]..
-
1138알고리즘/acmicpc 2015. 6. 25. 14:03
이 문제는 줄을 모두 비운 다음 입력에 따라서 하나씩 채워가면 된다. 예제로 나온 것을 보자 2 1 1 0 -1을 비어있는 것으로 보고 줄을 만들어보면 -1, -1, -1, -1 먼저 1의 크기를 가진 참가자는 자신의 앞에 두명이 있어야 한다. 그런데 다음으로 검사할 참가자들은 모두 1보다 키가 클 것이므로 앞에 두명을 비운 다음에 자신의 위치를 잡아 줄 수 있다. -1, -1, 1, -1 다음 2의 크기를 가진 참가자는 자신 앞에 한명이 있어야 한다. 앞의 경우와 마찬가지로 다음으로 검사할 참가자들은 모두 2보다 키가 크기 때문에 3이 올지 4가 올지 생각하지 않고 그냥 앞에 한 칸을 비우면 된다 -1, 2, 1, -1 핵심은 키의 순서대로 적용하고 있다는 것이고 그 숫자만큼 빈칸을 만들어 두면 된다는..
-
4158알고리즘/acmicpc 2015. 6. 18. 16:41
속도를 어떻게 높일 것인가에 대한 문제인데 문제에서 힌트로 주어지는 CD 넘버가 오름차순을 띤다고 했다. 가장 일반적으로 생각할 수 있는 방법은 트리 구조임을 이용해 O(nlogn)시간 내에 푸는 방법이 있을 수 있지만 상근이와 선영이의 CD로 주어지는 넘버 모두 오름차순을 띈다는 점을 이용해 O(N)시간에 해결 할 수 있다. #include #include using namespace std; int a[1000000], b[1000000]; int main() { int piv_a, piv_b; int size_a, size_b; int cnt; while(true){ scanf("%d %d", &size_a, &size_b); if(size_a == 0 && size_b == 0) break; cn..
-
4883알고리즘/acmicpc 2015. 6. 18. 16:10
삼각그래프 알고리즘 문제를 풀 때 가장 기본적인 태도는 1. 먼저 문제를 잘 읽는다 2. 문제를 의심한다 여기선 문제를 잘 읽기는 했는데 문제를 의심하는 단계가 부족했다. 입력으로 비용의 제곱은 1000000보다 작다고 했는데 그렇다면 비용은 음수가 들어올 수도 있다는 이야기... 하지만 나는 그걸 몰랐고 쓸데 없이 틀렸다. 그런데 이런건 좀 친절히 설명해줘야 하는거 아닌가 ㅡㅡ #include #include using namespace std; int main() { int cost[3], clk=0; long long cur[3], bef[3]; int n; while(true){ scanf("%d", &n); if(n==0) break; for(int i = 0; i < n; i++){ for(i..
-
1890알고리즘/acmicpc 2015. 6. 18. 11:21
도착 할 경로가 몇개나 있는지 묻는 문제이다. 도착 할 좌표의 경로를 찾는데 집중 하기 보다는 각 좌표까지 이동 할 수 있는 경우의 수들을 모두 계산 한 후 마지막에 도착 지점의 경우의 수를 구해주면 풀기 쉽다. #include #include #include using namespace std; int main() { int n; int map[100][100]; unsigned long long d[100][100]; ifstream ifp("input.txt"); scanf("%d", &n); for(int i = 0; i >map[i][j]; d[i][j] = 0; } d[0..
-
1976알고리즘/acmicpc 2015. 3. 29. 16:16
딱 보면 알고리즘에 배운 Floyd Warshall로 해결 할 수 있을 것 같지만 Floyd Warshall 알고리즘은 나중에 한 값이 이전에 한 값에 영향을 줄 수 있는 문제점이 있다. 즉 나중에 연결 한 선이 이전에 연결한 선까지 변경 할 수 있다는 말이다(말이 좀 어렵다. 그림으로 표현하면 쉬울것 같은데 그림 그리자니 그건 귀찮고) 그래서 내가 10달전에 제출해보았던 코드들은 대부분 Floyd 알고리즘을 썼더니 모두 틀렸다. 새롭게 생각해낸 방법은 다익스트라 알고리즘을 이용한 방식이다. 한 점을 루트 로 잡고 그 점으로 부터 bfs 탐색을 한다 여기서 bfs로 거쳐가는 노드들은 모두 루트로부터 연결이 가능한 노드들이다. 난 좀 무식하게 해서 모든 점을 루트로 잡아서 연결을 했다. 그러면 이건 나중에..