알고리즘 썸네일형 리스트형 BOJ 백준 16234 인구이동<BFS> https://www.acmicpc.net/problem/16234 이 문제는 상하좌우로 인접한 국가끼리의 인구 차이가 문제에서 입력되는 L 이상, R 이하인 경우 국경이 개방되고 국경이 개방된 국가끼리 인구수를 모두 더한 후 국가 수로 나누어 평균을 내 연합된 국가에 할당해주는 문제이다. 1. bfs를 통해 연합 가능한 국가들을 찾아가면서 방문 여부를 표시해주고, 총 인구수와 총 국가 수를 갱신해나간다. 2. for문을 통해 N x N 만큼 돌면서 연합국가들의 인구수들을 갱신해 주었다면, 방문 여부를 모두 지워준다. 3. 다시 N x N 만큼 돌면서 bfs를 돌려주는데, 만약 연합 가능한 국가가 한 개도 없다면, 즉 인구 이동이 불가능하다면 반복문을 끝낸다. 다른 맞은 사람들의 효율정.. BOJ 백준 1652 누울 자리를 찾아라 <수학> https://www.acmicpc.net/problem/1652 이 문제는 N x N 의 배열에서 가로, 세로로 2칸 이상 연속으로 '.'으로 이루어진 곳을 카운팅해주면 되는 간단한 문제이다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include #define SIZE 101 using namespace std; char room[SIZE][SIZE]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=0; i> room[i]; } int countH = 0.. BOJ 백준 1037 약수 <수학> https://www.acmicpc.net/problem/1037 특정 수 A의 1이 아닌 약수들을 진짜 약수라고 하고, 이 약수의 총 개수와 각 약수들이 주어질 때 A가 어떤 수인지 출력해주는 문제이다. 진짜 약수들 중에서 가장 작은 약수와 가장 큰 약수의 곱은 이러한 약수들을 가지고 있는 정수가 나오게 된다. 따라서 주어지는 진짜 약수들 중에서 가장 작은 약수와 큰 약수를 구해주어 곱을 출력해주면 되는 간단한 문제이다. 123456789101112131415161718192021222324252627#include #include using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n; int iMa.. BOJ 백준 2869 달팽이는 올라가고 싶다 <수학> https://www.acmicpc.net/problem/2869 이 문제는 달팽이가 하루 A만큼 올라간 뒤에 B만큼 미끄러질 때, 총 V 만큼 가려면 며칠이 걸리는 지 계산하면 되는 문제이다. 즉 하루에 ( A - B ) 만큼 올라갈 수 있는 것이고 도달하는 날에는 미끄러지는 것을 계산할 필요가 없으므로, A 만큼 올라간 것으로 보면 된다. V - A 만큼만 가면 다음 날은 도착이므로, V - A 까지만 ( A - B ) 만큼 가는 것으로 계산해주면 된다. 123456789101112131415161718192021#include using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int a.. BOJ 백준 3053 택시 기하학 < 기하 알고리즘 > https://www.acmicpc.net/problem/3053 이 문제는 택시 기하학에서의 원이 무엇인지를 알아야 풀 수 있는 문제이다. 원의 정의는 유클리드 기하학, 택시 기하학에서 같다고 되어 있다. " 평면 상의 어떤 점에서 거리가 일정한 점들의 집합 " 유클리드 기하학에서는 두 점의 거리를 (x1 - x2)^2 + (y1 - y2)^2 의 값에 루트를 씌우는 형태라면, 택시 기하학에서는 두 점의 거리를 ㅣx1 - x2ㅣ + ㅣy1 -y2ㅣ로 한다고 되어있다. 즉, 택시 기하학에서의 원은 마름모꼴로 나타나게 된다. 택시 기하학에서 왜 원이 마름모꼴인지 이해가 가지 않는다면 https://m.blog.naver.com/alwaysneoi/100172516753 블로그를 참고해보.. BOJ 백준 9251 LCS <dp, LCS> https://www.acmicpc.net/problem/9251 이 문제는 두 문자열을 받아와서 공통돤 최장 수열을 찾아 그것이 몇 개의 알파벳으로 이루어져 있는 지 출력해주는 문제이다. 예제 입력 1 복사ACAYKP CAPCAK 예제 출력 1 복사4 예제 입력을 보면 ACAYKP 와 CAPCAK를 비교하는데 이 입력의 답은 ACAYKP / CAPCAK으로 ACAK, 4를 출력해주면 된다. 하나의 수열을 두고 LCS를 구하는 문제는 풀어보았지만, 두 문자열을 가지고 공통된 최장 문자열을 찾는 것은 풀기 힘들었다. https://www.youtube.com/watch?v=P-mMvhfJhu8&t=335s 위 링크의 유투브 영상을 참고했는데 정말 쉽게 잘 설명해주어서 보자마자 문제를 풀 수 .. BOJ 백준 2162 선분 그룹 <선분 교차> https://www.acmicpc.net/problem/2162 이 문제는 최대 3000개의 선분을 입력 받고 그 선분들이 한 점이라도 공통된 점이 있다면 한 그룹으로 엮는다. 그룹의 수와 가장 많은 선분을 가진 그룹의 선분의 개수를 출력해주면 된다. 처음에는 선분의 식을 구해서 다른 선분의 양 끝점을 대입했을 때 -와 +가 나오는 경우에 교차하는 형태로 접근하려 했으나 모든 경우의 수를 고려하지 못할 뿐더러 코드가 매우 복잡했다. 결국 선분 교차 알고리즘을 검색하였고, 그 결과 CCW라는 새로운 알고리즘을 알게되었다. CCW는 세 점이 시계 방향인지, 반 시계 방향인지, 평행한 지 알려주는 알고리즘이다. CCW를 이용하여 선분 교차 여부를 판별하는 알고리즘을 짤 수 있었다. 1. 선.. 선분 교차 알고리즘 <CCW 이용> http://jason9319.tistory.com/358 위의 블로그에서 보고 배웠습니다. CCW : CounterClockWise의 약자로 뜻은 '시계 반대 방향'을 의미한다. 세 가지 점 (a, b, c)가 주어졌을 때, a->b->c 가 1. 시계방향2. 반시계방향3. 평행 중 어떤 경우인지를 분별해주는 알고리즘이다. (x2 - x1)(y3 - y1) - (y2 - y1)(x3 - x1)의 값이 0보다 큰 경우 : 반 시계 방향 0인 경우 : 평행 0보다 작은 경우 : 시계 방향 * 위의 굵은 색 식의 값을 2로 나누면 삼각형의 넓이가 나온다고 한다. 굵은 색의 식을 나열하면 x1y2 + x2y3 + x3y1 - x1y3 - x2y1 - x3y2 가 된다. 이 식을 코드로 나타내면 아래 op와 관.. 이전 1 2 3 4 5 6 다음