레벨업 일지

문제 18222번: 투에-모스 문자열 (acmicpc.net) 18222번: 투에-모스 문자열 0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다. X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. X의 뒤에 www.acmicpc.net 풀이 반복되는 조건을 어떻게 처리할지가 관건인 문제 문제 조건을 다시 확인해 보자 X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. X의 뒤에 X'를 붙인 문자열을 X로 다시 정의한다. 2~3의 과정을 무한히 반복한다. 문자열 최대 길이 10^18를 일일히 확인하려면 TLE 가 뜬다. 따라서 반복되는 조건을 이용하여 찾아야 한..

문제 https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 풀이 현재 위치 i 에서 0..i-1 중에 자신의 실력보다 낮은 개수를 센 다음, 차를 구하는 문제. 분할 정복으로 정렬해서 O(N log N) 풀이하였다. 알고리즘은 다음과 같다. 1. 분할 정복 소트 기법을 사용한다. 2. 두 배열을 병합할때 RIght 배열 원소를 삽입 할때 자기 Left 배열에서 현재숫자보다 낮은 개수를 누적합한다. 3. 자기 자신의 인덱스 - 자신 실력보다 낮은..