728x90 프로그래밍43 [알고리즘] 누적 합, 구간 합 - 백준 단계별로 풀어보기 시리즈 들어가며이번 포스팅에서 다룰 알고리즘은 누적 합 입니다. 누적 합 배열을 이용해 구간 합을 구하는 알고리즘입니다.개인적으로는 구간 합이라고 불리는 것이 더 적절하다고 생각합니다. 아이디어 자체는 간단하지만 한번씩 예상치 못한 곳에서 사용되는 것 같습니다.구간 합누적 합 배열을 이용하여 상수 시간만에 구간의 합을 구하는 알고리즘입니다. 구간 합을 구하는 과정은 일반적으로 다음과 같습니다.1. 누적 합 배열을 만든다. 2. 두 지점의 차를 통해 구간 합을 구한다. 1차원 구간 합$ y $를 누적합 배열, $ x $를 원소라고 하자. 누적 합 배열을 만드는 방법$ y[i] = y[i-1] + x[i] $ 구간 합을 구하는 방법$ [a, b] $ 구간에 대해서, $ y[b] - y[a-1] $ 2차원 구간 합 .. 2024. 7. 26. [알고리즘] 백트래킹 - 백준 단계별로 풀어보기 들어가며이번 챕터는 백트래킹입니다. 특별한 개념은 아니고, 재귀 함수의 콜스택을 이용하여 모든 경우의 수를 탐색하는 알고리즘 입니다.백트래킹재귀 함수를 이용하여 제약 조건 내 모든 경우의 수를 시뮬레이션하는 알고리즘입니다.제약 조건을 잘 설정하는 것이 관건입니다.당연한 얘기지만 재귀 함수를 이용합니다.알고리즘의 구조def backtracking(매개 변수): if 탈출조건: # 탈출 실행 if 제약범위안: # 실행 # 다음 단계로 # 실행 취소 return Any # return의 이용 여부는 사용자에게 달려있음 예시백트래킹 알고리즘은 미로 찾기와 같이 시뮬레이션이 필요한 문제를 푸는데 많이 사용됩니다.보통 다음의 형태로 많이 사용됩.. 2024. 7. 25. [알고리즘] 그래프와 탐색 - 백준 단계별로 풀어보기 시리즈 들어가며설명할게 따로 없어 바로 본론 들어가겠습니다. DFS깊이 우선 탐색이라고 불리며, 방향별로 탐색하는 방법입니다.보통 재귀 함수, 스택으로 구현됩니다.재귀 구현연결되어 있지 않은 노드를 고려하였습니다.grp = { 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': [], 'D': [], 'E': []}visited = set()def dfs(now): if now not in visited: print(now, end=' ') visited.add(now) for next in grp[now]: if next not in visited: dfs(next)for node in grp: dfs(node.. 2024. 7. 24. [안드로이드] Jetpack Compose에 MVVM 적용하기 [안드로이드] Jetpack Compose을 보고 오시면 더 좋습니다. 들어가며이전 시간에는 Jetpack Compose를 이용하여 UI를 만드는 방법을 배웠습니다.사실, Jetpack Compose의 진짜 장점은 MVVM 패턴과 결합했을 때 나온다고 생각하는데요. 그만큼 뷰와 데이터를 연결하기 쉽게 느껴졌기 때문인 것 같습니다. 기존 시스템과의 비교xml 파일과 데이터를 연동하는 기존의 방식은 거쳐야 할 절차가 많았습니다. 기존의 방식의 복잡성을 알기 위해 저번 시간에 구현했던 스톱워치 애플리케이션을 xml로 변환하여, xml파일은 어떻게 뷰와 뷰 모델을 연결했는지 알아봅시다. xml파일에서 데이터 바인딩먼저 종속성을 추가합니다 ... buildFeatures { dataBind.. 2024. 7. 24. [안드로이드] Jetpack Compose 들어가며기존 안드로이드의 UI를 제작하기 위해서는 Xml 파일을 직접 작성하거나, Design 화면에서 열심히 요소를 배치해야했는데요. 현재도 그러한 방법을 많이 사용하고 있지만, 점점 Jetpack Compose로 전환하는 추세를 보이고 있는 것 같습니다.Kotlin이 정착한 이후 안드로이드 개발이 매우 현대적으로 변화하고 있는 것 같습니다. 프로젝트 생성 화면에서도 많은 변화를 느낄 수 있었습니다. 예전에는 Empty Activity를 생성하면 기본적인 구성에 activty_main.xml 파일이 포함되어 생성되었는데, Jetpack Compose의 사용률이 증가하면서 더 이상 기본으로 생성해주지 않았습니다. Empty Views Activity를 클릭하면 activity_main.xml 파일이 포.. 2024. 7. 23. [운영체제] Real-time CPU Scheduling Real-time OS에서 가장 중요한 일은 시간 안에 작업을 수행하여 즉각적으로 반응하는 것입니다.이로 인해, Real-time OS에서는 deadline내에 모든 작업을 수행하기 위해서 선점형 우선순위 기반 스케쥴링을 합니다. Real-time OS의 프로세스의 새로운 특징주기성(periodic) : 주기적으로 반복되어 실행됨 processing time (t) : CPU 사용 시간deadline (d) : 마감 시간period (p) : 반복 주기t Rate Montonic Scheduling선점형 우선순위 기반 스케쥴링 방법이며,CPU burst time이 짧을 수록 높은 우선순위를 가지는 스케쥴링 방법입니다.deadline 내에 실행되지 못한 작업은 다음 주기에 그 작업을 완료합니다. 문제점작.. 2024. 7. 23. [운영체제] Multiprocessor Scheduling CPU 스케쥴링 알고리즘을 학습할 때는 싱글 코어 프로세서를 가정했습니다.멀티 코어 프로세서는 어떻게 스케쥴링할까요? 멀티 코어 스케쥴링 방법Asymmetric multiprocessing (AMP) 하나의 프로세서에 특정한 역할을 부여하는 방식.해당 역할이 부여된 프로세서를 Master라고 하며 스케쥴링, I/O 작업 등을 전담합니다.Master 프로세서에 많은 역할이 가중되면 시스템 전체의 속도가 같이 느려질 수 있습니다. Symmetric multiprocessing (SMP)모든 프로세서가 동일한 역할을 수행하는 방식.각 코어마다 self-scheduling이 필요합니다.일반적으로 SMP 아키텍쳐를 사용합니다. SMP에 대해 더 다뤄보도록 하겠습니다. SMP에서는 코어가 여러개이기 때문에 각 코어.. 2024. 7. 23. [운영체제] CPU Scheduling CPU Scheduling이란 무엇인가CPU Scheduling이란 Ready Queue에 존재하는 작업들의 CPU 사용 시점을 결정하는 과정을 의미합니다.멀티 태스킹을 위해 필요한 운영 체제의 핵심 기능이며 효율적인 CPU 사용을 위한 다양한 스케쥴링 알고리즘이 있습니다. CPU SchedulerCPU Scheduling을 수행하기 위한 소스코드 모듈을 의미합니다.Ready Queue에 존재하는 작업들 중 다음에 실행할 작업을 선택합니다. DispatcherCPU Scheduler 중 context-switch를 담당하는 소스코드 모듈을 의미합니다.CPU Scheduler에 의해 선택된 작업에게 CPU의 제어권을 넘깁니다. (dispatch) 스케쥴링의 두 가지 방식1. 자진 반납 (Non-preemp.. 2024. 7. 20. [운영체제] 쓰레드 (Thread) 쓰레드 (Thread)란 무엇인가쓰레드란 regiseter, pc, stack으로 구성된 CPU Scheduling의 가장 최소 단위 입니다.동일 프로그램을 두 개 이상 실행하는 경우 자원을 효율적으로 사용하기 위해 개발되었습니다.한 프로세스 내에 다수의 쓰레드가 존재할 수 있으며, 프로세스 내의 일부 영역을 공유함으로써 컴퓨터 자원을 효율적으로 사용할 수 있습니다. 공유 하는 영역textdataheapOS resource공유 하지 않는 영역stackregisterpc(program counter) 멀티 쓰레드의 장점(1) 자원 공유 (Resource Sharing)멀티 프로세스를 사용하는 것보다 시스템 자원 소모량을 줄일 수 있고쓰레드끼리는 데이터나 heap영역을 통해 소통할 수 있기 때문에 IPC (.. 2024. 7. 20. 이전 1 2 3 4 5 다음 728x90
