Hyun's_Devlog

https://www.acmicpc.net/problem/1849

세그먼트 트리 문제다.

풀이

숫자 i 앞에 i보다 큰 숫자의 개수는 작은 수부터 탐색했을 때, 앞에 주어진 빈칸의 개수로 접근 가능하다. 트리의 리프가 1인 구간합 트리를 생성하여 해당 숫자가 몇 번째 숫자인지 뽑아내면 문제를 해결할 수 있게 된다. 수열 [2 4 3 1]의 경우로 시나리오를 작성하면 다음과 같다.

입력 예제 : 3 0 1 0

수열의 구간중 남아있는 공간의 수를 나타내는 세그먼트 트리 생성.

트리 초기화 및 입력값 저장. 순번으로 다루기 편하게 입력값을 +1 처리하여 저장한다.

가장 먼저 1의 인덱스를 찾는다. 남아 있는 공간 중 네 번째 공간의 인덱스를 탐색. 3이 반환된다. 해당 인덱스에 1 저장.

다음 탐색을 위해 방문했던 노드는 -1 처리한다.

2의 인덱스 탐색, 현재 남아있는 공간중 첫 번째 공간의 인덱스로 0이 반환된다.

3의 인덱스를 탐색, 현재 남아있는 공간중 두 번째 공간의 인덱스인 2가 반환된다

마지막으로 4의 인덱스 탐색. 남아있는 공간중 첫 번째 공간, 즉 유일하게 남아있는 공간의 인덱스를 반환하여 수열을 완성하면 된다.

정답 코드

https://www.acmicpc.net/problem/1517

제목은 버블 소트지만 크게 세그먼트트리 또는 머지 소트로 접근하는 문제다. 세그먼트 트리를 공부하기 위해 세그먼트 트리로 접근했다.

풀이

버블 소트는 자신보다 뒷순번의 숫자 중 더 작은 숫자와 swap이 일어나게 된다. 즉 자신보다 뒷순번의 숫자 중 더 작은 수의 개수를 세그먼트 트리를 통해 구해내고 그 수의 합을 반환하면 문제에서 요구하는 swap이 일어나는 수를 구할 수 있다는 얘기다.

입력된 수열에 숫자와 인덱스가 담긴 튜플배열을 생성하여 숫자 기준 오름차순으로 정렬한다. 0으로 초기화된 세그먼트트리를 생성. 이후 (숫자, 인덱스) 튜플이 담긴 배열을 순회하면서 (인덱스 ~ N-1) 구간의 숫자를 정답에 더해준 뒤 해당 구간에 +1 갱신해 준다. 수열을 모두 돌게 되면 자연스럽게 자신보다 뒷구간에 더 작은 숫자들의 개수를 계산할 수 있게 된다.

예제 [3,2,1]을 기준으로 설명하면 다음과 같다.

구간 합 세그먼트 트리 생성. (숫자, 인덱스) 튜플을 숫자 기준 오름차순으로 정렬한다.

1의 인덱스는 2였다. 2부터 마지막 인덱스 2 즉 2~2 구간의 값을 조회. 0을 정답에 추가.

이후 들어올 구간합을 계산하기 위해 2-2에 +1 갱신작업을 한다.

다음 숫자의 인덱스는 1이다. 1~2구간의 값을 조회. 1이 반환되며 해당 결과를 정답에 저장. 

이후 마찬가지로 1-1 구간에 +1 갱신 작업을 한다.

마지막 3의 인덱스는 0이다. 0~2 구간의 값을 조회. 3보다 뒤에 있으면서 작은 숫자들의 개수는 2이다. 정답에 저장한다.

0-0 구간에 +1 갱신. 정답에는 0 + 1 + 2 즉 3이 담겨있고 해당 값이 swap이 일어난 횟수이다.

정답 코드

https://www.acmicpc.net/problem/1572

세그먼트 트리 문제다.

풀이

[1321] 군인 문제와 [2243] 사탕상자 문제와 마찬가지로 최근 K개의 숫자 중 (K+1)/2 번째 숫자에 접근하면 된다. 0부터 65536의 숫자가 몇 개가 담겨있는지를 표현하는 구간 합 세그먼트트리를 생성. 이후 N개의 입력을 받으면서 세그먼트트리에 갱신해 준 뒤, 원소가 K개 이상일 때부터 (K+1)/2 번째로 작은 숫자를 계산하면 정답을 구할 수 있다.

여기서 중요한 점은 최근 K개까지가 범위이므로 중앙값을 반환할 때마다 (수열의 크기 - K) 번째 숫자를 세그먼트트리에서 하나씩 제거해주어야 한다.

정답 코드

https://www.youtube.com/watch?v=nqNLrpMQrU8 

유튜브 채널 iOS Academy에서 발견한 영상. lazy sequence에 관련된 영상이다. 재밌게 시청해서 가져왔다. 

lazy

우선 lazy 키워드에 대한 간략한 설명을 하자면 말 그대로 lazy하게 변수를 할당하는 키워드이다. 대다수의 언어가 그렇겠지만 swift에서 변수, 상수의 경우 우선적으로 초기화가 이루어져야지만 컴파일이 완료된다. 하지만 lazy의 경우, 해당 변수의 초기화가 완료되었다고 판단하고 컴파일이 우선적으로 이루어진다. 이후 lazy로 생성된 변수에 접근하게 될 경우에 뒤늦게 초기화가 이루어지게 된다. 해당 부분의 경우 cs193p swift강의를 보면서 처음 마주했는데, 사실 당시에는 필요성이 크게 와닿지 않았다. 

lazy sequence

앞선 얘기는 lazy stored property에 관련된 이야기였고 이번글은 lazy sequence에 관련된 이야기를 하려 한다. swift에서 collection 타입의 자료들을 다루게 되면 가장 많이 다루게 되는 부분이 고차함수가 아닐까 싶다. rest-api를 사용할 때 반환된 요청을 map() 혹은 filter()와 같은 고차함수들을 통해 파싱을 하게 되는데, 이때 입력되는 자료의 수가 많다면 성능 저하가 일어나기 쉬울 것이다. 해당 자료들을 모두 사용하게 된다면 어쩔 수 없으나 대다수의 경우 해당 자료에서 일부분의 자료만 뽑아내어 사용자에게 보여주는 일이 많다. 여기서 lazy sequence를 통해 어느 정도의 성능개선을 이루어낼 수 있다.

0부터 1,000,000이 담긴 배열을 생성, map() 메소드를 통해 원소값들을 가공한 뒤 필요한 자료를 호출한 모습이다. 1,000,001 개의 원소를 탐색, 마지막으로 threeTimesArr에 결과를 저장하는 과정이 더해져 1,000,002번의 자료 접근이 일어나게 된다. 곱셈이라는 단순한 작업이었지만 처리해야 할 자료의 수가 많고 더욱 복잡한 자료의 연산이 일어난다면 성능 저하를 유발하게 된다.

이번엔 lazy를 이용한 연산이다. 앞서 말했듯이 lazy는 해당 자료에 접근이 일어날 경우에 초기화가 이루어지게 된다. lazy를 통한 map()메소드는 마찬가지로 자료의 접근이 일어날 때에 필요한 부분에서 연산이 일어나게 되고, 자료를 반환하는 모습을 볼 수 있다. 따라서 arr [50]의 자료접근, threeTimesArr[50]에 자료를 저장하는 과정 총 두 번의 접근을 통해 값을 출력하는 모습을 보여준다. 개발과정에서 이러한 lazy sequence를 통해 성능개선을 이루어낼 수 있지 않을까 싶다.

이상 lazy 키워드를 통한 성능개선에 관련된 이야기였으며 아마도 iOS 개발을 하면서 정말 유용하게 사용할 수 있는 미세먼지팁이 되지 않을까 싶다. 혹시나 틀린 정보를 적었다면 성장중인 아기개발자를 위해 따끔한 지적 부탁드립니다.

https://www.acmicpc.net/problem/1321

세그먼트트리 문제다. 바로 이전 문제인 [2243] 사탕상자 문제와 동일한 풀이로 접근하면 된다.

풀이

N개의 부대에 속한 군인 수를 저장하는 구간 합 세그먼트트리를 생성한다. 이후 i번째 군인의 부대를 호출할 때, 현재 구간의 군인 수가 i보다 크다면 좌측노드에서 i번째 군인 탐색. 현재 구간의 군인 수가 i보다 적다면 (i - 좌측구간 군인수) 번째 군인을 우측노드에서 탐색한다. 없는 군인을 탐색하는 경우는 주어지지 않으므로 리프노드에 도달할 경우에 해당 노드의 인덱스를 반환하면 된다.

정답 코드

https://www.acmicpc.net/problem/2243

세그먼트트리 문제다. 접근방법이 떠오르지 않아 풀이를 찾아보았다.

풀이

1번 맛부터 1,000,000번 맛에 해당하는 사탕의 개수를 표현하는 세그먼트트리를 생성한다. 최대합 세그먼트 트리를 구현하면 된다.

고민할 부분은 문제의 요점인 i번째 순번의 사탕을 찾는 것인데, 해당 부분도 재귀호출을 통해 접근해야 한다. 부모노드부터 시작하여 좌측자식으로 탐색할지 우측자식으로 탐색할지 결정해야 한다. 만일 좌측노드의 값이 i이상이라면, 즉 좌측 노드에서 i번째 사탕을 찾을 수 있다면 그대로 좌측노드로 탐색을 시작하면 되고, 만일 좌측노드의 값이 i 보다 작다면, 즉 좌측노드에서 i번째 사탕을 찾을 수 없다면 우측노드로 탐색을 시도해야 하는데, 우측노드를 탐색한다는 뜻은 (i - 좌측노드의 값) 번째 사탕을 찾는다는 의미이다. 문제에서 현재 없는 사탕을 찾는 경우는 주어지지 않으므로 리프노드에 도달할 때까지 찾아야 할 사탕의 순번을 조절해서 탐색을 시도하면 된다.

예제를 기준으로 설명하면 다음과 같다.

0으로 초기화된 세그먼트 트리 생성 예제의 경우 큰 번호의 사탕이 나오지 않았기에 6번까지의 범위만 그렸다.

1번 사탕 2개 추가. 3번 사탕 3개 추가.

두 번째로 맛있는 사탕을 찾는다. 1번이 두 개 있기에 1번을 반환. 방문하는 모든 좌측노드가 2 이상이기에 1번 사탕까지 바로 접근. 사탕을 빼내는 작업이기에 방문한 리프노드에 도달할 때까지 방문한 모든 노드는 1만큼 차감해 준다.

이번에도 두 번째로 맛있는 사탕을 탐색, 0-3 범위에 도달할 때까지는 노드 값이 4이기에 좌측 노드 탐색.

이후에는 좌측 노드의 값이 1이므로 해당 노드에는 두 번째로 맛있는 사탕을 찾을 수 없다. 따라서 우측 노드 탐색 수행.

우측에서는 전체 범위에서 두 번째로 맛있는 사탕을 찾기 위해선 해당 범위에서 첫 번째로 맛있는 사탕을 찾아야 하기에 순번을 1로 변경하여 탐색을 진행하면 된다. 마찬가지로 방문했던 노드는 1 차감한다.

1번 사탕의 개수 변동. 마찬가지로 리프노드를 만날 때까지 변경 값을 반영하면 된다.

마지막으로 두번째로 맛있는 사탕 탐색. 위에서 탐색한 방법과 같은 방법으로 탐색 후 3번을 반환 후 방문했던 노드의 값 1을 차감한다.

정답 코드

https://www.acmicpc.net/problem/3745

최장증가 부분수열(LIS) 문제다. DP로 푸는 방법, 이분탐색을 이용하는 방법, 세그먼트 트리를 이용한 방법 총 세 가지 방법이 있다. 

지난번에는 이분탐색을 통해 문제를 풀어보았고 현재 세그먼트 트리를 공부 중이라, 이번에는 세그먼트 트리를 이용하여 접근해 보았다. 이분탐색 풀이와 마찬가지로 O(N*logN)의 복잡도로 풀 수 있다.

풀이

해당범위의 LIS의 길이를 담은 구간 최댓값 세그먼트 트리를 생성한다. 초기값은 0이다.

주가를 입력받을 때, (가격, 인덱스) 튜플형태로 입력받은 뒤, 주가를 기준으로 오름차순, 주가가 같다면 인덱스 기준 내림차순으로 정렬을 한다. 이후 정렬된 주가정보를 순차 탐색하면서 세그먼트 트리를 갱신해 주면 된다.

원리는 다음과 같다. 주가가 작은 값부터 탐색을 시작하기에 들어오는 정보 (주가, 인덱스)는 곧 0부터 인덱스 i까지의 최장증가 부분수열의 길이이며, 해당 수열에 입력된 주가 값을 덧붙이면(+1) 새로운 최장증가부분수열의 길이를 구할 수 있는 것이다.

예제 [5,2,1,4,5,3]을 기준으로 세그먼트를 완성시켜 보자.

가장 먼저 0으로 초기화된 세그먼트트리와 (값, 인덱스) 튜플형태를 정렬한 모습이다.

가장 먼저 인덱스 0-2 값을 조회, 길이가 0이고 여기에 배열의 가장 최솟값인 1을 붙여 길이가 1인 LIS길이가 생성된다. 해당 범위인 0-2까지의 LIS길이가 1이 되는 것이다. 따라서 0-2 범위를 1로 갱신하게 된다.

다음 값은 2이며 범위 0-1에 해당하는 값을 참고, 해당 수열에 2를 붙여 갱신하게 된다. 다음과 같은 작업을 반복하면 된다.

0-5 범위의 최장수열에 3을 붙여 길이 2인 최장수열이 생성된다. 해당 범위의 트리에 값 갱신.

0-3 범위 조회 후 갱신

0-4 범위 조회 후 갱신

가장 마지막으로 0-0 범위 조회 후 갱신

다음과 같은 과정으로 트리가 완성되며 문제에서 요구하는 전체 범위의 최장증가 부분수열의 길이는 루트 노드에 담겨있게 된다.

정답 코드

스위프트의 경우 입력 부분에서 제약이 생긴다. 라인이 분리되어서 주가가 입력되는 경우가 들어오게 되는데, 기본적인 입력으로는 해결하기 까다로워 보였다. 결국 해당 문제 질문 게시판에서 발견한 honghoker님의 글을 참고해서 입력을 처리하였다.

https://www.acmicpc.net/problem/12837

세그먼트트리 문제다.

풀이

구간합 문제와 동일하게 접근했으나 문제에서 오해하기 쉬운 요소가 있어 오답을 받았다. 1 쿼리의 경우 해당 구간의 정보를 변경하는 것으로 이해했으나, 그게 아닌 입력 값만큼 추가만 해주면 된다.

기본의 구간 합 문제의 경우 바꾸려는 인덱스가 포함된 범위를 탐색하면서 변경할 값과 기존값의 차를 트리에 반영했다면, 이번에는 새로 입력되는 값을 범위 내에 트리에 더해주기만 하면 된다.

정답 코드