산타는 없다

설명 분할정복법은 큰 문제를 더 이상 나눌 수 없을 때까지 분할한 후 다시 합치면서 문제를 해결하는 방법입니다. 풀이 순서 1. 큰 문제를 둘 이상의 작은 문제로 분할한다. 2. 더 작은 문제로 나눌 수 없을때까지 분할한다. 3. 더이상 작은 문제로 나눌수 없다면 다시 합치면서 문제를 해결한다. 이렇게 되어있는 풀이 순서를 제 나름대로 제귀 함수를 쓴다 가정했을 때 풀이순서를 1. Input값을 둘 이상의 범위로 나눈다. 2. 나눈 범위를 제귀 함수의 매개변수로 넣어 반복 실행한다. 3. 입력받은 범위가 0이거나 1일때 반환처리를 한다. 4. 반환받은 값으로 문제를 해결하고 반환한다. 값들이 반환되면서 해답이 나오게 된다. 위와 같이 정리하였습니다. 응용 알고리즘 퀵 정렬 병합 정렬 이분 탐색 쿼드 트리..

문제 원문 조건 시간 제한 : 2초 메모리 제한 : 512 MB 문제 어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다. 예를 들어, 이 나라에..

본 게시글은 NAVER Engineering의 [ Search Reliability Engineering (부제: 지진에도 흔들리지 않는 네이버 검색시스템) ] 을 보고 정리하였습니다. 1. 들어가며 SRE란? 글로벌 스케일의 서비스를 제공하면서 어떻게 하면 시스템의 신뢰성을 보장할지 고민하는 기술 분야이자 방법론, 문화 보통의 SRE는 Site Reliability Engineering이지만 네이버 내부에서는 Site가 아닌 Search로 바꿔서 부름 네이버 검색시스템의 목표 많은 사용자가 동시에 검색어를 입력해도 서비스에 문제가 없어야 한다. - 대용량 처리 (High Throughput) 네이버 검색창에 검색어를 입력하면 1초안에는 결과가 나와야 한다. - 짧은 대기시간 (Low Latency) →..

문제 원문 조건 시간 제한 : 1초 메모리 제한 : 256 MB 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 예제 풀이 동적계획법을 활용하여 푸는 문제입니다. 가장 공통인 문자열의 길이를 구하는 문제이므로 처음엔 DP 배열을 1차원 배열로 사용하여 문자가 일치할때 : DP[i] = DP[i] + 1 문자가..

문제 원문 조건 시간 제한 : 1초 메모리 제한 : 128 MB 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 입력 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 출력 첫째 줄에 답을 출력한다. 예제 풀이 양수가 나오면 더하고 음수가 나오면 초기화 하는 그리드 알고리즘으..

물건을 최대 K 만큼 버틸 수 있는 배낭에 가장 가치가 높도록 물건을 구성했을때 가치의 최댓값을 구하는 알고리즘입니다. 그리드 알고리즘으론 정확한 답을 찾을 수 없어 동적 계획법으로 풀이하여야 합니다. 그리드 알고리즘으로 풀이를 할 경우엔 가장 높은 가치 순으로 탐색을 하였을 때 결과값 보다 더 높은 경우가 발생할 가능성이 있기 때문입니다. 따라서 동적 계획법으로 풀어야하는데 동적 계획법의 진행은 i번째 물건을 j무게까지 담을 수 있을 때 최댓값을 넣어 가면서 진행합니다. 그렇게 진행하면 물건이 중복되지 않고 무게를 갱신해 가면서 진행할 수 있습니다. 문제 출처 - 백준 12865번 평범한 배낭 무게 가치 6 13 4 8 3 6 5 12 위 물건들을 최대 무게 7 까지 버틸 수 있는 가방에 넣을 때 DP..

문제 원문 문제 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다. 또한 위쪽 가운데 위치한 3x3 ..

문제 원문 문제 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다. 출력 첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력..