복습 정리 노트

백준 BOJ 12084번 : Captain Hammer (small) 문제 난이도 : Silver IV 알고리즘 분류 : 이분 탐색 물체를 초기 속도 V, 각도 θ로 쏠 때 거리 D만큼 보내기 위해서 몇 도로 쏴야 하는지를 구하는 문제이다. 고등학교 1학년 수준의 물리 지식이 있다면 간단한 이분탐색으로 답을 구해줄 수 있다. 위와 같이 운동 방정식 2개를 가지고 풀어주면 세타에 대한 식이 나온다. 물론 아크사인으로 구할 수도 있겠지만 문제 분류가 이분 탐색으로 되어있으니 이분 탐색으로 풀어보자. 범위는 0도에서 45도 사이로 잡으면 된다. (왜냐하면 x = 90 - x에서 삼각함수의 대칭성에 의해 같은 답이 나온다.) #include #define int long long using namespace s..

백준 BOJ 2568번 : 전깃줄 - 2 문제 난이도 : Platinum V 알고리즘 분류 : LIS (가장 긴 증가하는 부분 수열) 위의 그림처럼 전깃줄의 연결 상태가 주어질 때, 교차하는 전깃줄이 없도록 만들기 위해 제거해야 하는 전깃줄의 수가 최소인 경우 제거해야 할 전깃줄의 A에 연결된 번호들을 오름차순으로 구하는 문제이다. A와 연결된 번호들을 오름차순으로 정렬했을 때, B와 연결된 번호들도 오름차순이라면 교차하는 선분이 없다는 것이다. 따라서, A의 위치들에 대해 오름차순으로 정렬하고 B의 위치들에 대해 LIS를 구한 뒤 이에 포함되지 않는 원소들을 찾아 다시 A와 연결되는 위치로 가서 해당 번호들을 제거해주면 된다. 연결 관계가 이중으로 되어있고 A의 번호와 B의 번호를 고려해야하며, 모든 ..

오랜만에 코드포스(Codeforces) 라운드에 참가하려고 했는데 7시에 방 와서 혼밥하고 너무 피곤해서 그대로 뻗어버렸다. 일어나보니 시간은 12시 반이 넘어있었다. 코드포스 라운드 많이 치겠다고 다짐했는데 정작 최근에 아예 안 풀어서 진짜로 지금 배치 보면 그린 나올 것 같다. 아무튼 오늘도 백준 문제 풀이를 해보자. 백준 BOJ 18977번 : Maximum Multiple 문제 난이도 : Silver I 알고리즘 분류 : 정수론 (새벽에 백준을 들어갔는데 진짜 우연히 koosaga님의 제출이 맨 위에 있길래 무슨 문제일까 궁금해서 풀어봤다.) 주어진 N에 대해, x + y + z = N이고 x | N, y | N, z | N인 순서쌍 (x, y, z) 중 xyz 값의 최대를 구하는 문제이다. ax..

백준 BOJ 20040번 : 사이클 게임 문제 난이도 : Gold IV 알고리즘 분류 : 분리 집합 N개의 정점이 있는 그래프에 M개의 간선을 연결할 때 몇 번째 간선부터 사이클이 생기는지를 구하는 문제이다. 사이클의 발생은 두 노드를 간선으로 연결하기 전에 두 노드가 이미 연결 관계인 경우 발생한다. 따라서 분리 집합을 이용하여 연결 관계를 체크해주다가 두 노드 사이가 연결 관계라면 해당 번째 번호를 출력해주면 된다. #include #define int long long using namespace std; vector v; int f(int x) { if(v[x] == x) return x; else return v[x] = f(v[x]); } main() { ios_base::sync_with_s..

백준 BOJ 3184번 : 양 문제 난이도 : Silver I 알고리즘 분류 : DFS '#'으로 분리된 우리 안에 양과 늑대가 있을 때, 양이 늑대보다 많다면 양은 늑대를 쫓아내고 그 외의 경우에는 늑대가 양을 잡아먹는다고 할 때 시간이 지난 뒤 총 양의 수와 늑대의 수를 구하는 문제이다. DFS를 이용하여 각 우리 안에 있는 양과 늑대의 수를 구해주고, 문제에서 제시한 조건에 맞게 총 양의 수와 늑대의 수에 값을 더해주면 된다. #include #define int long long using namespace std; int N, M, c, d; vector v; vector vis; void f(int x, int y) { vis[x][y] = true; if(v[x][y] == 'o') c++;..

백준 BOJ 21739번 : 펭귄 네비게이터 문제 난이도 : Gold II 알고리즘 분류 : 조합론, DP 2 x N 격자에서 펭귄이 어떤 경로로 오른쪽과 아래로만 이동하더라도 더 큰 번호로만 이동하며 도착할 수 있도록 번호를 매긴다고 할 때 경우의 수를 구하는 문제이다. 높이가 2이므로 2부터 N-1까지 위쪽 또는 아래쪽 줄을 선택하면서 번호를 매길 수 있다. 규칙을 찾아보면 윗줄보다 아랫줄을 선택하는 순간이 2번 이상일 경우 조건에 어긋나게 된다. 따라서 이는 (0, 0)에서 (N, N)으로 격자를 따라 오른쪽과 아래로만 이동하는데, 아래를 오른쪽보다 2번 이상 선택하지 않는 경우의 수와 같고 이를 시각화하면 다음과 같다. 위는 N = 4일 때의 문제 상황을 앞서 설명한 다른 격자판으로 일대일 대응시..

백준 BOJ 4383번 : 점프는 즐거워 문제 난이도 : Silver V 알고리즘 분류 : 구현 길이 N인 수열이 주어질 때 인접한 N-1개의 정수 쌍에 대해 그 차이의 절댓값이 1 ~ N-1까지 모두 등장하는 수열인지 아닌지를 판별하는 문제이다. 간단한 구현 문제인데 정답률이 24%밖에 되지 않아 반례가 있나 싶었는데, 첫 제출에 간단하게 정답 처리를 받은 것으로 보아 EOF까지 입력받는 처리가 까다로워서 많은 사람들이 틀리지 않았나 싶다. #include #define int long long using namespace std; main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); int N; while(cin >> N)..

백준 BOJ 20162번 : 간식 파티 문제 난이도 : Silver II 알고리즘 분류 : DP 문제에 조건이 앞쪽에 숨겨져 있는데, 잘 보면 이전에 먹은 간식보다 점수가 높은 간식만 먹는다는 조건이 있다. 따라서 이 문제는 합이 가장 큰 증가하는 부분 수열 문제가 된다. 마지막에 답을 출력할 때 dp[N-1]이 아닌 모든 dp 값 중 최댓값을 출력해야 함에 유의하자. #include #define int long long using namespace std; main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); int N; cin >> N; vector v(N); for(int i=0; i> v[i]; vector dp(v)..

백준 BOJ 9764번 : 서로 다른 자연수의 합 문제 난이도 : Silver I 알고리즘 분류 : DP 자연수 N을 서로 다른 자연수들의 합으로 나타내는 방법의 수를 구하는 문제이다. 아주 아주 기초적인 DP 문제임에도 점화식을 못 떠올려서 꽤 오래 막혔고, 풀이를 참고했다. 점화식은 다양한 방법으로 세울 수 있겠으나, 참고한 풀이는 "dp(a, b) : b 이하의 수들의 합으로 a를 만드는 경우의 수"와 같이 dp를 정의하는 것이다. 그렇게 한다면 b를 증가시켜 가면서 dp(a, b) = dp(a-b, b+1) + dp(a, b+1) (즉, b를 a의 합에 넣어주는 경우와 그렇지 않은 경우의 합) 탑다운 방식으로 답을 구해줄 수 있다. 처리해야 할 예외는 다음과 같다. 1. dp 값이 이미 구해진 경..

2022년 7월 12일 화요일 푼 문제들과 사용되는 개념들을 정리한다. 백준 BOJ 1615번 : 교차 개수 세기 문제 난이도 : Gold I 알고리즘 분류 : 세그먼트 트리 N개의 점들의 쌍에 대해 M개의 선분이 주어질 때 교차 개수를 세는 문제이다. 세그먼트 트리의 가장 대표적인 문제들 중 하나인 Inversion Counting Problem인데 왜 그동안 못 풀고 있었나 봤더니 점들의 위치가 중복되어 주어진다는 점 때문이었다. 생각해보니 기존의 Inversion Counting Problem에서 같은 점이 주어져도 update 함수에서 tree[node] = 1로 설정해주었는데, 해당 노드에 점이 하나 추가되는 것이므로 간단히 tree[node]++와 같이 값을 갱신해주기만 하면 되는 문제였다. ..