뒤늦은 공부 정리

알고리즘 분류 : 수학, 브루트포스 알고리즘, 조합론, 백트래킹 전형적인 백트래킹문제이다. 모든 경우의 수에 대해서 탐색하되 조건이 맞을 경우에만 출력하면 된다. 입력으로 주어진 알파벳들을 오름차순으로 정렬하고 맨 앞부터 하나씩 골라서 길이가 l인 암호가 만들어졌을 때, 모음이 한 개 이상이고, 자음이 2개 이상이라면 출력한다. 재귀식으로 탐색하는 법이 코드짜기가 편하다. #include #include #include #include using namespace std; int l, c; char a; vector v, st; set vw = { 'a', 'e', 'i', 'o', 'u' }; void dfs(int x, int vowel) { if (st.size() == l) { if (vowel ..

알고리즘 분류 : 기하학, 볼록 껍질 이전에 풀었던 22819, 3970과 거의 흡사한 문제이다. 차이점은 수의 범위와 N의 크기 정도이다. 완벽하게 동일한 크레이터가 나오는 경우에 대한 예외처리만 해주었다. 구조체 vector에 대한 unique 함수 사용법을 몰라 x, y, r 순으로 정렬한 후 완벽하게 같은 경우에 체크해주고 다른 경우에 대조군을 변경해주는 방식으로 해결했다. circle c = v[0]; for (int i = 1; i < n; i++) { if (c.x == v[i].x && c.y == v[i].y && c.r == v[i].r) { notsurrounded[i] = 1; } else c = v[i]; } 나머지 풀이방식은 22819에 더 자세히 설명되어있다. BOJ 22819..

알고리즘 분류 : 기하학, 볼록 껍질 이전에 풀었던 Enclosing Circles와 거의 유사한 문제이다. 겹치거나 접하는 원이 없기때문에 더 쉽다. 하지만 소숫점 오차 때문에 외접선이 수직으로 그어지는 경우에 대해서 다음과 같이 예외처리를 반드시 해줘야 한다. if(abs(a-b) < 0.00000000000001) return 0; 이하 모든 방법론은 밑에 문제와 동일하다. BOJ 22819 Enclosing Circles 알고리즘 분류 : 수학, 기하학, 볼록 껍질, 분할 정복 입력으로 원들의 중심좌표와 반지름이 주어질 때 모든 원들을 감싸는 끈의 최소 길이를 구해야 한다. (원과 원 사이는 직선으로 감싸야 한다 offlinequery.tistory.com