Hyun's_Devlog

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

세그먼트 트리 문제다.

풀이

i번째 나무의 좌표 A에 대한 비용은 다음과 같이 정리가 가능하다. 

|(A -[i-1] 번 나무 좌표)| + |(A - [i-2] 번 나무좌표)| +... + |(A - [i-i] 번 나무 좌표)|
->  | A*i - ([i-1]번 나무 좌표 + [i-2] 번 나무좌표 +... + [i-i] 번 나무좌표) |

즉 해당 부분을 여태 심어진 나무의 갯수와 좌표의 누적값을 통해 계산이 가능하다는 것이다. 따라서 0부터 199,999 좌표의 나무개수와 해당 구간의 누적 좌표값을 표현하는 세그먼트 트리를 생성하여 다음과 같이 계산이 가능해진다.

좌측 비용 = (A보다 좌측에 있는 나무의 갯수 * A) - (A보다 좌측 좌표에 심어진 나무의 거리(좌표) 총합)
우측 비용 = ((A보다 우측 좌표에 심어진 나무의 거리(좌표) 총합) - (A보다 우측에 있는 나무의 개수 * A)
A좌표에 나무를 심는 비용 = 좌측비용 + 우측비용

매 입력마다 해당 좌표의 비용을 구하여 계산한 뒤, 다음 나무의 비용 계산을 위해 나무의 갯수를 갱신해 주면 값을 구할 수 있다.

정답 코드

세그먼트 트리의 활용은 정말 다양한 것 같다.

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

세그먼트트리로 접근한 문제다. 

풀이

구간 최솟값의 인덱스를 반환하는 세그먼트트리를 생성한다. 0~N-1 범위의 최소 인덱스를 찾은 뒤, 해당 인덱스를 사용하여 히스토그램의 넓이를 계산, 이후 해당 [0 ~ 최솟값인덱스-1] 범위와 [최솟값 인덱스+1 ~ N-1] 범위의 히스토그램 넓이를 계산해 나가면 된다. 

예제 [2,1,4,5,1,3,3]을 기준으로 다음과 같이 동작한다.

최솟값 인덱스 세그먼트트리 생성

가장 먼저 0~6 전체 범위의 히스토그램 영역을 탐색한다.

1번 인덱스가 반환되며 해당 블록의 높이인 1과 밑변에 해당하는 0~6 범위(6-0+1)를 곱해 넓이를 계산한다.

이후 해당 최소값 인덱스를 기준으로 좌, 우 영역의 넓이를 계산해 나가면 된다.

좌측의 경우 2*1 = 2가 반환되며 우측의 경우 1*5 = 5가 계산된다. 

이후 좌측의 경우 범위의 시작값과 마지막값이 동일하므로 종료.

우측의 경우 아직 탐색할 범위가 남았으므로 좌측과 우측을 계산한다.

2~3에 해당하는 넓이 4*2 = 8 계산. 5~6에 해당하는 넓이 3*2 = 6 계산.

남은 범위 계산을 위해 재귀호출을 이어간다.

3~3 범위 1*5 = 5 계산. 6~6 범위 3*1 = 3 계산.

더 이상 탐색할 범위가 없으므로 앞서 나온 모든 값들 중 최대값 8을 출력하면 정답이다.

정답 코드

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을 차감한다.

정답 코드