본문 바로가기

분류 전체보기

 (159)
[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이 되었는지와 방문여부를 바로 확인해준다. ..
[운영체제] 1. 서론 본 내용들은 전공수업으로 배운 내용들을 스스로 리마인드하기 위한 목적으로 작성되었으며, 누군가에게 지식을 전달하기 위한 목적으로 작성한 것이 아닙니다. 대부분의 내용은 제가 수강했던 전공수업 및 Operating System Concepts, 10th Edition에 근거하고 있습니다. 1. OS의 정의 뚜렷하게 통용되는 정의는 없다. 응용 프로그램, 유저와 하드웨어 사이의 중재자로서, 핵심적인 기능을 하는 커널부터 함께 포함된 시스템 프로그램, 응용 프로그램, 미들웨어 등에 이르기까지 동봉된 모든 것을 지칭한다. 2. 컴퓨터 시스템 구조의 개요 2.1 컴퓨터 시스템의 조직과 동작 - 하나 이상의 CPU와 Device controller들이 Shared memory에 접근할 수 있는 공용 버스로 연결되어..
[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..
[TIL] 24.03.15 사이드 프로젝트: Compose와 MVVM 1. 사이드 프로젝트: Compose와 MVVM 오늘은 대부분의 시간을 Compose UI에 ViewModel을 적용하면서 보낸 것 같다. 기존 xml에서 MVVM 적용하는 건 어느정도 익숙해졌는데, Compose에 적용해보는 건 낯설었다. Hilt를 이용해 DI를 구현해둔 상태였기 때문에, ViewModel클래스를 상속한 클래스를 만들고 @HiltViewModel 어노테이션을 붙이는 것부터 시작했다. 이후 필요한 Usecase를 주입하고 내부에 메소드를 구현하고 이런 건 xml에서와 같아서 여기까진 금방 끝났다. 그 뒤부터는 이 문서를 참조하여 구현하기 시작했다. ViewModel and State in Compose (android.com) Compose의 ViewModel 및 상태 | Android..

티스토리툴바