프로그래밍 공부 노트

https://www.acmicpc.net/problem/14658 14658번: 하늘에서 별똥별이 빗발친다 첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 www.acmicpc.net 문제에서 필요한 건 지구에 부딪히는 별똥별의 개수의 최솟값, 즉 트램펄린으로 튕겨내는 별똥별의 개수의 최댓값이므로 트램펄린의 정밀한 위치는 신경쓸 필요 없다. 주어진 별똥별 중 별똥별 A와 별똥별 B(이 때 A와 B는 같을 수도, 다를 수도 있다), 그리고 트램펄린의 왼쪽 꼭지점 P에 대해, A의 x좌표와 P의 x좌표가 ..

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 구역의 개수는 최대 10개이다. 구역을 두 종류로 나누는 모든 경우의 수는 2 ^ 10 - 2 = 1022(개)이고, 각 지역구가 인접한 지역만으로 이루어져 있는지는 각 지역에 대해 인접한 지역을 탐색해 확인할 수 있으므로 이 때의 시간 복잡도는 10 ^ 2 = 100, 각 지역구의 인구수 차이는 선형 시간이 소모되므로, 지역구를 이루는 모든 경우의 수를 매우 빠른 시간 안에 계산할 수 있다. #include type..

https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 이분 탐색과 투 포인터, 동적 계획법 세 가지 방법으로 해결할 수 있다. 이분 탐색 3인조의 코딩 실력의 합이 0일 경우, i번째 학생의 코딩 실력이 A_i일 때 나머지 두 학생의 코딩 실력의 합은 -A_i이다. 따라서 코딩 실력의 합이 k인 임의의 2인조를 구한 뒤, 코딩 실력이 -k인 학생의 수를 이분 탐색을 이용해 계산한다면 제한 시간 안에 코딩 실력의 합이 0이 되는 3인조의 수를 구할 수 있다..

대부분의 알고리즘 문제의 경우 문제를 해결하는 알고리즘이 존재하지만, 특정 상황을 구현하는 문제 등 어떤 경우는 문제를 해결하는 알고리즘이 존재하지 않을 수도 있다. 이럴 때 사용하는 알고리즘이 바로 브루트포스 알고리즘으로, 가능한 경우의 수를 모두 시도하여 문제를 해결해야 한다. 백트래킹은 브루트포스를 응용한 문제로, 브루트포스를 진행하다 불가능한 subset을 찾아낼 경우 해당 subset을 모두 제거하는 것을 말한다. 예를 들어 스도쿠를 백트래킹으로 해결한다고 할 때, 수를 빈 칸에 차례로 넣다가 불가능한 경우를 발견한다면 불가능한 경우를 건너뛰고 바로 다음 수를 넣어 탐색한다. 브루트포스 알고리즘 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드..

https://www.acmicpc.net/problem/3042 3042번: 트리플렛 상근이와 창영이는 트리플렛이라는 게임을 하고 있다. 이 게임을 하려면 칠판에 N*N 그리드를 그려야 한다. 그 다음 알파벳 대문자를 적절히 각 칸에 써 넣는다. 한 알파벳을 여러 칸에 쓸 수는 www.acmicpc.net 세 점 (x1, y1), (x2, y2), (x3, y3)가 한 직선에 있다면 (y2 - y1) / (x2 - x1) == (y3 - x3) / (y2 - x2)여야 한다. 이 때 double을 사용할 경우 오차가 발생할 수 있으므로 위 식을 정리하면 (y2 - y1)(x3 - x2) == (y3 - y2)(x2 - x1)이다. 주어진 조건에서 트리플렛은 세 알파벳이 직선을 이뤄야 한다고 되어 있다...

https://www.acmicpc.net/problem/24268 24268번: 2022는 무엇이 특별할까? 백준 온라인 저지의 신년대회 Hello, BOJ 2022!의 개최일은 2022년 1월 15일이다. 준겸이는 대회가 개최된다는 사실이 기뻐 제목을 뚫어져라 보다가 2022가 무언가 특별하다는 사실을 깨달았다. 그렇 www.acmicpc.net { 1, 0, 2, 3, ...}을 next_permutation으로 탐색하면서 10진수로 각각 변환하고, N보다 큰 수를 발견하면 그 수를, 발견하지 못했다면 -1을 출력한다. #include #include using namespace std; #define MAX_D 9 int main() { // N: 각 수가 한번씩 나오는 d진법을 찾을 수, d: ..

https://www.acmicpc.net/problem/20410 20410번: 추첨상 사수 대작전! (Easy) 한 줄에 걸쳐 준표가 좋아하는 소수 m, 참가자들이 정한 Seed, 시연으로 공개된 X1, X2 이 주어진다. 항상 가능한 상황만 입력으로 주어진다. www.acmicpc.net 문제의 조건의 범위가 0과 100 사이이므로, 브루트포스 알고리즘을 이용해 답을 찾아낼 수 있다. #include int main() { // m, seed, X1, X2: 문제에서 제공하는 조건 // a, c: 구할 값, X1_, X2_: 추정한 a와 c로 계산한 X1, X2 int m, seed, X1, X2, a, c, X1_, X2_; scanf("%d %d %d %d", &m, &seed, &X1, &X2..

https://www.acmicpc.net/problem/18119 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 기억하는 각 문자와 문자열에 든 각 문자를 비트마스킹 형태로 저장한다. 잊는 쿼리가 들어올 때 해당 문자를 기억함과 기억하는 쿼리가 들어올 때 해당 쿼리를 잊고 있음이 보장되므로, 쿼리가 들어올 때마다 기억하는 문자와 쿼리로 들어온 문자를 XOR연산한 뒤, 기억하는 각 문자와 문자열을 AND연산해 문자열을 얻은 개수를 출력한다. 이 과정을 모든 쿼리에 대해 진행하면 답을 얻을 수 있다. #in..

https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 높이가 i인 각 좌표를 저장한 뒤, 땅을 각 높이로 고르게 만드는 비용을 계산해 최소 비용과 이 때의 높이를 출력한다. #include using namespace std; #define MAX_H 256 #define INF 0x3f3f3f3f int abs(int n) { return n b ? a :..

https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 각 수를 노드, 각 수와 그 수에 제곱수를 더한 수와의 관계를 에지라고 보면, 이 문제는 제곱수를 이용한 bfs 문제로 볼 수 있다. #include #include using namespace std; #define MAX_N 50000 int min(int a, int b) {return a < b ? a : b; } int main() { // visit[..