문제 링크https://www.acmicpc.net/problem/32069 문제 요약수직선 도로 위해 \(N\) 개의 가로등이 위치해 있다. 각 위치에서 가장 가까운 가로등까지의 거리를 계산하고, 그 거리들을 오름차순으로 정렬한 뒤 앞에서부터 \(K\) 개 출력하는 문제이다. 문제 풀이문제에서는 어두운 정도를 각 위치로부터 가장 가까운 가로등까지의 거리로 정의하고 있다. 그래서 처음에는 각 위치별로 가장 가까운 가로등까지의 거리를 모두 계산해야 한다고 생각할 수 있다. 하지만 도로의 길이 \(L\)이 최대 \(10^{18}\)까지 될 수 있기 때문에, 모든 위치를 전부 탐색하는 완전탐색은 사실상 불가능하다. 이 문제를 해결하기 위해서는 가로등을 기준으로 생각할 필요가 있다. 각 가로등들을 중심으로 가까..
문제 링크https://www.acmicpc.net/problem/32068 문제 요약이 문제는 시작점 \(S\)에서 출발하여 보물 위치 \(L\) 또는 \(R\)에 방문하는데 필요한 이동 횟수를 계산하는 것이다. 이동 패턴은 한 단계식 오른쪽과 왼쪽을 번갈아가며 한 칸씩 점점 더 멀리 이동하는 방식이다. 문제 풀이서브태스크 4번까지는 입력 제한이 크지 않아 시뮬레이션으로도 해결할 수 있다. 그러나 서브태스크 5번을 해결하려면 더 효율적인 접근 방법이 필요하다. 먼저, \(S\)보다 왼쪽에 있는 \(L\)을 방문하기 위해서는 \(S\)와 \(L\)의 거리만큼 떨어진 오른쪽에 있는 점들을 모두 방문해야 한다. 따라서 \(L\)을 방문하기 위한 이동 횟수는 \(2 \times (S - L)\)이다. 마찬가지..
문제 링크https://www.acmicpc.net/problem/32036 문제를 바꿔서 생각하기배열에 연산을 직접 하는것이 아니라 수학적인 방법으로 접근하면 조금 더 쉽게 문제를 해결할 수 있다. 1번 쿼리에서 주어지는 a, b를 아래와 같이 함수로 표현될 수 있다.(문제에서는 x, y라고 했는데, 좌표 평면에서의 x, y와 겹치기 때문에 헷갈리지 않기 위해 a, b로 바꿔서 적었다.)$$f_i(x) = |x - a_i| + b_i$$주어진 여러 개의 1번 쿼리를 통해 업데이트된 배열의 값은 각 1번 쿼리의 함수들을 더한 것으로 표현될 수 있다.$$F(x) = \sum_{i=1}^{n} f_i(x) = \sum_{i=1}^{n}|x - a_i| + \sum_{i=1}^{n} b_i$$2번 쿼리에서는 ..
왜 Reset CSS와 Normalize CSS가 필요한가웹 개발을 하다 보면 HTML에 아무런 스타일을 작성하지 않았는데도 스타일이 적용된 것을 본 적이 있을 것이다. 이는 브라우저가 HTML 태그들에 대해 기본적으로 적용하는 마진, 패딩, 폰트 크기 등이 있기 때문이다. 문제는 각 브라우저마다 기본적으로 적용하는 스타일이 다를 수 있다는 점이다. 이로 인해 동일한 HTML 코드가 브라우저마다 다르게 보일 수 있다. 이를 해결하기 위해 등장한 개념이 바로 Reset CSS와 Normalize CSS이다. 이 두 개념은 모두 스타일의 일관성을 유지하는 것을 목표로 하지만, 이를 달성하기 위한 방식에 차이가 있다. 이제 Reset CSS와 Normalize CSS의 차이점과 각각의 장단점을 살펴보자. Re..
문제 링크https://www.acmicpc.net/problem/31997 문제 요약N명의 사람들이 T시간 동안 진행되는 회의에 참석하고 떠나는 시간이 주어진다. 그리고 각 사람들은 서로 친구 관계를 맺고 있다. 회의가 진행되는 동안 특정 시각 t에서 회의에 참석한 사람들 중 친구인 쌍이 몇 쌍인지 계산하는 문제이다.. 문제 풀이입력 데이터 처리N명의 사람들이 언제 도착하고 떠나는지, 그리고 누구와 친구 관계를 맺고 있는지 저장해야 한다. 각 시간마다 어떤 사람이 회의에 참석하고 떠나는지를 기록하면, 회의가 진행되는 모든 시간 동안 현재 참석하고 있는 사람들을 쉽게 파악할 수 있다. 또한, 친구 관계는 인접 리스트를 이용해 저장한다.// 각 시간대별로 회의에 참석하는 사람을 저장할 벡터vector> i..
문제 링크https://www.acmicpc.net/problem/31965 피로도를 최소로 하는 회의 순서 정하기회의 세트에 참여하는 K개의 집의 좌표를 오름차순으로 \(x_1, x_2, \cdots, x_k\)라고 하고, 각 집에서 회의를 개최했을 때 드는 비용을 \(c_1, c_2, \cdots, c_k\)라고 정의하자. 각 집에서 회의를 개최했을 때 드는 비용을 계산한 뒤 유심히 관찰해 보면, 회의 비용이 감소하거나 증가하는 방향으로 회의를 개최할 때 피로도가 최소가 된다는 것을 발견할 수 있다. 그 이유는 회의 비용이 정렬되어 있으면 인접한 회의의 비용 차이를 최소화할 수 있기 때문이다. 회의 비용이 정렬되어 있을 때 피로도는 \(c_1, c_2, \cdots, c_k\)중에서 최댓값과 최솟값의..
HTML에서 DOCTYPE의 역할과 중요성HTML을 작성할 때 첫 번째 줄에 코드를 꼭 작성해야 한다. 이 코드는 브라우저에게 HTML을 최신 스펙에 맞게 표시해야 한다고 알려준다. 또한 검색엔진들이 문서를 수집할 때 DOCTYPE이 있는 문서에 더 높은 점수를 준다고 비공식적으로 알려져 있다. 올바르게 UI 표시와 더 높은 SEO 점수를 고려할 때, HTML 첫 번째 줄에 을 넣지 않을 이유가 없다. 그런데 우리는 HTML 문서를 작성하는 것이 명확한데도 불구하고 왜 브라우저에게 이 문서가 HTML로 만들어졌다고 알려줘야 하는 것일까? DOCTYPE이 무엇이고, 그리고 왜 등장했는지에 대해 알아보자. DOCTYPE이 등장한 배경HTML과 브라우저가 처음 등장했을 당시에는 브라우저마다 HTML을 해석하..
문제 링크https://www.acmicpc.net/problem/31964(KOI 2024 1차대회 초등부 3번, 고등부 1번) 문제 요약트럭이 직선 도로상의 각 집을 특정 시각 이후에 방문에 물건을 회수한 후 다시 출발지로 돌아올 수 있는 최단 시간을 구하는 문제이다. 문제 풀이그리디로 접근하기출발지점에서 마지막 집까지 왕복하는 거리인 \(2 \times X_n\)은 트럭이 필수적으로 사용해야 하는 시간이다. 따라서 이 시간을 제외하고 각 집에서 기다려야 하는 시간을 최소화하는 것이 중요하다. 오른쪽 끝 집부터 방문해 물건을 회수하면, 트럭이 출발지점으로 돌아오는 시간에 각 집에서 기다려야 하는 시간이 포함될 수 있다. 그래서 트럭이 가장 오른쪽 집부터 방문에 물건을 회수하는 것이 가장 최선의 선택지..
문제 링크https://www.acmicpc.net/problem/31963(2024 KOI 1차대회 초등부 2번, 중등부 1번) 문제 요약길이가 N인 수열이 주어졌을 때, 수열의 한 원소에 숫자 2를 곱하는 연산을 할 수 있다. 이때 주어진 수열을 오름차순으로 만들 수 있는 최소한의 연산 횟수를 구하는 문제이다. 문제 풀이시뮬레이션으로 문제 풀기(부분점수)수열의 두 번째 원소부터 마지막 원소까지 순회하면서, 각 원소가 이전 원소보다 커질 때까지 2를 곱하는 과정을 반복하고, 그 횟수를 직접 계산하는 방법으로 문제를 풀 수 있다.int simulate(const vector& vi) { vector incresing_order(vi.size()); incresing_order[0] = vi[..
문제 링크https://www.acmicpc.net/problem/16937 문제 요약모눈종이 안에 두 개의 스티커를 겹치지 않게 붙일 때, 그 넓이의 합의 최댓값을 구하는 문제이다. 문제 풀이N의 크기가 작기 때문에 문제를 해결하기 위해 완전탐색을 사용할 수 있다. 따라서, 두 개의 스티커를 골라 모눈종이 안에 붙일 수 있는지 판단하는 함수를 작성하는 것이 이 문제를 해결하기 위한 핵심이다. 1. 첫 번째 스티커 붙이기먼저, 한 개의 스티커를 모눈종이 안에 붙일 수 있는지 판단하는 함수인 isInside 함수를 작성한다. 이 함수는 왼쪽 사각형이 오른쪽 사각형을 포함할 수 있는지 판단한다. 왼쪽 사각형의 가로와 세로가 오른쪽 사각형의 가로와 세로보다 같거나 큰지 확인하는 것으로 구현할 수 있다.boo..
문제 링크https://www.acmicpc.net/problem/30804 문제 요약1부터 9로 이루어진 수열이 주어진다. 이때, 연속된 부분 수열 중에서 숫자가 최대 두 개의 숫자로만 이루어진 부분 수열의 최대 길이를 구하는 문제이다. 문제 풀이이 문제를 푸는 가장 효율적인 방법은 슬라이딩 윈도우 기법을 이용하는 것이다. 하지만 문제에서 주어진 제약 조건들을 잘 활용하면 조금은 더 간단한 방법으로 문제를 해결할 수 있다. 이 문제가 Division 1, Division 2에 동시에 출제된 것을 보면 다양한 접근 방법을 생각할 수 있게 의도된 문제로 보인다. 문제의 제약 조건을 활용하면 더욱 효과적이고 빠른 해결 방법을 찾을 수 있기 때문에, 문제를 풀기 전에 제약 조건을 먼저 확인하는 것이 중요하다..
문제 링크https://www.acmicpc.net/problem/17845 문제 요약최대 공부시간 \(N\)과 과목 수 \(K\)가 주어진다. 이어서 각 과목 \(i\)의 중요도 \(I_i\)와 필요한 공부시간 \(T_i\)가 주어진다. 최대 공부시간 \(N\)을 초과하지 않으면서 중요도 합이 최대가 되도록 과목을 선택할 때, 최대 중요도를 구하는 문제이다. 문제 풀이이 문제는 전형적인 배낭 문제(Knapsack Problem)로 동적 계획법(Dynamic Programming)을 이용해 풀 수 있다. 동적 계획법은 Top Down 방식과 Bottom Up 방식으로 풀 수 있는데, 여기서 두 가지 방법 모두를 이용해 문제를 푸는 방법을 소개한다. Top Down 방식으로 문제 풀기동적 계획법을 Top ..
