이 글은 C, C++에 익숙한 개발자의 시점으로 작성됐습니다. Symbol과 Object는 다루지 않습니다. 이 두 가지는 다른 포스팅에서 자세히 다룰 예정입니다. 자바 스크립트의 데이터 타입은 크게 두 가지로 나눠질 수 있다. 첫 번째는 기본 타입, 두 번째는 객체(Object)이다. 기본 타입은 숫자, 문자열, 불리언, undefined, null, Symbol(ECMAscript6)로 나눠지며 객체는 배열, 함수, 정규표현식으로 나눠진다. 이 글에서는 기본 타입에 해당하는 데이터 타입들을 살펴볼 것이다. 숫자(Number) C, C++, Java는 숫자를 정수, 실수로 나눠 \(int\), \(float\), \(double\) 등과 같은 다양한 타입이 존재한다. 하지만 자바스크립트에서는 모든 숫자..
프로그래밍 대회에서 좋은 성적을 올리기 위한 방법에는 어떤 것이 있을까요? 아마 대부분의 사람들이 다양한 알고리즘을 알고 있는 것이라 대답할 것입니다. 물론 문제를 풀기 위해서 여러 알고리즘을 아는 것은 매우 중요합니다. 하지만 단순히 알고리즘만 많이 알고 있다고 해서 프로그래밍 대회에서 좋은 성적을 거둘 수 있는 것은 아닙니다. 그렇다면 어떤 것이 가장 중요할까요? 혼자서 공부를 할 때는 제한시간이 없기 때문에 여유로운 마음으로 코딩을 할 수 있습니다. 하지만 프로그래밍 대회에서는 그렇지 않습니다. 제한시간이 있고 다른 사람들이 문제를 얼마나 풀었는지 볼 수 있습니다. 또한 팀원들이 같이 있을 경우 내가 잡은 문제를 꼭 풀어야 한다는 압박감을 받을 수 있습니다. 이러한 상황 속에서 여유로운 마음으로 코..
1. 방 배정 https://www.acmicpc.net/problem/13300 학생들을 학년별, 성별로 한 방에 배정하려고 하는데 필요한 최소 방의 개수를 구하는 문제다. 문제에서 요구하는 대로 학년별, 성별로 인원을 센 다음에 각각에 대해 최소로 필요한 방의 개수를 센 뒤 더해주면 된다. 이는 나눗셈과 나머지 연산으로 쉽게 구할 수 있다. #include int n, k, s, y, C[7][2]; int main() { scanf("%d%d", &n, &k); while (n--) { scanf("%d%d", &s, &y); ++C[y][s]; } int ans = 0; for (int i = 1 ; i
문제 링크 https://www.acmicpc.net/problem/5626 문제 요약 현재 제단의 상태가 주어진다. 도둑이 훔쳐간 부분은 -1이고 남아있는 부분은 정수로 표현이 되어있다. 이 때 가능한 초기 제단의 경우의 수를 구하는 문제다. 문제에서 초기 제단을 만드는 방법은 주어진다. 문제 풀이 모든 열의 초기값은 0이다. 이 때 한가지 연산을 할 수 있다. 같은 높이를 가지는 연속하는 열들을 선택한다. 그리고 선택한 연속된 열 중 처음 열과 가장 끝 열을 제외한 모든 열의 높이를 1씩 높인다. 이 연산을 사용해서 제단을 만들어 나갈 수 있다. 이 연산을 잘 생각해 본다면 두가지 통찰을 얻을 수 있다. 1. 첫 번째 제단과 마지막 열의 높이는 0이다. 2. 인접한 두 열의 높이차는 최대 1이다. 이..
문제 링크 https://www.acmicpc.net/problem/1637 문제 요약 정수가 여러개 모여있는 정수더미가 있다. 이 때 정수더미 안에서 홀수개 들어있는 특정 정수를 찾는 문제다. 홀수개 들어있는 정수의 수는 최대 한개이며 없을수도 있다. 문제 풀이 이 문제는 정수가 직접 주어지는게 아니라 정수더미 안에 들어있는 수들의 규칙이 주어지고 이를 통해 홀수개 들어있는 정수를 찾아야 하기 때문에 단순 시뮬레이션으로는 풀수가 없다. 그렇다면 어떻게 접근해야 할까? 우선 예제의 수들을 한번 직접 계산해보자. 직접 계산해 본다면 숫자 4가 3개 들어있어서 답이 됨을 알 수 있다. 이것만으로 일정한 규칙을 찾을수가 없다. 하지만 이들 수의 누적합을 계산해 본다면 특정 규칙을 찾을 수 있다. 위 표를 잘 ..
MO's algorithm은 온라인으로 풀기 힘든 쿼리 문제를 오프라인으로 쉽게 풀 수 있게 해주는 알고리즘이다. MO's algorithm은 쿼리를 정렬한 뒤 정렬된 순서대로 처리를 한다. 이론은 이게 끝이다. 이론만 들어서는 아마 문제에 어떻게 적용해야 할 지 감이 안올것이다. 그럼 연습문제를 풀면서 MO's algorithm을 익혀보도록 하자. 연습문제는 https://www.acmicpc.net/problem/13547에서 풀 수 있다. 구간에 존재하는 서로 다른 수의 개수연습 문제는 아래와 같다. 자연수로 이루어진 \(A_1,\ A_2,\ A_3,\ ...\ ,\ A_{N-1},\ A_{N}\)시퀀스가 있다. 이 때 다음 쿼리를 처리해야 한다.1. \(x,\ y\ (1 \le x \le y \l..
문제 링크 https://www.acmicpc.net/problem/2365 문제 요약 \(N*N\)행렬의 각 열들의 합과 각 행들의 합이 주어졌을 때 원본 행렬을 복구하는 문제다. 하지만 아무렇게나 복구하는것이 아니라 행렬에 써져있는 숫자의 최댓값이 최소가 되도록 하고 싶다. 이 때 행렬을 복구한 뒤 출력한다. 문제 풀이 이 문제는 https://www.acmicpc.net/problem/1960와 상당히 유사한 문제다. 먼저 이 문제를 풀어보는것을 권장한다. 이 문제의 풀이를 알고 있다는 전제조건 하에 풀이를 서술하려 한다. 이 문제의 풀이는 링크에서 볼 수 있다. 이 문제에서 달라진 점은 각 행렬에 들어갈 수 있는 값이 0또는 1이 아니라 내가 정할 수 있다는 점이다. 만약 내가 원본 행렬에 존재하..
문제 링크 https://www.acmicpc.net/problem/1960 문제 요약 \(N*N\)행렬의 각 열들의 합과 각 행들의 합이 주어졌을 때 원본 행렬을 복구해 출력하는 문제다. 원본 행렬이 가질 수 있는 값은 0또는 1이다. 물론 만들지 못하는 경우도 주어질 수 있으며 이때는 -1을 출력한다. 문제 풀이 이 문제는 전형적인 네트워크 플로우로 문제다.(그리디로도 해결이 가능하다고 한다.) 모델링 또한 너무 간단하다. 우선 왼쪽에는 각 행들을 대표할 수 있는 정점들을 두고 오른쪽에는 각 열들을 대표할 수 있는 정점들을 둔다. 그리고 소스와 왼쪽 정점들을, 싱크와 오른쪽 정점들을 연결해준다. 각각의 \(capacity\)는 행들의 합과 열들의 합으로 설정해 준다. 그 뒤 행들을 대표하는 정점들과 ..
원소들을 효율적으로 관리해야할 일이 있을때 우리는 어떤 전략을 선택해야할까? 원소들을 효율적으로 관리하는 방법은 여러가지가 있다. 이번에는 그 중 하나인 Sqrt Decomposition에 대해 알아보도록 하자. Sqrt Decomposition에서 Sqrt는 Square root의 약자다. 이를 우리나라 말로 번역하자면 평방분할이라고 한다. 하지만 의미적으로 별로 와닿지 않는다고 생각하기 때문에 Sqrt Decomposition이라고 하겠다. 연속적인 원소들을 하나의 묶음으로Sqrt Decomposition의 기본 아이디어는 정말 간단하다. 연속적인 원소들을 하나의 묶음으로 생각하자는 것이다. 이 때 한 묶음의 크기는 보통 \(\sqrt N\)으로 잡는다.(그래서 Square root라는 이름이 붙은..
문제 링크 https://www.acmicpc.net/problem/6241 문제 요약 \(N\)마리의 소와 \(F\)개의 음식, \(D\)개의 음료가 주어진다. 각각의 소들은 식성이 다 다르기 때문에 좋아하는 음료, 음식들이 전부 다 다르다. 소들은 자신이 좋아하는 음식들 중 한개와 자신이 좋아하는 음료들 중 한개를 동시에 먹을 때 행복하다고 느낀다. 모든 음식과 음료들은 한 소에게만 나눠줄 수 있을 때 행복한 소의 수를 최대로 만드는 문제다. 문제 풀이 얼핏 보면 이분 매칭과 흡사해 보일 수 있다. 하지만 이 문제는 소에게 음료와 음식을 동시에 할당해 줘야 하기때문에 이분 매칭으로는 풀 수 없다. 그렇다면 조금은 다른 풀이를 생각해야 한다. 이 문제에서는 소를 정 중앙에 두고 왼쪽에는 음식, 오른쪽에..
문제 링크 https://www.acmicpc.net/problem/11670 문제 요약 \(N\)개의 줄에 걸쳐 \(A_i\)와 \(B_i\)가 주어진다. 이 때 각각의 \(A_i\)와 \(B_i\)에 대해 \(+,-,*\)중 하나를 선택해서 나온 결과를 모두 다르게 하고 싶다. 이렇게 연산자들을 선택하는게 가능한지, 가능하다면 어떻게 선택해야 하는지 출력하는 문제다. 문제 풀이 \(N\)이 최대 \(2,500\)개가 들어오기 때문에 완전탐색으로는 불가능하다. 우리는 모든 계산의 결과가 유니크해야하다는 것에 주목할 필요가 있다. \(A_i\)와 \(B_i\)의 쌍을 하나의 정점으로 생각하고 \(+,-,*\)한 결과들에 간선을 연결해 보자. 예제 입력을 그래프로 모델링하면 아래와 같은 결과가 나온다. 그..
문제 링크 https://www.acmicpc.net/problem/13344 문제 요약 수식이 주어졌을 때 주어진 수식들이 일관성이 있는지 혹은 모순이 있는지 찾아내는 문제다. 문제 풀이 수식은 크게 두가지 종류가 존재한다. 1. \(u = v\) : \(u\)와 \(v\)는 같다 2. \(u \gt v\) : \(u\)가 \(v\)보다 크다 만약 1번 수식이 없다고 생각을 해보자. 1번 수식이 없고 2번 수식만 있을 때 주어진 수식들이 일관성이 있는지 없는지 어떻게 판단을 할 수 있을까? \(u\)와 \(v\)가 나오고 \(\gt\)가 화살표 처럼 생겼으므로 \(u\)에서 \(v\)로 향하는 방향 그래프를 만들어 보자. 이 때 만약 \(Cycle\)이 있으면 어떻게 될까? \(Cycle\)이 존재하도..
