Prefix Sum 알고리즘이란?문제를 풀다 보면 배열에서 특정 구간의 합을 구해야 하는 문제들을 종종 만나곤 한다. 한 번만 계산해야 한다면 반복문을 통해 \(O(N)\)의 시간 복잡도로 해결할 수 있지만, 여러 번 반복해서 계산해야 한다면 조금 더 효율적인 알고리즘이 필요하다. 이때 사용할 수 있는 알고리즘이 Prefix Sum이다. Prefix Sum 알고리즘은 배열의 첫 번째 원소부터 각 원소들까지의 합을 미리 계산해두는 알고리즘이다. 예를 들어, 배열 [1, 2, 3, 4, 5]가 있을 때 첫 번째 원소의 Prefix Sum은 1, 두 번째 원소의 Prefix Sum은 1 + 2 = 3, 세 번째 원소의 Prefix Sum은 1 + 2 + 3 = 6 이 된다. 이렇게 미리 배열의 모든 원소들의..
문제 링크https://www.acmicpc.net/problem/2417 문제 요약문제에서 주어진 N의 제곱근을 소수점에서 올림 한 값을 구하는 문제이다. 함정이 가득한 문제문제 자체는 상당히 간단해 이제 막 PS에 입문한 사람들이 연습용으로 풀기 좋은 문제로 보인다. 그리고 문제 번호도 2000번 대여서 뭔가 연습문제 같은 느낌도 상당히 든다.???: 제곱근을 수하고 소수점에서 올림을 하라니?! sqrt 함수를 이용하면 그냥 풀 수 있는 문제잖아! 이런 생각의 흐름을 거치고 나면 아래와 같은 코드를 작성하고 제출을 누르게 된다.#include #include using namespace std;int main() { unsigned long long n; cin >> n; ..
문제 링크https://www.acmicpc.net/problem/15989 문제 요약정수 N이 주어졌을 때, 1, 2, 3의 합으로 N을 나타내는 경우의 수를 찾는 문제이다. 순서만 다른 것은 같은 경우라는 것을 주의해야 한다. 문제 풀이이 문제는 전형적인 동적 계획법(dynamic programming, 이하 DP)로 해결할 수 있다. DP는 상향식과 하향식 두 가지 방법으로 구현할 수 있는데 보통은 하향식 방법이 구현이 쉽고 직관적이다. 하지만 슬라이딩 윈도우, 컨벡스 헐 트릭등 다양한 DP 최적화 전략을 이용하기 위해서라면 상향식 방법도 이용할 줄 알아야 하기 때문에 두 가지 방법으로 모두 구현을 해본다. 하향식으로 문제 풀기상향식으로 문제를 풀 때 가장 먼저 해야 할 일은 재귀적으로 문제를 해결..
문제 링크https://www.acmicpc.net/problem/17086 문제 요약임의의 점 \((i, j)\)의 안전거리는 \((i, j)\)에서 시작해서 아기 상어가 있는 곳까지의 최소 거리를 의미한다. 여기서 거리는 인접한 8방향(상하좌우 및 대각선)으로 이동한 칸 수로 계산한다. 격자판 위의 모든 점들 중에서 안전거리가 최대인 값을 찾아 출력하는 것이 이 문제의 목표이다. 문제 풀이기본적인 풀이너비 우선 탐색(이하 BFS)을 이용하면 임의의 점 \((i, j)\)에서 가장 가까운 아기 상어까지의 거리를 계산할 수 있다. 그리고 N과 M의 크기가 작으므로 모든 점들에 대해서 BFS를 한 번씩 돌려도 제한시간 내에 충분히 답을 구할 수 있다. 아래 더보기 버튼을 누르면 이 방법으로 푼 코드를 볼..
문제 링크https://www.acmicpc.net/problem/9376 문제 요약두 죄수 A, B가 최소한의 문을 열어 감옥에서 탈출하려고 한다. 한 죄수가 문을 열면, 그 문은 계속 열려 있어서 다른 죄수도 그 문을 이용할 수 있다.(원래 문제에서는 감옥 밖에 있는 상근이가 특별한 기술을 이용해 문을 열어준다고 되어 있지만, 문제를 더 쉽게 이해할 수 있게 내용을 살짝 바꿨다.) 문제 풀이가장 먼저 떠오르는 생각은 두 죄수의 상태를 동시에 관리하는 것이다. 하지만 죄수가 있을 수 있는 장소는 1만 곳이고, 이를 두 죄수의 상태로 표현하면 1억 가지의 경우의 수가 생긴다. 여기에 탈출을 위해 이용한 문의 개수까지 고려한다면 이 방법은 문제를 제한 시간 내에 풀 수 있는 방법이 아니다. 경우의 수 나누..
문제 링크https://www.acmicpc.net/problem/10021 문제 요약농부 John은 가뭄 때문에 N개의 농지에 물을 공급하기 위한 수로를 설치하려고 한다. 각 농지는 2차원 평면 위의 점 \((x_i, y_i)\)로 나타내며, 서로 다른 두 농지 \(i\)와 \(j\)를 연결하는 수로를 건설하는 비용은 \((x_i - x_j)^2 + (y_i - y_j)^2\)으로 계산한다. 이 문제는 모든 농지가 서로 물을 공급받을 수 있도록 수로를 설치하는 최소 비용을 계산하는것이 목표다. 제약 사항이 하나 있다면 수로를 건설하는 업자가 수로 건설 비용이 C 이상이 되는 것만 설치한다는 것이다. 문제 풀이이 문제에서 농지는 그래프의 노드로, 수로는 간선으로 모델링 할 수 있다. 이렇게 그래프로 모델..
문제 링크https://www.acmicpc.net/problem/17404 문제 요약N개의 집을 다음 두 개의 규칙에 맞게 빨강, 초록, 파랑 중 하나로 칠해야 한다.인접한 두 집의 색이 달라야 한다.1번 집과 N번 집의 색이 달라야 한다.각 집을 특정 색으로 칠하는 비용이 주어졌을 때, 모든 집을 규칙에 맞게 칠할 때 드는 최소 비용을 구하는 문제이다.원래 문제에는 규칙이 세 개 있지만, 이해를 돕기 위해 두 개로 정리했다. 문제 풀이이 문제는 동적 계획법(dynamic programming)을 이용해 해결할 수 있다. 먼저, 부분 문제를 해결할 수 있는 함수를 정의한다. \(findMinCost(idx, prevColor) =\) idx - 1번째 집을 prevColor로 칠했을 때, idx번째 ..
문제 링크https://www.acmicpc.net/problem/1022 문제 요약반시계 방향을 따라 소용돌이 모양으로 숫자를 채운 뒤, 주어진 범위의 숫자를 포맷에 맞게 출력하는 문제 문제 풀이이 문제를 푸는 방법에는 실제로 소용돌이를 만들어보는 시뮬레이션 방법과 특정 좌표의 숫자를 구할 수 있는 규칙을 찾는 방법 두 가지가 있다. 이 문제를 풀기 위해 접근할 때 보통 두 번째 방법을 많이 생각하는 것 같다. 하지만 입력으로 주어지는 수의 제한 범위와 현대 컴퓨터의 연산속도를 이용하면 직접 시뮬레이션을 돌려 푸는 방법도 있다는 것을 소개하고 싶다.풀이 1. 시뮬레이션모눈종이에 소용돌이 모양으로 숫자를 채우는 시물레이션을 돌려보는 상상을 해보자. 입력으로 주어지는 좌표의 최솟값은 -5,000이고 최댓값..
문제 링크 https://www.acmicpc.net/problem/1111 문제 요약점화식 \(x_{i+1} = x_i * a + b\) 으로 만들어진 길이 \(N\)의 수열이 주어진다. \(a\), \(b\)를 찾아 수열의 다음 항을 출력하는 문제이다. 문제 번호도 그렇고 제목도 그렇고 뭔가 쉬워보이는 냄새가 난다. IQ Test 정도는 뭔가 쉽게 통과할 것 같은 근자감도 생긴다. 그렇게 9년 전의 나는 쉬운 마음으로 1111번에게 도전했다 참패했다. 9년이 지난 지금의 나는 어떨까? 쉽진 않았지만 그래도 어찌저찌 9년 전 참패는 만회할 수 있었다. 구미가 당기는 번호, 쉬운 제목으로 사람을 현혹시키고 패배의 감정을 맛보게 해주는 악마의 문제 백준 1111번 풀이를 적어본다. 문제 풀이세 개의 연속된..
백준에서 풀만한 문제가 뭐가 있다 어슬렁거리다 과거의 내가 풀지 못했던 문제를 지금 내가 푼다면 맞출 수 있을까 궁금해졌다. 슬프게도 시도했지만 맞지 못한 문제가 많아 숫자가 작은 것부터 다시 시도해 봤다. 그래서 선택한 1039번!! 무려 9년 전, 그러니까 2014년에 시도하고, 2015년에 다시 한번 시도하고 나에게 잊혔던 1039번이 다시 나에게 다가왔다. 과연 지금의 나는 과거의 나보다 더 강해졌을까 긴장되는 마음으로 문제를 다시 읽어봤는데 다행히 과거의 나보다는 더 강해진 것 같아 이렇게 풀이를 작성해 본다.문제 링크https://www.acmicpc.net/problem/1039 문제 요약주어진 정수 \(N\)에서 서로 다른 두 자릿수의 위치 \(i\), \(j\)를 선택하여 숫자를 서로 교..
티스토리에서 MathJax 스크립트를 삽입했는데도 MathJax가 동작하지 않을 때 사용할 수 있는 방법을 소개하려고 한다. 기존에 사용하던 티스토리 기본 스킨을 hELLO 스킨으로 변경하고 난 다음에 멀쩡히 동작하던 MathJax가 동작하지 않기 시작했다. 구글링을 해도 마땅한 해결 방법을 찾지 못해, 온리 영어로 되어있어 최후의 보루로 남겨놓은 공식 문서를 열었는데 결국 그곳에서 힌트를 발견할 수 있었다. 방법 1. Lazy typesetting"Lazy typesetting"은 페이지에 있는 수식들이 실제로 브라우저 뷰포트에 진입할 때까지 그 렌더링을 지연시키는 설정인데, 보는 순간 이거 된다라는 생각이 들었다. 자세한 내용은 공식 문서에서 읽을 수 있다. 방법 2. MathJax 강제로 한 번 더..
대부분의 프로그래밍 언어에서 데이터 타입을 확인할 수 있는 연산자를 제공한다. 자바스크립트도 데이터 타입을 확인할 수 있는 \(typeof\) 연산자를 제공한다. \(typeof\) 연산자는 피 연산자의 데이터 타입을 문자열로 리턴한다. 사용법은 어렵지 않기때문에 실습 코드로 설명을 대신한다. 소스 코드/* number example */var intNum = 10;var floatNum = 3.14;console.log(typeof intNum, typeof floatNum); // number number/* string example */var ch = 'a';var str = "hello world";console.log(typeof ch, typeof str) // string string/*..
