2021/01
문제 N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 만약 리스트의 길이가 100보다 작거나 같으면, 연속된 수를 첫째 줄에 공백으로 구분하여 출력한다. 만약 길이가 100보다 크거나 그러한 수열이 없을 때는 -1을 출력한다. 예제 입력 1 18 2예제 출력 1 5 6 7 나의 풀이 처음에 투 포인터 기법으로 접근해보았지만 알고보니 수학문제 였던 문제입니다. 연속된 L개의 숫자들로 더해진 합은 다음과 같은 수식으로 나타낼 수 있습니다. N = (x+1) + (..
이번 글에서는 Apache가 제공하는 mod_proxy 모듈을 사용해 리버스 프록시를 구현해보려고 합니다. 프록시에 대해서 모든 것을 설명하기에는 벅차기 때문에 이번 글에서는 간단히 프록시가 무엇이고, 포워드 프록시와 리버스 프록시의 차이점에 대해서만 설명해보려고 합니다. 프록시란? 프록시 서버는 서버와 클라이언트 사이에 위치하여 요청이나 응답을 중계하는 역할을 하는 서버라고 할 수 있습니다. 다시 말하면 클라이언트에서 보내는 요청을 프록시 서버에서 대신 처리하게끔하여 일종의 대리인이 될 수도 있습니다. 즉, 아래 그림과 같이 클라이언트에서 요청을 보내면 프록시 서버가 중간에 위치하여 요청에 대하여 검증을 한다거나 부가적인 작업을 수행할 수 있게됩니다. 포워드 프록시? 리버스 프록시? 어찌됐든 프록시 서..
이번 글에서는 HTTPS가 무엇이고, Apache에서 HTTPS를 구현하기 위해서 동작 과정과 인증서를 생성하고 설정하는 방법에 대하여 살펴보고자 합니다. HTTPS란? HTTPS란, HTTP over TLS, HTTP over SSL, HTTP Secure라고 불리며, 기존 HTTP가 평문으로 전달되는 통신 과정에서 안전하지 못한 문제점을 HTTP의 데이터를 SSL/TLS로 암호화하여 안전한 통신을 보장하기 위해 사용되는 프로토콜입니다. 또한, HTTP의 경우 80번 포트를 사용하는반면 HTTPS는 443번 포트를 사용하게 됩니다. HTTPS의 동작 원리 HTTPS가 이뤄지는 과정, 즉 SSL Handshake는 크게 3단계로 설명할 수 있습니다. Hello 교환 인증서 교환 키 교환 이 과정을 그림으..
문제 세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다. N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수이고, C는 10^9보다 작거나 같은 음이아닌 정수이고. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다. 출력 첫째 줄에 가방에 넣는 방법의 수를 출력한다. 예제 입력 1 2 1 1 1예제 출력 1 3 나의 풀이 이 문제는 meet in the middle 알고리즘을 사용하여 풀이를 해야하는 문제였습니다. meet in the middle은 적당한 N이 주어질 때 완전탐색을 해야하는 경우 시간복잡도가 O(2^N)이 나오는 것을 반으..
문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. 입력 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 ..
문제 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,..
문제 재귀 호출만 생각하면 신이 난다! 아닌가요? 다음과 같은 재귀함수 w(a, b, c)가 있다. if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15) a, b, c가 주어졌을 때, w(a, b, c)를 출력하..
문제 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액..
문제 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000) 출력 문제의 조건을 만족하는 쌍의 개수를 출력한다. 예제 입력 1 9 5 12 7 10 9 1 2 3 11 13예제 출력 1 3 나의 풀이 해당 문제의 풀이는 이진탐색을 사용하는 방법과 투 포인터 기법을 사용하는 두 가지의 ..