본문 바로가기

내일배움캠프 안드로이드 3기

 (68)
[TIL] 24.03.04 알고리즘, 1주차 프로젝트 회고 1. 알고리즘 문제 해결 문제 출제(백준 2854): 경우의 수를 따지는 DP 문제이다. 처음에는 DP 테이블을 구성할 때, 비연속적인 난이도의 문제를 선택하는 경우와 연속적인 난이도의 문제를 선택하는 경우, 두 경우로만 나누려고 했다. 그런데 그렇게 처리하려고 하니, 계산하기가 영 까다로웠다. 난이도가 n인 문제를 채택할 때 세 가지의 케이스는 따져야 할 것 같았다. - 난이도 n의 문제를 선택하는 경우 - 난이도 n-1 또는 n의 문제를 선택하는 경우 - 난이도 n 또는 n+1의 문제를 선택하는 경우 첫 번째와 세 번째 케이스는 난이도 n-1인 문제를 채택하는 방법에 영향을 받지 않는 것이 자명하다. 따라서 난이도 n-1인 문제까지 선택한 경우의 수에 단순하게 곱해서 DP 테이블을 채울 수 있다. 하..
[TIL] 24.02.29 1. 알고리즘 문제 해결 쉬운 계단 수(백준 10844): 간단한 DP문제, 주어진 N이 워낙 작아서 끝자리 숫자 기준으로 2차원 DP 테이블을 생성해 모두 탐색해주면 된다. 오히려 오버플로우 때문에 모듈러 연산 적용하는 것에 더 신경써야 하는 문제. 동물원(백준 1309): 위의 계단 수 문제와 유사한 문제. 좌우칸을 나누어 생각할 필요 없이, 사자가 해당 행에 위치하는지 아닌지만 따지면 된다. 어차피 가로로도, 세로로도 사자가 붙어있게 배치될 수 없기 때문에, 사자가 한 행에 배치되면 다음 행에 배치될 수 있는 사자의 위치는 고정된다. 따라서 앞의 행에 사자가 없는 경우에는 사자가 배치되는 경우가 2가지 생길 수 있고, 앞의 행에 사자가 있는 경우에는 배치되는 경우가 1가지가 생기게 된다. 그리고 첫..
[TIL] 24.02.28 1. 알고리즘 문제 해결 동전 1(백준 2294): 어제 풀었던 '동전 2' 문제와 유사한 DP 문제이지만, 세부사항이 약간 다르다. '동전 2'에서와는 달리 합이 k원이 되는 동전 조합의 경우의 수를 묻고 있고, 가치가 중복된 동전이 주어지지 않는다. 어제처럼 바깥의 루프가 dp 배열이고(해당 금액을 만들 수 있는 경우의 수가 저장됨) 안쪽의 루프가 동전 배열이면 동전의 중복처리가 상당히 까다로워진다. 따라서 바깥 루프를 동전 배열로 설정하면, 쉽게 해결할 수 있다. #include #include using namespace std; int main() { int n, k; cin >> n >> k; vector coins(n); vector dp(k+1, 0); for(int i=0; i> coin..
[TIL] 24.02.27 1. 알고리즘 문제 해결 포도주 시식(백준 2156): 간단한 유형의 DP 문제이다. 대신 두번째 규칙 때문에 DP 테이블을 나눠서 생각할 필요가 있다. DP 테이블을 3 x n 형태의 2차원 배열로 선언하고, 각 행이 선택 여부를 구분하여 나타낼 수 있도록 했다. - dp[0][k]에는 k번째 포도주를 선택하지 않는 경우를 저장한다. - dp[1][k]에는 k-1번째 포도주를 선택하지 않고, k번째 포도주를 선택하는 경우를 저장한다. - dp[2][k]에는 k-1번째 포도주와 k번째 포도주를 모두 선택하는 경우를 저장한다. 이 때, dp[2][k]를 계산할 때는 dp[1][k-1] 값만을 이용해야하는 것은 명확하며, 모든 DP 테이블 값을 계산한 후에 n번째 열 중 가장 큰 값을 출력해주면 된다. 동전..
[TIL] 24.02.21 1. 안드로이드 공부 오랜만에 Compose를 통해서 UI를 구성하니까 쉽지가 않다. 제대로 다 익히지 못한 채로 중단했었는데, 그래서 더 헷갈리는 부분이 많은 것 같다. 강의를 보며 따라하는 것이 아닌, 혼자 직접 구현해보는 것이 처음이기도 해서 생각보다 진도가 잘 안 나간다. Compose의 핵심이라고 할 수 있는 상태 관리에 대해서도 잊은 부분이 많아 공식문서를 보며 이와 관련된 부분들을 다시금 떠올렸다. - Compose 내에서는, 상태의 변화에 의해 recomposition이 발생한다. Composable 함수 내에 인자로 일반적인 변수를 지정해도, 그 변수의 값이 변한다고 해서 recomposition은 발생하지 않는다. 이를 이용해서 recomposition을 지연시켜서 퍼포먼스를 확보하는 ..
[TIL] 24.02.20 1. 안드로이드 공부 요며칠 쓸 게 없어서 TIL을 작성하지 않았다. 연습용으로 새 프로젝트를 생성하는 김에 빌드 스크립트 관리를 Groovy가 아닌 Kotlin DSL로 해볼까 해서 관련 내용을 좀 찾아봤다. 예전에 한 번 써보았을 때는 다른 것은 차치하고, 컴파일 속도가 좀 답답했던 거 같은데, 아직도 그럴지 모르겠다. Migrate your build configuration from Groovy to Kotlin | Android Studio | Android Developers Groovy에서 Kotlin으로 빌드 구성 이전 | Android 스튜디오 | Android Developers Gradle 구성 파일을 Groovy에서 Kotlin으로 이전합니다. developer.android.com..
[TIL] 24.02.15 1. 알고리즘 문제 해결 텀 프로젝트(백준 9466): 사이클에 포함되지 않는 원소의 수를 찾는 문제이다. DFS를 사용하는 것은 명확했는데 시간초과 때문에 애를 먹었다. 스택을 사용해서 풀려고 시도하니까 자꾸 시간초과가 났다. 탐색에 있어서 방문처리를 위한 자료구조와 사이클을 위한 자료구조를 따로 사용하다보니, 그렇게 된 것 같다. 둘 다 Vector로 이용하면 매번 초기화 과정에서 시간을 많이 사용하게 돼서, Set을 이용해보기도 했는데 조금 더 많은 테스트 케이스를 통과하긴 했지만 결국 시간초과가 났다. 탐색을 진행하다가 방문한 노드에 도달하게 되면 사이클을 찾은 것으로 판단하고, 역으로 순회하며 사이클 포함처리를 해주는 로직이었는데, 내가 아는 선에서는 더 이상 시간 복잡도를 줄이기 힘들어 보였다..
[TIL] 24.02.13 1. 알고리즘 문제 해결 벽 부수고 이동하기2(백준 14442): 로직 자체는 쉽게 떠올릴 수 있는데, 구현하는 과정에서 조금 섬세해야하는 문제. 최단경로 문제인데, 인접정보보단 행렬자체가 주어지는데다 벽을 부수는 것 때문에 타 알고리즘보다 BFS가 적합하다. 방문처리를 할 때 현재 부순 벽의 수 별로 따로 처리해주는 것만 신경쓰면, 다른 BFS 최단 경로 찾기와 같다. 나는 현재까지의 경로 길이를 방문 처리할 때 이용했는데, BFS의 특성상 굳이 그렇게 안하고 방문 여부만 이용했어도 괜찮았을 것 같다. #include #include #include using namespace std; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int n, m; v..

티스토리툴바