본문 바로가기

전체 글

 (166)
[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..
[TIL] 24.02.08 1. 알고리즘 문제 해결 DSLR(백준 9019): BFS를 이용한다는 것과 로직은 이전 문제들과 흡사하다. 처음에는 큐에 현재까지의 명령어 문자열도 함께 담기도록 했는데, 시간 초과가 났다. 아무래도 문자열의 복사가 반복되다보니, 명령어가 길어질수록 문제가 생길 수 있을 것 같았다. 그래서 그냥 큐에서는 명령어 문자열 대신 직전 값과 직전 명령어가 담기게 했고, 방문 배열에 이를 기록할 수 있도록 했다. 이후 원하는 값에 도달했을 때, 방문 배열을 통해 다시 처음의 값까지 역추적 해서 출력하도록 했고 시간 초과가 나지 않고 통과했다. #pragma GCC optimize("Ofast") #include #include #include using namespace std; int D(int n) { re..
[TIL] 24.02.07 1. 알고리즘 문제 해결 불(백준 5427): 이것도 BFS로 풀 수 있다. 불이 옮겨진 칸을 비롯해 불이 붙으려는 칸도 이동할 수 없으므로, 시간이 지났을 때 불의 번짐처리를 먼저 해주면 된다. 처음에 메모리를 아끼겠답시고, 방문 행렬을 따로 사용하지 않고 기존의 지도 행렬에서 ','를 이용해 방문처리를 해주려고 했다. 그렇게 하니까 불이 먼저 번짐 처리 되었을 때, 방문처리를 동시에 할 수가 없어서 조금 난감했다. 그래서 방문 체크를 조금 느슨하게 했더니 바로 메모리 초과가 났다. 물론 불인데 방문한 곳을 뜻하는 문자를 하나 더 지정했다면 해결할 수 있었을 거 같다. 하지만 직관적으로 짜는게 나중에 코딩 테스트나 사후 리뷰 때 유리한 부분이 있을 것 같아서 그냥 방문 행렬을 따로 만들어 이용했고 바로..

티스토리툴바