본문 바로가기

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

 (68)
[TIL] 24.03.27 알고리즘, 챌린지반 과제 1. 알고리즘 문제 해결 도로포장(백준 1162): 다익스트라 알고리즘에 DP가 섞인 문제. 사실 DP라고 의식하지 않아도 풀다 보면 DP를 이용해서 풀게 된다. 당연하게도 브루트포스로는 풀 수 없다. 도로 중에서 포장할 도로를 고르는 경우의 수만 해도 50,000C20까지 주어질 수 있고, 각 경우의 수마다 최소 비용도 계산해야 한다. 이 문제를 해결하기 위한 로직은 꽤나 심플하다. 다익스트라 알고리즘을 사용하되, 다음 경로를 탐색할 때 도로를 포장하는 경우와 포장하지 않는 경우를 둘 다 고려해서 우선순위 큐에 넣어주는 것이다. 뭐 특정 개수 이하로 벽을 뚫고 미로를 탈출하라든지, 길의 종류가 있고 각 종류별로 제한된 수만큼만 이용하라든지 하는 DFS, BFS와 맥락이 정확히 같다. 이제 저 방법을 적..
[TIL] 24.03.26 알고리즘, 챌린지 반 과제 1. 알고리즘 문제 해결 최소비용 구하기 2(백준 11779): 어제 풀었던 간단한 다익스트라 알고리즘에 추가로 각 노드별로 직전 노드만 저장했다가 역추적해서 경로를 찾아내면 되는 문제. 그래서 별 문제 없이 풀릴 줄 알았는데, 맞왜틀 주화입마에 빠져서 엄청 고생했다.. #include #include #include #include #define INF 987654321 using namespace std; struct cmp { bool operator()(pair l, pair r) { return l.second > r.second; } }; int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); int n, m, start, targe..
[TIL] 24.03.25 알고리즘, 사이드 프로젝트 등 1. 알고리즘 문제 해결 최소비용 구하기(백준 1916): 가중치가 음수인 간선이 없고, 시작점이 고정된 상태에서 최단 경로를 구하는 문제라 다익스트라 알고리즘으로 풀 수 있고, 가장 심플한 형태이다. 정점이라고 할 수 있는 도시의 개수가 1,000개 이하로 주어지기 때문에 O(V^2)의 시간복잡도로 풀어도 무방하겠지만, 굳이 그렇게 구현할 이유는 없으므로 우선순위 큐를 사용해 O((V+E)logV)의 시간복잡도로 풀었다. 너무 잘 알려진 알고리즘이기에 이론적인 부분을 정말 간략하게 작성하자면.. - 시작점에서 향할 수 있는 노드를 찾아 비용 배열을 업데이트하고, 갈 수 없는 곳은 구현 상 들어올 수 없는 값으로 INF 처리한다. - (노드, 비용) 정보들을 우선순위 큐에 집어넣고 비용이 작은 것이 to..
[TIL] 24.03.22 알고리즘, 사이드 프로젝트 1. 알고리즘 문제 해결 문제집(백준 1766): 위상 정렬 문제인데, 우선순위 큐를 활용하는 문제이다. 기존에 사용하던 위상 정렬 로직에서 진입차수가 0인 노드를 찾아 저장해두던 자료구조를 큐 대신 우선순위 큐로 사용하고(min heap), 방문 처리 및 우선순위 큐에 넣는 타이밍을 조금 다르게 했다. 그래프를 입력 받고, 초기의 진입차수가 0인 노드들을 찾아 우선순위 큐에 집어 넣는다. 이 때 집어넣으면서 미리 방문처리를 하도록 한다. 이후에 우선순위 큐의 top을 확인해 출력하고(현 시점에서 가장 먼저 풀 수 있고 쉬운 문제에 해당), 해당 노드의 인접 노드들을 확인한다. 인접 노드들의 진입차수를 1 감소시킨 뒤, 그 시점에 그 인접 노드들의 진입차수가 0이 되었는지와 방문여부를 바로 확인해준다. ..
[TIL] 24.03.21 알고리즘, 사이드 프로젝트 1. 알고리즘 문제 해결 ACM Craft(백준 1005): 위상 정렬 문제인데, DP의 개념을 적용해야 한다. Kahn 알고리즘을 이용해 위상 정렬을 하되, 그 과정에서 진입차수를 빼줄 때 최소 시간 요구치를 함께 업데이트해줘야 한다. 그리고 큐에서 front를 확인할 때, 해당 건물번호가 승리를 위해 필요한 건물의 번호라면 그 건물을 짓는데 필요한 최소 시간 요구치를 출력해 주면 된다. 위상 정렬을 위한 기본적인 알고리즘 구현 방식은 저번 게시물( [TIL] 24.03.20 알고리즘 (tistory.com) ) 참조. #include #include #include #include using namespace std; int main() { cin.tie(nullptr); ios_base::sync_..
[TIL] 24.03.20 알고리즘 1. 알고리즘 문제 해결 줄 세우기(백준 2252): 심플한 위상 정렬 문제이다. N명의 학생과, M번의 비교 정보는 DAG로 치환될 수 있다. 위상 정렬, 그러니까 Topological Sort는 Kahn 알고리즘이나 DFS를 사용해 구현할 수 있는데, 나는 Kahn 알고리즘을 통해 이 문제를 해결했다. Kahn 알고리즘도 심플한 로직인데, 먼저 방문한 적 없고, 진입차수가 0인 노드들을 찾아 큐에 넣는다. 이후 큐에서 노드를 pop하고 해당 노드에서 진출하여 인접하는 노드들의 진입차수 정보를 1씩 감소시킨다. 이 때, 큐에서 빠져나온 순서가 위상 정렬된 상태이며, 큐에서 빠진 시점에 방문처리도 해준다. 큐가 빌 때까지 반복한 이후에 처음으로 돌아가, 또 방문한 적 없고 진입차수가 0인 노드가 있나 확..
[TIL] 24.03.19 개인 과제 1. 앱개발 입문 주차 개인 과제 Lv3 까지의 필수 구현 과제 및 선택 구현 사항을 모두 구현했다. 어제 작성한 것처럼, 기능 및 디자인 명세가 명확해서 예상한대로 금방 끝났다. 해당 주차의 강의에 포함된 내용들만으로 구성하려니, 조금 어색한 부분도 있었지만 큰 문제는 없었던 것 같다. ConstraintLayout을 이용해 기본적인 레이아웃을 구성하고, Intent 활용해 Activity 간 데이터 주고받기 등이 핵심이었다. 기본적인 validation 로직도 필요했다. 그 중에서 조금 신경쓴 것들은 다음의 것들이다. GuideLine 위젯을 이용해 기준점이 되는 constraint 지점으로 삼아, 디스플레이의 세로 비율이 조금 길어지거나 짧아지더라도 중앙을 중심으로 모여있도록 했다. 물론 모든 비율..
[TIL] 24.03.18 Android 앱개발 입문 주차 1. Android 앱개발 입문 주차 오늘부터 본격적인 주특기 주차인 앱개발 입문 주차에 돌입했다. 전체 커리큘럼 중, 저 정도에 위치한 상태라고 한다. 수준별 보충학습도 제공한다고 하는데, 일단 가장 적합한 성취도의 과정을 골라 신청해 놨다. 평소에 조금 애매하게 알고 있던 부분들을(MVVM이나 클린 아키텍처 등을 적용할 때 생기는 의문들) 확실하게 보충해 줄 수 있을 것 같다. 보충과 별개로 메인이 되는 이번 주차의 학습 목적과 구체적인 목표 사항들을 확인하니, 전반적으로 Activity 및 Intent의 활용과 간단한 xml 레이아웃 작성하는 것이 주요 과정인 것 같았다. 그래서 오늘 지급된 강의들을 모두 들어보았는데, 예상과 크게 다른 건 없었다. 이후에는 주어진 개인 과제를 살펴보았다. 2. A..

티스토리툴바