대부분의 프로그래밍 언어에서 데이터 타입을 확인할 수 있는 연산자를 제공한다. 자바스크립트도 데이터 타입을 확인할 수 있는 \(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 ..
이 글은 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 ..
문제 링크 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라는 이름이 붙은..
- Total
- Today
- Yesterday
- Binary Search
- max flow
- Sqrt Decomposition
- Data Structure
- brute force
- bipartite matching
- disjoint set
- DP
- greedy
- graph
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |