분류 전체보기
-
백준(BOJ) 14889번 스타트와 링크알고리즘 풀이/백준(Boj) 2019. 8. 29. 16:58
문제 : https://www.acmicpc.net/problem/14889 문제오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 S..
-
오일러 서킷을 찾아내는 알고리즘알고리즘 이론/알고리즘 구현 2019. 8. 28. 02:47
오일러 서킷이란? 깊이 우선 탐색을 이용해 풀 수 있는 유명한 문제로, 그래프의 모든 간성르 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 찾는 문제이다. 모든 정점이 짝수점이면서, 간선들이 하나의 컴포넌트에 포함된 그래프가 주어진다면 항상 오일러 서킷을 찾아내는 알고리즘을 만들 수 있다. findRandomCircuit(u)는 u와 인접한 간선들을 하나하나 검사하면서, 아직 방문하지 않은 간선 (u,v)가 있다면 또다시 findRandomCircuit(v)를 호출. 더이상 따라갈 간선이 없다면 재귀 호출 종료후 반환한다. 재귀 호출이 끝나고 반환할 때 경로에 추가해줌 으로서 경로의 끝점부터 역순으로 간선들이 추가된다. 코드 ( C+ + ) #include #include using namespace..
-
백준(BOJ) 17144번 미세먼지 안녕!알고리즘 풀이/백준(Boj) 2019. 8. 26. 18:19
문제 : https://www.acmicpc.net/problem/17144 문제미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.1초 동안 아래 적힌 일이 순서대로 일어난다.미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난..
-
그래프의 깊이 우선 탐색알고리즘 이론/알고리즘 구현 2019. 8. 25. 02:45
깊이 우선 탐색(DFS)은 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법이다. 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라가는 것. 이 과정에서 더이상 갈 곳이 없는 막힌 정점에 도달하면 포기하고, 마지막에 따라왔던 간선을 따라 뒤로 돌아간다. 그래프에서는 모든 정점들이 간선을 통해 연결되어 있다는 보장이 없기 때문에, dfs() 만으로는 모든 정점을 순서대로 발견한다는 목적에 부핮하지 않는다. 따라서 dfsAll()을 통해 모든 정점을 방문해야 한다. 코드 ( C++ ) #include #include #include using namespace std; //그래프의 인접 리스트 표현vector adj;// 각 정..
-
백준(BOJ) 15685번 드래곤 커브알고리즘 풀이/백준(Boj) 2019. 8. 24. 19:44
문제 : https://www.acmicpc.net/problem/15685 문제드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.시작 점시작 방향세대0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 ..
-
백준(BOJ) 17136번 색종이 붙이기알고리즘 풀이/백준(Boj) 2019. 8. 23. 20:08
문제: https://www.acmicpc.net/problem/17136 문제과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자. 나의 풀이:..
-
크루스칼의 최소 스패닝 트리 알고리즘알고리즘 이론/알고리즘 구현 2019. 8. 23. 02:25
크루스칼 알고리즘은 그래프의 모든 간선을 가중치의 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가해 간다. 가중치가 작다고 해서 무조건 간선을 트리에 더하는 것은 아니다. 결과적으로 사이클이 생기는 간선은 고려에서 제외해야 한다. 간선을 트리에 추가했을 때 이미 추가한 간선들과 합쳐 사이클을 이루는지 여부를 판단하는 부분이 크루스칼 알고리즘의 핵심이다. 이는 상호 배타적 집합 자료 구조를 통해 구현한다. 코드 ( C ++ ) #include #include #include using namespace std; // DisjointSet은 상호 배타적 집합 구현struct DisjointSet {vector parent, rank;DisjointSet(int n) : parent(n), rank(n) ..
-
음주 운전 단속알고리즘 풀이/알고리즘 해결전략 연습 2019. 8. 22. 23:40
문제 : https://algospot.com/judge/problem/read/DRUNKEN 코드 ( C ++ ) 종만북 참조 #include #include #include using namespace std; int V, adj[500][500], E;// 각 정점에서 음주 운전 단속을 할 때 걸리는 시간int delay[500];int W[500][500];const int INF = 987654321;// 입력을 받을 때 1부터 시작하는 정점 번호를 0부터 시작하도록 변경했다고 가정한다void solve() {// 모든 정점들을 예상 시간 별로 정렬한다vector order;for (int i = 0; i < V; ++i)order.push_back(make_pair(delay[i], i));s..