TIL 24일차 (n^2 배열 자르기 - Kotlin | 앱개발 입문 2주차 정리)

코드카타

 

n^2 배열 자르기

 

문제

 

문제 설명에는 규칙에 따라 2차원 배열을 만들고 평탄화 한 다음

그 배열의 left ~ right 번지수에 해당하는 요소를 담은 배열을 반환하라고 하는데

이 방식대로 문제를 풀면 메모리 초과가 발생하게 된다.

 

 

입출력 예시

 

이것만 봐서는 이해가 어려운데 그래서 밑에 움짤로 설명이 추가되어있다.

 

 

 

이걸 보면 입출력 예시의 이해가 가능하다.

 

 

2차원 배열의 규칙 파악

// n이 3일때 (3x3 행렬일 때)

(1,1) = 1 (1,2) = 2 (1,3) = 3
(2,1) = 2 (2,2) = 2 (2,3) = 3
(3,1) = 3 (3,2) = 3 (3,3) = 3

각 좌표 x, y 값 중 큰 값이 배열 요소의 값이 되는 규칙이 있다.

 

 

배열 평탄화 하기

fun main() {
    var arr = listOf(listOf(1,2,3), listOf(4,5,6))
    println(arr.flatten()) // [1, 2, 3, 4, 5, 6]
}

flatten 함수는 2차원 배열을 평탄화하여 1차원 배열로 반환한다.

flatten함수를 호출하려면 2차원 배열의 요소는 전부 같은 자료형이여야 한다.

 

 

잘못된 풀이

class Solution {
    fun solution(n: Int, left: Long, right: Long): List<Int> {
        val arr = List(n) { x ->
            List(n) { y ->
                if (y <= x) x + 1 else y + 1
            }
        }.flatten()
        
        var res = mutableListOf<Int>()
        for(i in left..right){
            res.add(arr[i.toInt()])
        }
        
        return res
    }
}

문제 설명 그대로 풀이를 진행한 코드이다.

 

컬렉션의 람다식을 사용하여 규칙에 따라 2차원 배열을 생성한 후,

이를 평탄화하여 1차원 배열로 만든 다음,

해당 배열의 left ~ right 번지 요소를 리스트로 반환하는 코드를 작성했다.

 

해당 코드는 Int형 2차원 배열을 생성하는 부분에서 메모리 초과가 발생한다.

제한사항에서 n의 최대값은 10^7이라 언급되어 있기에

2차원 배열을 생성하면 엄청난 메모리 소모가 발생한다.

 

 

2차원 배열 메모리 계산

그래프도 그려주는 우리 지피티

 

arr의 메모리 사용량은 n x n x sizeof(Int)이며, 만약 n이 최대값으로 들어온다면

메모리 사용량은 대략 10^7 x 10^7 x 4 bytes = 400,000,000,000,000 bytes가 된다.

 

이는 매우 큰 메모리 크기로, 일반적인 시스템의 물리적 메모리 한계를 초과한다.

 

 

n^2 배열 인덱스의 x, y 좌표값 구하기

 

n^2 크기의 2차원 배열, 즉 가로 세로 길이가 동일한 2차원 배열에서

x값은 n에서 인덱스 값을 나눈 나머지, y값은 소수점을 제외한 몫에 해당한다.

 

(코틀린에서 정수형(Int, Long 등) 변수들 간의 나눗셈 연산은

소수점 이하 값을 버리고 정수 부분만 반환한다.)

 

 

최적화된 해결 방법

class Solution {
    fun solution(n: Int, left: Long, right: Long): List<Int> {
        val res = mutableListOf<Int>()
        for (i in left..right) {
            val x = (i % n).toInt()
            val y = (i / n).toInt()
            res.add(maxOf(x + 1, y + 1))
        }
        return res
    }
}

메모리 초과 문제를 해결하기 위해서는 전체 배열을 생성하지 않고

필요한 값만 계산하는 방법을 사용해야 한다.

 

해당 로직은 left ~ right 범위 인덱스의 x, y 좌표값을 계산해

배열 규칙에 따라 더 큰 좌표 값을 리스트에 추가하여 알맞은 결과값을 반환한다.

 

 

회고

2차원 배열에 대한 이해도가 소폭 상승한 느낌이다.

2차원 배열의 좌표개념을 알고나니 그제서야 코드를 이해할 수 있었다. 

 

시간 초과는 많이 만나봤지만 메모리 초과는 처음 만나본다.

n차원 배열을 다루는 문제에서 메모리 초과를 고려한 코드를 짜야겠다.

 

---

안드로이드 앱 개발 입문 2주차 정리

 

Anroid Studio 프로젝트 구조

 

북마크

 

F11을 눌러 북마크 지정이 가능하다.

 

 

 

 Shift + F11을 눌러 북마크 리스트 창을 띄울 수 있다.

북마크를 선택 후 Enter를 누르면 해당 북마크의 위치로 이동한다.

 

해당 기능은 프로젝트의 코드가 길어질 때 유용하게 쓰인다.

 

 

그래들

 

그래들은 안드로이드 앱의 빌드 도구이고, build.gradle은 빌드 설정파일에 해당한다.

프로젝트 수준의 그래들과 모듈 수준의 그래들 파일이 존재한다.

 

 

매니페스트

 

앱의 구성요소인 컴포넌트를 정의한 XML파일이다.

 

 

리소스 파일

앱의 리소스를 코틀린 코드에서 분리하여 독립적으로 관리 할 수 있도록 해준다.

화면크기 변화 혹은 사용 언어 변경 등의 다양한 환경에서도 코드의 일관성을 유지할 수 있다.

 

 

리소스 폴더

drawable	이미지 리소스
layout	UI 구성에 필요한 XML 리소
mipmap	앱 아이콘 이미지
values	문자열, 색상 등의 값이 정의된 리소스

 

리소스 폴더는 폴더명 변경과 하위 폴더 생성이 불가하다.

리소스 파일 명에는 알파벳 대문자가 포함되어선 안된다.

 

 

코틀린 소스 파일

 

MainActivity.kt 파일은 프로젝트 생성시 자동으로 만들어진다.

 

 

빌드 프로세스

 

컴파일러는 소스코드를 DEX 파일로 변환하고, 

그 외 모든 것을 컴파일 리소스로 변환한다.

 

APK Packager은 컴파일러가 반환한 것들을 APK 파일로 만든다.

APK 파일은 안드로이드 기기에 앱을 설치하는데 사용되는 앱 파일이다.