전체 글
-
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로 저장해서 관리하는 방법으로 해결했다. 그러면 매번 각..
-
4256알고리즘/acmicpc 2015. 2. 28. 19:40
전위탐색에서의 값을 중위탐색에서 찾으면 그것의 왼쪽에 있는 것들은 left child, 오른쪽에 있는 것들은 right child이다. 이 성질을 이용해서 풀면 쉽게 풀수있다. 재귀함수를 이용해 좀 더 깔끔히 푸는 방식이 있으나 나는 규칙성과 stack을 같이 응용해 풀었다. #include #include #include using namespace std; int d[1005]; int pre[1005]; int ior[1005]; int main() { int tc, size; stack s; scanf("%d", &tc); d[0]=1; while(tc--) { scanf("%d", &size); d[size+1]=1; for(int i=1; i
-
2156알고리즘/acmicpc 2015. 2. 28. 18:23
바로 전 문제 dp를 쉽게 풀어서 이 문제 만만히 봤는데 4번맞에 맞았다;; 너무 내가 성급히 접근한것 같다. 경우의 수를 좀 철저히 따져봐야 했는데. 문제의 핵심은 연속 3잔은 마실 수 없다는 것이다. 그러면 경우의 수로 나눌 수 있는데 1 2 3 4 5 6 이렇게 포도주가 있으면 12 3 45 6 하나를 공백으로 두고 마시는 경우와 12 3 4 56 두개를 공백으로 두는 경우 그리고 1 2 3 4 5 6 하나씩 공백으로 두는 경우로 나눌 수 있다. 이 문제를 풀기위한 자료구조로 이차원 배열을 생각해냈다 d[][2] -> d[][0]는 현 위치에서 연속이 끝나는, d[][1]는 현 위치에서 연속이 시작하는 위의 모든 경우와 자료구조를 정의했으니 다음과 같은 점화식을 낼 수 있다. d[here][0] -..
-
10159알고리즘/acmicpc 2015. 2. 28. 13:54
처음에 이 문제를 읽을때 위상정렬을 써야하나 깊이 고민했는데 올림피아드 문제에서 대학생들이 공부하는 위상정렬을 여기서 쓰겟나 싶어서 간단히 접근한결과 무식하게 풀기를 생각해냈다. 이차원 배열을 선언하고 다음과 같이 정의한다. judge[from][to] from과 to의 값을 비교 결과를 저장하는 배열이다. from to 이면 1, 알수 없으면 0으로 저장한다. 여기서 너무도 당연한 사실을 생각 할 수 있는데 from < to 이면 from과 from보다 작은 값들과, to와 to보다 높은 값들과 비교를 할 수 있다는 사실 그래서 난 from과 from보다 작은 값들을 loser라는 벡터에 두고 to와 to보다 높은 것들을 winner라는 벡터에 두어서 (judge[][]함..
-
오일러회로알고리즘/자료구조 2015. 2. 27. 15:21
오일러 회로는 그래프의 모든 간선을 방문하고 시작점과 끝점이 같은 회로를 말한다. 우리에게는 연필로 모든 간선을 칠하고 다시 돌아오는 것으로 친숙하다. 별표그릴때를 생각해보면. 이 회로를 만들기 위한 조건은 각 정점들마다 나가고 들어오는 간선의 수가 같아야 한다(무방향의 그래프는 정점과 연결된 간선의 수가 짝수개여야 한다) 정말 간단히 생각하면 된다. 어떤 정점의 나가는 간선의 수가 들어오는 간선의 수보다 적다면 그 정점으로 들어오는 간선들은 아직 방문하지 못한채 그 정점에서 나가지 못하게 된다. 위의 그림에서 정점은 2개의 나가는 간선과 3개의 들어오는 간선이 있다. 검은색 간선은 이미 방문 한 것이고 파란색 간선은 아직 방문하지 않는 것이다. 현재 위치는 정점 3인데 여기서 더이상 어느 곳으로 나갈 ..