백준 1358번 문제 바로가기 최근 한달간 알고리즘 문제풀이가 뜸했는데, 다시 마음을 다잡고 차근차근 풀어보려 한다. 1358번은 비교적 간단한 기하학 문제였는데, y축이나 x축 둘 중 하나를 기준잡고 부등식을 풀어서 판별하는 방식이 가장 효과적이다. 이 문제의 경우 y축을 기준으로 잡는 편이 수학적으로 간결하고 조건 분기가 간단해져 코드가 짧아지는데, 나의 경우 그냥 x축을 기준으로 풀어내긴 했다. 원의 방정식을 활용해서 x에 따른 y의 범위를 부등식으로 풀어내는 것이 핵심! 사실 식만 세우면 따로 더 고민할 필요가 없는 쉬운 문제였다. ...
백준 1069번 문제 바로가기 문제에 대한 첫 인상 이 문제는 처음 접했을 땐, 이게 골드 문제?! 싶었지만, 문제를 찬찬히 살펴보니 생각보다 고려할게 많았다. 처음엔 “택시 거리"처럼 축을 따라서만 이동할 수 있는줄 알았지만, 그런 제약을 없었다는 것! 따라서 이동할 수 있는 경우의 수는 총 4가지가 있다. 대각선을 따라서 그냥 걸어오는 경우 대각선을 따라 직전까지 뛰고 나머지를 걸어오는 경우 대각선을 따라 한번 저 뛰고 차이만큼 걸어서 돌아오는 경우 점프만 이용해서 돌아돌아 오는 경우 (활 꼴 그리는 느낌으로) 이 경우 3번의 점프 횟수 만큼 점프해야 한다. 위의 4가지 경우에 맞게 구현해주고 min값을 구해주면 답을 얻어낼 수 있다. 오차를 $ 10^{-9} $ 로 맞춰주라 했기 때문에 cout.precision(16) 정도로 넉넉하게 잡아주면 된다. ...
백준 1074번 문제 바로가기 문제에 대한 첫 인상 반복되는 패턴이 있기에 분할해서 풀어나가면 좋겠다는 생각을 하게 되었다. 재귀함수를 세우는게 가장 깔끔해보여서 epoch()함수를 재귀해가면서 풀어내었다. 재귀함수는 결과물을 보면 깔끔한데 직접 구현하는건 은근 까다롭단 말이지… n과 전체 길이를 자꾸만 헷갈려서 코드를 고치기를 거듭했다. ㅜㅜㅋㅋ 문제를 처음부터 제대로 보고 한번에 풀어내는 연습하쟈!! #include <iostream> #include <cmath> using namespace std; long long epoch(int n, int r, int c){ // r행 c열 if (n == 0){ return 0; } int size = 1 << n; int half = size / 2; if (r < half && c < half){ return epoch(n-1, r, c); } else if (r < half && c >= half){ return pow(half, 2) + epoch(n-1, r, c-half); } else if (r >= half && c < half){ return 2*pow(half, 2) + epoch(n-1, r-half, c); } else{ return 3*pow(half, 2) + epoch(n-1, r-half, c-half); cout << "yes" << endl; } } int main() { int n, r, c; cin >> n >> r >> c; cout << epoch(n, r, c); return 0; }
백준 17386번 문제 바로가기 문제에 대한 첫인상 최근 geometry 문제들에 대한 경험치를 높이기 위해서 관련 문제들을 열심히 풀어보고 있다. 이번에 풀어볼 문제는 “두 선분이 주어졌을 때, 서로 교차하는지 아닌지 판단"하는 문제였다. 17386번 문제의 경우 “세 점이 일직선 위에 있는” 경우는 없으므로 상대적 방향만 고려해주면 쉽게 구할 수 있었다. 공간 상에서의 선분의 관계를 구할 때에 기울기를 이용하는 방법도 있겠지만, 외적을 활용하면 더욱 편하게 풀 수 있다. 외적의 부호를 비교하면 두 벡터가 반시계/시계/일직선 상에 위치하는지 확인할 수 있다. ...
백준 17387번 문제 바로가기 백준 17386번 - 선분 교차 2 문제에서 세 점이 한 직선상에 있는 경우를 포함한 문제이다. 앞에서 이용한 CCW 알고리즘을 활용하면 되지만 조건을 추가로 고려야해야해서 간단한 문제는 아니었다. 조건문 분기에서 자꾸만 에러가 발생해서 애를 먹었다… 실수한 포인트는 다음과 같다. int로 하게 되면 CCW 계산 과정에서 overflow 가능성이 있어서 에러가 발생한다. if (ccw2 ==0 && ccw3 == 0) 와 같이 4점 모두 일직선에 있는 경우 x좌표만 비교하면 안되고 y좌표도 비교해줘야 한다. 0 1 0 2 0 3 0 4 와 같은 반례가 있기 때문!! #include <iostream> #include <cmath> using namespace std; int ccw(long long x1, long long y1, long long x2, long long y2, long long x3, long long y3){ long long temp = (x2-x1)*(y3-y1); temp -= (y2-y1)*(x3-x1); if (temp > 0){ return 1; // 반시계 방향 } else if (temp < 0){ return -1; // 시계 방향 } else{ return 0; // 일직선 } } int main() { long long x1, y1, x2, y2, x3, y3, x4, y4; cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4; int ccw2 = ccw(x1, y1, x2, y2, x3, y3)*ccw(x1, y1, x2, y2, x4, y4); int ccw3 = ccw(x3, y3, x4, y4, x1, y1)*ccw(x3, y3, x4, y4, x2, y2); if (ccw2 <= 0 && ccw3 <= 0){ if (ccw2 ==0 && ccw3 == 0){ // 4점 모두 일직선 if ((max(x1, x2) < min(x3, x4)) || (max(x3, x4) < min(x1, x2))){ cout << 0; } else if ((max(y1, y2) < min(y3, y4)) || (max(y3, y4) < min(y1, y2))) { cout << 0; } else{ cout << 1; } } else{ cout << 1; } } else{ cout << 0; } return 0; }