1. 좌표를 압축하는 방법좌표를 압축하는 경우가령 이런 경우가 있을 수 있습니다. 어떤 문제를 푸는데, 수의 값은 필요가 없는데 수의 대소 관계를 알아야 하는 상황이 왔다고 생각해 보죠. 이런 경우가 사실 많이 나오는 경우는 아닌데 문제를 풀다 보면 종종 나오기는 합니다. 특히 이런 문제들이 굉장히 넓은 수의 범위를 들고 나오면 더욱 난감해지죠.그래서 생겨난 기법이 바로 좌표 압축(Coordinate Compression)입니다. 좌표의 집합 $X$를 압축한 결과는 다음과 같아야 합니다.$X$를 좌표 압축한 결과인 $X'$은 $X$에 한 번 이상 등장한 모든 원소를 중복 없이 포함해야 한다.그러니까 이게 무슨 말이냐면, 1차원 좌표계 상에 다음과 같은 좌표들이 있다고 가정합시다.$$X=\{-2, 5, 9..

1. 개괄어디에 쓰는 기법일까수치 해석(Numeric Analysis)이라는 기법이 있습니다. 수치 해석은, 직접적으로 풀기 어려운 수학 문제를 근사의 방식을 이용해 풀어내는 기법으로, 단순히 이러한 방식으로 풀어내는 방법뿐 아니라 이 방식의 안정성과 오차 범위 등까지 폭넓게 연구하는 전산학의 한 분야입니다. 주로 공학, 과학, 금융공학 등에 사용되는 기법이죠.수치 해석은 PS를 비롯한 문제에 깊게 나오는 영역은 아닙니다. 다만, 수치 해석의 기저를 담당하는 알고리즘들은 PS에서 밥 먹듯이 나오는 영역이다 보니 한 번 이상은 다루고 가면 좋습니다.수치 해석의 수학적 비유자, 다음의 식을 생각해 봅시다.$$f\left(x\right)=x^2$$이때, $y=f\left(x\right)$라고 쓰고 이를 좌표평..

1. 덧셈에 알고리즘이?여러 개를 합하는 과정살다 보면 제시된 데이터 시트 내에 있는 값들 중 일부를 갖고 연산해야 할 때가 있습니다. 예를 들어, 다음과 같은 문제를 생각해 보죠. 총 인원이 30명인 학급의 수학 시험 성적에 대한 데이터가 있다. 상위 10명의 학생들의 수학 시험 성적의 평균을 구하시오. 이런 문제를 많이 보셨을 텐데요. 우리는 프로그래밍 기법을 배우는 입장이므로, 좀 더 확장해보자면 총 인원이 $n$명인 학급의 수학 시험 성적에 대한 데이터가 있다. $a$등부터 $b$등까지 학생들의 수학 시험 성적의 평균을 구하시오. 와 같은 문제가 됩니다. 얼핏 보기에는 ‘정렬 → 탐색 → 또 탐색 → 인원 수 구하고 → 성적 합해서 → 나누면 되는 거 아닌가?’하는 생각이 들 수 있습니다. 사실..

1. 어떠한 것들을 다루는가빈출 주제는 아닙니다사실 이 파트를 써야 하나, 고민을 많이 했습니다. 하지만, PS에서 정수론 문제가 가끔 나와 사람들을 골때리게 하는 경우는 왕왕 존재합니다. 그래서 "PS에 자주 나오지는 않지만, 그래도 알아놓으면 훌륭하게 쓸 가치가 있는 주제들"을 위주로 골라 이번 내용에 담았습니다.참고로 게시 순서는 중요도와 일절 무관합니다. 다만, 상위의 내용을 알아야 하위의 내용을 알 수 있는 연계 관계는 일부 있으니 참고하시면 될 듯합니다.2. 베주 항등식꼭 알아두어야 할 항등식베주 항등식(Bézout’s Identity)이라는 항등식이 있습니다. 다음과 같습니다.$$ax+by=d$$얼핏 보기에 별 특징이 없는 이 항등식은, 사실 재미있는 정보 몇 가지를 내포하고 있는데 다음과 ..

1. 정수론에서 합동정수론에서 합동?흔히들 "합동"이라고 한다면 도형의 합동을 제일 먼저 떠올릴 듯 합니다. 하지만, 정수론에서 합동이라 함은 도형의 합동과는 다소 다른 개념을 지칭합니다.정수론에서의 두 수가 합동(Congruence)이라 함은, 정확하게 다음을 의미합니다.정수 $a$, $b$, $m$에 대해, $a$와 $b$를 $m$으로 나눈 나머지가 동일한 경우, $a$는 법 $m$에 대해 $b$와 합동이라고 표현한다.식으로는 다음과 같이 표현합니다.$$m|\left(a-b\right) \Longleftrightarrow a\equiv b\left( \mathrm{mod}\, m \right)$$이때, $=$과 비슷하게 생긴 $\equiv$ 기호를 모듈러 연산자(Modulus Operator)라고 하..

1. 정수론의 기초여기서 왜 정수론이?프로그래밍과 수학의 연관성은 이미 잘 알려져 있죠. 모르는 분들은 거의 없을 뿐더러 지금까지의 프로그래밍에 대한 이야기를 읽어 보신 분이라면 매우 잘 알 것이라고 생각합니다. 그러니 이에 대한 이야기는 생략하고, 지금부터는 간략하게 "PS에서 요구하는 수학 역량의 정도"에 대해 이야기하고자 합니다.단적으로 이야기해서, 대부분의 개발자들이 반드시 통과해야 하는 코딩 테스트를 기준으로 하자면, PS에서 요구하는 수학적 역량은 중등 수학, 그러니까 고등학교 수준의 수학이라면 충분합니다. 수능 수학을 무리없이 풀어낼 수 있을 정도의 사고력을 갖추고 있다면, 거의 모든 PS 문제들을 무리없이 풀어낼 수 있습니다. 만약 공학이나 자연과학 등에서 프로그래밍을 활용한다면, Calc..

1. 개괄스위핑과 엮어서앞서 18장에서 스위핑에 대해 배운 바 있습니다. 스위핑에서 더 나아가서, 스위핑과 자주 엮여 흔히 등장하는 두 개의 알고리즘이 있습니다. 바로 "두 포인터 문제"와 "슬라이딩 윈도우 알고리즘"입니다.두 포인터와 슬라이딩 윈도우도 별도의 알고리즘이 있는 게 아니라, 이렇게 풀어야 한다는 방법론적인 이야기에 가깝습니다. PS에서도 단골마냥 등장하는 주제들이니 만큼, 이번 장에서도 훌륭한 예제들을 통해 이러한 알고리즘이 어떻게 적용되는지 알아봅시다.2. 두 포인터 - 두 용액 2470번: 두 용액https://www.acmicpc.net/problem/2470역시 스위핑 문제이 문제의 용액 개수는 총 10만 개입니다. 이 문제를 단순히 생각하고 이중 반복문을 돌렸다면, 용액의 개수가 ..

1. 개괄스위핑의 뜻Sweeping, 영어로 "쓸고 지나가는"을 나타내는 단어입니다. "전면적인", "못마땅한", "압승" 등의 별의별 해괴망측한 뜻들도 있기는 하지만 얘네는 지금 볼 게 아니니까 넘어가죠.스위핑 알고리즘이라는 건, 한쪽 방향에서 시작해서 다른 쪽 방향으로 "쓸듯이" 지나가면서 탐색하는 알고리즘을 의미합니다.특별한 자료구조가 있는 것도 아니고, 딱 한 번의 전 영역 탐색만으로 모든 답을 구할 수 있는 건 사실이지만, 어떻게 결합하느냐에 따라 난이도가 천정부지로 뛰는, 그야말로 애증의 파트이기도 합니다. 스위핑에서 가장 유명한 예제들을 통해, 어떠한 문제인지 알아보도록 합시다.2. 선 긋기 2170번: 선 긋기https://www.acmicpc.net/problem/2170배열을 만들 수는..

1. 이진수 연산의 장점CPU는 이진수를 사용한다.굉장히 당연한 이야기이지만, CPU는 이진수로 모든 일을 처리합니다. 하지만 워낙 컴퓨터가 많은 활동을 하다 보니 우리는 뭔가 자각하지는 않는 이야기입니다.사람의 입장에서 생각해 본다면, 우리는 십진수를 쓰는 게 일상화되어 있고 또 당연한 듯이 사용합니다. 일반적으로 십진수 이외의 수를 접할 때면, 이를 십진수로 바꾸고 사용하는 게 더 편리할 때가 많죠?이 이야기를 하는 건, 컴퓨터의 입장에서도 이는 결코 예외적인 사실이 아니기 때문입니다. 이진수를 다루는 컴퓨터의 입장에서는, 이진수로 수를 입력시키면 더욱 편리하게 연산을 수행할 수 있을 겁니다. 비트마스크라는 기법의 아이디어는 여기에서 출발합니다. 이진수를 사용하는 컴퓨터에게, 인간이 의식적으로 이진수..

1. 문자열에 관련된 몇 가지 용어들많이 나오지는 않지만혹시, PS 문제에서 문자열에 관한 문제를 본 경험이 있나요? 사실 이렇게 쓰고 있는 필자도 '내가 PS에서 문자열 문제를 얼마나 봤지...?'라고 생각하면 정말로 손에 꼽을 정도로 그 개수가 굉장히 적습니다. 보통 PS 문제들은 수학적인 아이디어를 위주로 사용하거든요. 보통 출력이 문자열인 경우는 문제에서 특정 형식으로 입력하는 경우가 아니면 잘 없습니다.그 이유가 무엇인지 생각해 보면, 정말 여러 가지 이유가 있겠지만, 첫째는 문자열의 특성상 구현이 다소 복잡하다는 점, 그리고 앞서 이야기한 단점이 시간적으로 제한된 PS의 환경에서 간단한 구현만을 이용하는 문제들을 위주로 내야 하다 보니 일반적으로는 PS에 출제되는 문자열 문제는 그 난이도가 다..