전체 글
-
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로 거쳐가는 노드들은 모두 루트로부터 연결이 가능한 노드들이다. 난 좀 무식하게 해서 모든 점을 루트로 잡아서 연결을 했다. 그러면 이건 나중에..
-
1199알고리즘/acmicpc 2015. 3. 1. 17:50
문제가 좀 불친절 한 것 같다. 여기서 입력이 핵심인데 두 정점 사이에 간선이 여러개 있을 수 있다고 한다. 그런데 간선이 여러개 있는 것을 어떻게 표현할 것인가에 대한 설명은 없다. 그래서 나는 주어진 간선 이차원 배열에서 입력받는 정수가 두 정점 사이의 간선의 개수라 생각하고 문제를 풀었다. 나머지는 오일러 회로 문제라 생각하면 된다. 오일러 회로의 성립 요건은 모든 정점의 인접한 간선의 수가 짝수여야 한다는것 이걸로 오일러 회로가 성립 하지 않는 경우에 대해서 -1을 출력했고 성립하는 경우 정점 출력 순서는 주위의 간선이 존재하지 않는 것으로 stack을 이용했다. 여기서 속도 문제가 있었는데 그거는 각 노드마다 자신과 인접한 노드를 queue로 저장해서 관리하는 방법으로 해결했다. 그러면 매번 각..