55일차)알고리즘 문제(점찍기),알고리즘 공부(레이지 프로파게이션 세트먼트 트리, 스위핑 알고리즘), 챌린지반 강의(리사이클러뷰, 반응형 디자인), 챌린지반 과제

>알고리즘 문제

1. 문제

문제 설명

좌표평면을 좋아하는 진수는 x축과 y축이 직교하는 2차원 좌표평면에 점을 찍으면서 놀고 있습니다. 진수는 두 양의 정수 k, d가 주어질 때 다음과 같이 점을 찍으려 합니다.

• 원점(0, 0)으로부터 x축 방향으로 a*k(a = 0, 1, 2, 3 ...), y축 방향으로 b*k(b = 0, 1, 2, 3 ...)만큼 떨어진 위치에 점을 찍습니다.
• 원점과 거리가 d를 넘는 위치에는 점을 찍지 않습니다.

예를 들어, k가 2, d가 4인 경우에는 (0, 0), (0, 2), (0, 4), (2, 0), (2, 2), (4, 0) 위치에 점을 찍어 총 6개의 점을 찍습니다.

정수 k와 원점과의 거리를 나타내는 정수 d가 주어졌을 때, 점이 총 몇 개 찍히는지 return 하는 solution 함수를 완성하세요.

---

제한사항

• 1 ≤ k ≤ 1,000,000
• 1 ≤ d ≤ 1,000,000

2. 솔루션

class Solution {
    fun solution(k: Int, d: Int): Long {
        var answer: Long = 0
        for(x in 0L..d.toLong() step k.toLong()){
            val y= Math.sqrt((d.toLong()*d.toLong() - x*x).toDouble()).toLong()
            answer+=y/k.toLong() + 1L
        }
        return answer
    }
}

 

 

>알고리즘 공부

1. 레이지 프로파게이션 세그먼트 트리

1)의미:세그먼트 트리에서 바로 업데이트 하는 것이 아닌 필요시 업데이트 하는 세그먼트 트리. 

2)방식: 레이지에 업데이트 내역을 저장해 두었다가 해당 노드를 방문하게 되면 자식노드와 자식노드에 해당하는 레이지를 업데이트 시켜준다

3)예시

class SegmentTree(private val size: Int) {
    private val tree = IntArray(4 * size)
    private val lazy = IntArray(4 * size)

    fun updateRange(start: Int, end: Int, value: Int) {
        updateRange(0, 0, size - 1, start, end, value)
    }

    private fun updateRange(node: Int, nodeStart: Int, nodeEnd: Int, start: Int, end: Int, value: Int) {
        if (lazy[node] != 0) {
            tree[node] += (nodeEnd - nodeStart + 1) * lazy[node]
            if (nodeStart != nodeEnd) {
                lazy[2 * node + 1] += lazy[node]
                lazy[2 * node + 2] += lazy[node]
            }
            lazy[node] = 0
        }

        if (start > nodeEnd || end < nodeStart) {
            return
        }

        if (start <= nodeStart && end >= nodeEnd) {
            tree[node] += (nodeEnd - nodeStart + 1) * value
            if (nodeStart != nodeEnd) {
                lazy[2 * node + 1] += value
                lazy[2 * node + 2] += value
            }
            return
        }

        val mid = (nodeStart + nodeEnd) / 2
        updateRange(2 * node + 1, nodeStart, mid, start, end, value)
        updateRange(2 * node + 2, mid + 1, nodeEnd, start, end, value)
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2]
    }

    fun queryRange(start: Int, end: Int): Int {
        return queryRange(0, 0, size - 1, start, end)
    }

    private fun queryRange(node: Int, nodeStart: Int, nodeEnd: Int, start: Int, end: Int): Int {
        if (lazy[node] != 0) {
            tree[node] += (nodeEnd - nodeStart + 1) * lazy[node]
            if (nodeStart != nodeEnd) {
                lazy[2 * node + 1] += lazy[node]
                lazy[2 * node + 2] += lazy[node]
            }
            lazy[node] = 0
        }

        if (start > nodeEnd || end < nodeStart) {
            return 0
        }

        if (start <= nodeStart && end >= nodeEnd) {
            return tree[node]
        }

        val mid = (nodeStart + nodeEnd) / 2
        val leftQuery = queryRange(2 * node + 1, nodeStart, mid, start, end)
        val rightQuery = queryRange(2 * node + 2, mid + 1, nodeEnd, start, end)
        return leftQuery + rightQuery
    }
}

-node의 자식노드 인덱스는 2*node+1, 2*node+2

-update는 구간을 업데이트 시키는 것이고 query는 구간의 합을 구하는 것이다.

 

 

2.스위핑 알고리즘

:면이나 선에서 구간이 겹치는 부분을 합쳐나가며 연산하는 방식의 알고리즘

=>면의 경우 위의 세그먼트 트리로 구현한 방식을 이용하면 된다.

 

 

 

>챌린지반 강의

1. recyclerView의 OOP적 특징
-adapter의 역할: 데이터의 갱신시 중계역할.
=>Activity는 adapter만 보면 됨
=>data에 대한 로직과 UI로직이 분리됨
=>ViewModel을 쓰면 adapter에만 데이터 변화를 알려주면 된다.

-리사클러뷰 Adapter하나에 여러가지의 ViewHolder가 사용되기도 한다
=>아이템뷰가 여러종류로 나타날 수 있다.
=>view type이 뭔지 보내줌

-재활용 로직: 사라져서 안쓰이는 뷰를 unused view에 넣어 저장해두고 이후 재활용해서 data와 binding해서 다시 사용한다.
@이때 문제: data binding을 잘못하면 과거 데이터가 보이기도 함. 이부분 유의
@어댑터는 바로 재활용할지 , 두세개를 남겨두고 재활용할지 선택가능

@ViewHolder안에 또다른 리사이클러뷰가 있기도한다.


2. listAdapter: RecyclerView.Adapter 를 베이스로해서 리스트 데이터를 보여주기위한 것.
=>라이브 데이터 쓸때는 리스트어댑터로 데이터 전달이 더 쉬움
=>submitList로 데이터 전달

@DiFFUtil.ItemCallBack
-areContentsTheSame: 같은 형식인가?
-areItemTheSame : 같은 데이터인가?
=>아이디 비교는 item: 먼저 비교 후 교체
=>객체 자체 비교는 content: 이후 비교 후 교체

위 item부터 비교후 content를 비교하기 때문에 구현 순서도 item부터


3. 화면 모양, 가로세로 별 레이아웃 파일 설정:한정자
-res/layout - land/main_layout.xml
=>가운데 부분.

 

>챌린지반 과제 

1. 연락처 리스트앱

https://appdevelopjava.tistory.com/74

연락처 리스트앱 구현

2. 뉴스 리더 앱

https://appdevelopjava.tistory.com/75

뉴스 리더 앱