>알고리즘 문제
1. 네트워크
1)문제
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.
제한사항
- 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
- 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
- i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
- computer[i][i]는 항상 1입니다.
2)솔루션
class Solution {
fun solution(n: Int, computers: Array<IntArray>): Int {
var answer = 0
val q=ArrayDeque<Int>()
val visited=BooleanArray(n){false}
q.addLast(0)
visited[0]=true
answer++
while(q.isNotEmpty()){
val cur=q.removeFirst()
for(i in 0..n-1){
if(!visited[i]&&computers[cur][i]==1){
q.addLast(i)
visited[i]=true
}
}
if(q.isEmpty()){
for(i in 0..n-1){
if(!visited[i]){
q.addLast(i)
visited[i]=true
println(i)
answer++
break
}
}
}
}
return answer
}
}-BFS를 사용하여 탐색후 더이상 탐색할게 없으면 방문안한 노드에서 하나 더 꺼내오며 answer++하는 방식으로 찾음
2. 단어 변환
1)문제
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.
예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.
제한사항
- 각 단어는 알파벳 소문자로만 이루어져 있습니다.
- 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
- words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
- begin과 target은 같지 않습니다.
- 변환할 수 없는 경우에는 0를 return 합니다.
2)솔루션
class Solution {
fun solution(begin: String, target: String, words: Array<String>): Int {
var answer = 0
if(!words.contains(target)) return 0
val arr=Array(words.size){IntArray(words.size)}
for((i,v1) in words.withIndex()){
for((j,v2) in words.withIndex()){
if(checkWord(v1,v2)){
arr[i][j]=1
arr[j][i]=1
}
}
}
val q=ArrayDeque<Pair<Int,Int>>() //변환수, 인덱스
for((i,v) in words.withIndex()){
if(checkWord(begin,v)) {
q.addLast(Pair(1,i))
}
}
while(q.isNotEmpty()){
val (num,cur) = q.removeFirst()
if(num>words.size) continue
if(target==words[cur]) return num
for(i in words.indices){
if(arr[cur][i]==1){
q.addLast(Pair(num+1,i))
}
}
}
return 0
}
fun checkWord(str1:String, str2:String):Boolean{
var dif=0
for(i in str1.indices){
if(str1[i]!=str2[i]) ++dif
}
return if(dif==1) true else false
}
}-우선 단어간 변환 가능한 관계를 표현하는 행렬을 작성
-BFS를 이용하여 구함
>Hilt
1. gradle설정
1)libs.versions.toml
[versions]
hilt = "2.48"
ksp = "1.9.0-1.0.13"
[libraries]
hilt = { group = "com.google.dagger", name = "hilt-android", version.ref = "hilt" }
hilt-compiler = { group = "com.google.dagger", name = "hilt-android-compiler", version.ref = "hilt" }
[plugins]
hilt = { id = "com.google.dagger.hilt.android", version.ref = "hilt"}
ksp = { id = "com.google.devtools.ksp", version.ref = "ksp"}2)mudule수준 gradle
plugins{
alias(libs.plugins.hilt)
alias(libs.plugins.ksp)
}
dependecies{
implementation(libs.hilt)
ksp(libs.hilt.compiler)
}3)Project수준 gradle
plugins{
alias(libs.plugins.hilt) apply false
alias(libs.plugins.ksp) apply false
}
2. Application Class생성 및 AndroidManifest수정
<application
android:name=".ImageSearchApplication"
.
.@HiltAndroidApp
class ExampleApplication : Application() {
override fun onCreate() {
super.onCreate()
.
.
}
}-주로 API데이터를 들고오거나 DB초기화에 사용
-hilt구성요소가 생성되어 Application의 수명주기에 연결되 관련 종속 항목 제공 및 액세스 가능
=>최상위 컨테이너 역할
3. 종속 항목 삽입 - 결합 생성
1)종속항목 주입을 위한 Annotation
-@HiltAdroidApp: Application
-@HiltViewModel: ViewModel
-@AndroidEntryPoint: Activity, Fragment, View, Service, BroadcastReceiver
@유의점: 어떤 클래스에 @AndroidEnrtyPoint 주석을 지정시 이 클래스에 종속된 클래스에도 주석 지정이 필요
-예시: A activity에서 B Fragment를 사용중이면 B에 주석지정시 A에도 주석지정이 필요
=>A는 B에 종속된 상태
2)종속 항목을 받는 계층 구조
<1>@AndroidEntryPoint는 각 클래스에 관한 개별 Hilt구성요소 생성
=>계층구조에 따라 상위클래스에서 종속목을 받을 수 있음
<2>계층구조
3)종속 항목 가져오기
-@Inject를 이용하며 필드나 생성자내 프로퍼티에 삽입 실행 가능
-"필드 주입"시에는 @Inject lateinit var 을 사용
=>private는 사용 불가능!
-"생성자 주입"시에는 class ClassName @Inject constructor(private val ~, val ~,...){}
=>생성자 파라미터도 주입을 받아야 하면 해당 클래스도 @Inject로 만들어주거나 Module사용
@필드주입은 Activity같이 생성자 주입이 불가능한 곳에서만 사용하고 나머진 생성자 주입 사용
4)Hilt Module사용
<1>생성자 주입을 사용할 수 없는 경우 사용
-인터페이스인 경우
-외부 라이브러리인 경우(ex-Retrofit, OkHttp, Room같은 빌터 패턴으로 인스턴스를 생성해야 하는 경우)
<2>사용 방법
-인터페이스의 경우:@Bind사용
interface AnalyticsService {
fun analyticsMethods()
}[1]인터페이스의 구현체에 @Inject로 결합 생성
class AnalyticsServiceImpl @Inject constructor(
...
) : AnalyticsService { ... }[2]abstract class로 Module생성
@Module
@InstallIn(ActivityComponent::class)
abstract class AnalyticsModule {
@Binds
abstract fun bindAnalyticsService(
analyticsServiceImpl: AnalyticsServiceImpl
): AnalyticsService
}=>특징: 그저 연결만 해주는 것이기 때문에 메소드는 추상 메소드이다.
=>묶는법: 파라미터에 구현체, 반환타입에 인터페이스를 쓰면
-외부라이브러리인 경우
(1)특징: binds와 같은 방식인데 라이브러리에 따라 그냥 메소드인 경우도 있다.
=>이런경우 보통object로 하면 됨.
=>그냥 메소드인경우 반환값까지 설정해서 어떤식으로 주입할값을 만드는지도 명시해놓으면 된다.
(1)InstallIn()은 스코프를 의미: 스코프에 따라 사용할 수 있는 범위가 지정되고 수명이 결정 된다.
(2)예시: InstallIn(AcitivityComponent:class)로 지정된 모듈이면 동일 액티비티 내에서 사용될때는 동일 인스턴스를, 서로다른 액티비티에 대해서는 서로다른 인스턴스를 주입한다.
(3)종류
-SingletonComponent: 애플리케이션 수명주기 동안 살아있음. 애플리케이션 수준의 의존성 제공시 사용
-ActivityComponent: 액티비티 수명주기 동안 살아있음. 액티비티 수준의 의존성 제공시 사용
-FragmentComponent: 프래그먼트 수명주기 동안 살아있음. 프래그먼트 수준의 의존성 제공시 사용
-ViewComponent: 뷰의 수명주기 동안 살아있음. 뷰 수준 의존성 제공시 사용
-ViewModelComponent: 뷰 모델 수명주기 동안 살아있음. 뷰 모델 수준 의존성 제공시 사용
-ServiceComponent: 서비스 수명주기 동안 살아있음. 서비스 스준 의존성 제공시 사용
(4)사용: Module에만 사용
@Scope지정법: Module내 의존성(@Provides, @Binds)이나 생성자에 사용
(1)의미: 해당 스코프 내에서 단일 인스턴스를 유지
=>스코프를 지정안하면 매번 새로운 인스턴스를 생성
(2)종류
-@Singleton: 앱 전체에서 단일 인스턴스 유지
-@ActivityScoped: 각 액티비티 생명주기 동안 단일 인스턴스 유지
-@FragmentScoped: 각 프래그먼트 생명주기 동안 단일 인스턴스 유지
-@ViewScoped: 각 뷰의 생명주기 동안 단일 인스턴스 유지
-@ViewModelScoped: 각 뷰모델 생명주기 동안 단일 인스턴스 유지
-@ServiceScoped: 각 서비스 생명주기 동안 단일 인스턴스 유지
(3)유의점: Module에서 사용시 하위컴포넌트에서 사용 불가
=>예를들어 ActivityComponent에서 @Singleton은 사용 불가
@클래스, 구성요소, 범위 정리
@Scope사용 유의점: 제공된 객체는 component가 제거될때까지 메모리에 남아있기때문에 결합에서 scope를 지정하면 cost가 많이 들 수 있음. 그러니 필요한 경우가 아니면 scope 지정된 결합 사용은 지양해야함.
=>특정 scope내에 동일 인스턴스 사용시나 동기화가 필요하거나 생성에 큰 cost가 드는 경우같을때 사용
5)동일 유형을 여려가지로 제공
-@Qualifier: 인터페이스의 구현체가 여러종류인 경우 주석을 이용해서 Inject시 명시해줄 수 있다.
-사용 예시
<1>구현체에 주석 달기
@Qualifier
annotation class InMemoryLogger
@Qualifier
annotation class DatabaseLogger
@InstallIn(ApplicationComponent::class)
@Module
abstract class LoggingDatabaseModule {
@DatabaseLogger
@Singleton
@Binds
abstract fun bindDatabaseLogger(impl: LoggerLocalDataSource): LoggerDataSource
}
@InstallIn(ActivityComponent::class)
@Module
abstract class LoggingInMemoryModule {
@InMemoryLogger
@ActivityScoped
@Binds
abstract fun bindInMemoryLogger(impl: LoggerInMemoryDataSource): LoggerDataSource
}<2>Inject위에 어노테이션 추가
@AndroidEntryPoint
class LogsFragment : Fragment() {
@InMemoryLogger
@Inject lateinit var logger: LoggerDataSource
...
}
6)Context주입
-Application: @AppicationContext context: Context
-Activity: @ActivityContext context: Context
-Fragment: @FragmentContext context: Context
7)Hilt가 지원하지 않는 종류 클래스에 종속 항목 삽입
<1>방법:
-원하는 결합유형마다 @EntryPoint 주석이 지정된 인터페이스를 정의후 @InstallIn으로 진입점 설치할 구성요소 지정
-이후 EntryPointAccessors 오 from~을 이용. ~부분은 @InstallIn에 따라 결정. Argument는 구성요소 이거나 구성요소 소유자 역할을 하는 @AndroidEnrtyPoint객체여야 함.
<2>예시:ContentProvider는 hilt에서 지원안함
class ExampleContentProvider : ContentProvider() {
@EntryPoint
@InstallIn(SingletonComponent::class)
interface ExampleContentProviderEntryPoint {
fun analyticsService(): AnalyticsService
}
...
override fun query(...): Cursor {
val appContext = context?.applicationContext ?: throw IllegalStateException()
val hiltEntryPoint =
EntryPointAccessors.fromApplication(appContext, ExampleContentProviderEntryPoint::class.java)
val analyticsService = hiltEntryPoint.analyticsService()
...
}
}
@@참고 링크@@
https://developer.android.com/training/dependency-injection/hilt-android?hl=ko
Hilt를 사용한 종속 항목 삽입 | Android Developers
이 페이지는 Cloud Translation API를 통해 번역되었습니다. Hilt를 사용한 종속 항목 삽입 컬렉션을 사용해 정리하기 내 환경설정을 기준으로 콘텐츠를 저장하고 분류하세요. Hilt는 프로젝트에서 종속
developer.android.com
>특강 정리
1. 스레드 vs 프로세스
-프로세스: 메모리에 올라와 실행되고 있는 프로그램의 인스턴스(독립적객체)
=>실행된 프로그램을 의미, 프로세스간 자원접근은 IPC(inter-process communication)을 사용해야 함
-스레드: 프로세스 내에서 실행되는 여러 흐름의 단위
=>스레드간에는 stack을 제외한 Code,Data,Heap영역을 공유하므로 힙메모리를 서로 읽고 쓰기 가능
2. (Android)Main Thread vs Worker Thread
-Main Thread(=UI Thread): UI그리는 작업을 맡는 스레드, 다른 작업도 가능하나 작업 시간이 길어지면 ANR이 날 수 있으므로 되도록이면 지양하는게 좋음
-Worker Thread: UI그리는 작업 외의 네트워크작업이나 긴시간이 걸리는 작업등을 하는 스레드
3. 동기(synchronous) vs 비동기(Asynchronous)
-동기: 순차처리. 요청이 들어오면 순차적으로 처리하기때문에 다른 작업들은 완료까지 대기하게 됨.
-비동기: 작업을 독립적으로 실행. 작업이 완료되지 않더라도 다음 작업을 실행함.
4. 코루틴 vs 스레드
-스레드:
1)작업 단위:Thread
2)동시성 보장 수단: Context switching
-Blocking: Thead A가 Thead B의 결과를 기다려야 하면 Thread A는 Blocking되며 그동안 Thread A는 멈춰있는다.
-코루틴:
1)작업단위: Coroutine Object
2)동시성 보장 수단: Programmer Switching
-프로그래머의 코드를 통해 Switching시점을 자유롭게 정함 =>운영체제 커널에 의해 결정되는 스레드와는 다름
-Suspend(Non-Blocking): Object1이 Object2의 결과를 기다려야 한다고 Object1이 실행되던 Thread는 멈추지 않고 계속 일을 함
=>이러한 이유로 한 스레드에서 여러 코루틴작업이 일어날 수 있고 한 코루틴이 여러 스레드를 건너가며 실행될 수 있다.
5. Concurrency(동시성) vs Parallelism(병렬성)
-동시성:동시에 여러작업을 수행. 시분할(Interleaving) 기법을 활용
@시분할 기법: 여러작업을 각각 잘개 쪼갠뒤에 번갈아 가며 수행하여 동시에 일어나는것 처럼 보이게 하는것
-병렬성: 시분할 기법없이 실제로 여러 작업을 동시에 수행
=>작업 수행을 위한 자원(cpu core)이 여러개 존재해야 가능
6. routine vs subroutine vs coroutine
-Routine: 프로그램 일부로써 특정 일을 실행하기 위한 일련의 명령.
=>여기서 일련의 명령을 일컬어 함수라고 부름
-SubRoutine: 함수안에 함수가 있는 경우 안쪽에 있는 함수를 서브루틴이라 부름
-Coroutine: 함께 실행되는 함수
=>서로 다른 함수가 서로 Thread점유를 양보하면서 함께 수행되는 것을 코루틴이라 부름
=>스레드 자원 활용성이 극대화
7. 코루틴 빌더
-코루틴을 만드는 함수
- runBlocking, launch, async, withContext
@runBlocking
1)runBlocking내 코드가 실행될때까지 MainThread를 Blocking함
2)그때문에 안드로이드 메인스레드 호출 환경에서 사용하면 ANR이 발생할수 있음
3)주로 unit test에 사용
=>fun main() = runBlocking{} 같은 형태로 블록내에 테스트할 코드를 넣음
8. 코루틴 스코프
-GlobalScope: 최상위 스코프라 application이 종료될때 까지 살아있음
=>되도록 사용하지 말고 AAC 워크스테이션쓰기(다시 듣기)
-CoroutineScope with Android Components
<1>ViewModelScope: 뷰모델 생명주기에 맞춰 코루틴 Scope관리
=>Viewmodel의 onCleared()에 작업 취소
<2>LifeCycleScope: View의 Lifecycle객체에 정의 되어 생명주기 끝날시 종료됨
9. Suspend function
@Suspend: 언제든지 시작, 멈추고 , 다시시작 가능한 함수.
-이점: Thead는 block되면 thread는 다른 작업을 할 수 없는 block상태가됨
=>반면 suspend함수는 block됐을때 그동안 thread에서는 다른 작업 수행 가능
=>스레드 내에서 코루틴을 여러개가 실행가능하고 코루틴은 여러 스레드에서 실행될 수 있음
=> suspension point도달시 바로 다른 코루틴 실행가능
=>light weight(경량)하다
10. 코루틴 디스패쳐: 코루틴 실행을 스케줄링하기 위해 사용
=>코루틴이 사용할 스레드를 제어하는 작업 담당
-Dispatcher.IO : I/O를 많이 사용하는 작업
=>네트워크/DB 입출력이 있는 작업들에 대해 적절한 Thread로 할당하는 역할. 스레드 풀에서 최대 64개의 Thread를 생성하여 할당이 가능하다.
-Dispatcher.Main : UI와 직접 상호 작용을 하는 작업을 메인 Thread에 전달하는 역할
-Dispatcher.Default: 연속적인 작업, CPU를 많이 사용하는 작업 등을 수행할 때 적절한 Thread로 할당하는 역할. 스레드 풀에서 보통 CPU Core의 개수에 해당하는 Thread를 생성하여 할당이 가능하다.
11. Supervisor Job
1)일반적으로 Job만 사용하면 코루틴에서 에러가 발생시 cancel이 아랫방향, 윗방향 모두 전파되어 전부 취소됨
=>A의 자식 B,C가 있을시 B에서 에러로 취소 발생하면 A로 전파후 다시 A는C로 전파하여 A,B,C전부 취소남
2)Supervisor Job: 예외에 의한 취소를 아래방향으로만 내려가게 함
-예시
suspend fun random1(): Int {
delay(1000L)
return Random.nextInt(0, 500)
}
suspend fun random2Exception() {
delay(500L)
throw ArithmeticException()
}
fun main() = runBlocking {
val scope = CoroutineScope(Dispatchers.IO + SupervisorJob())
val job1 = scope.launch { println(random1()) }
val job2 = scope.launch { random2Exception() }
joinAll(job1, job2)
}-이러면 원래는 r1, r2전부 취소나야 하지만 SupervisorJob덕분에 r1은 정상 작동한다.
12. Job
-사용: 코루틴을 컨트롤하기위해 사용.
-1대 다수: 하나의 코루틴의 동작을 제어하기도 하고 N개의 코루틴 동작을 제어하기도 한다.
-Job의 States
-Job으로 할 수 있는것
1)start: 현재 코루틴 동작을 체크해 동작중이면 true, 아니면 false반환
2)join: 현재 코루틴 동작이 끝날때까지 대기 =>await처럼 사용
3)cancel: 현재 코루틴을 즉시 종료하도록 유도만 하고 대기하지는 않음
=>타이트하게 동작하는 단순루프에서는 delay가 없으면 종료하지 못함
4)cancelAndJoin: 현재 코루틴에 종료하라는 신호를 보내고 정상종료까지 대기
5)cancelChildren: 코루틴 스코프내의 자식 코루틴들을 종료
=>cancel 과는 달리 하위 아이템들만 종료하며 부모는 취소 X
@Mapping: A 형태 클래스를 B형태 클래스로 바꿈
=>map함수를 이용해서 만들어주면 됨.