일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
- leetcode
- BHS
- 프로그래머스
- Database
- 백준
- 응용 계층
- 릿코드
- 네트워크
- STL
- Transport layer
- 문제풀이
- Djikstra
- ps
- Network
- 임베디드
- 다익스트라
- C++
- baekjoon
- 데이터베이스
- 부트시퀀스
- Embedded
- Application Layer
- BST
- 전송 계층
- swea
- 관계형 모델
- 자료구조
- boot sequence
- dp
- DB
- Today
- Total
목록전체 글 (69)
BOBO's Note
https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세�� www.acmicpc.net 풀이 방법 소요시간을 기준으로 다익스트라 알고리즘을 적용해 풀 수 있다. 이때, 지원비용 내에서 최소 소요시간을 구하는 문제이기 때문에 한번 방문했던 vertex더라도 재방문할 수 있다(소요시간은 짧지만 비용이 커서 해당 경로로 못 갈 수 있기 때문이다). 처음엔 다익스트라 알고리즘에서 인접 vertex에 대해 distance 벡터를 업데이트해줄 때 다음과..
우선순위 큐(Priority Queue)는 우선순위가 높을수록 앞쪽에 위치하는 큐이다. 내부적으로는 heap 자료구조를 사용하므로 전체 N개의 데이터가 존재할 때, 큐의 첫번째 요소를 얻는 데에 O(1), 삽입 및삭제는 O(logN)의 시간이 걸린다. Heap - 추가 예정 - C++ 에 정의되어 있으며 element 타입, 컨테이너 형식(vector 또는 deque), 정렬 기준(less 또는 greater)을 지정해줄 수 있다. 더보기 컨테이너 적응자(container adaptor)에는 stack, queue, priority_queue가 있다. 컨테이너 적응자의 특징은 다음과 같다. 순차 컨테이너보다 축소된 인터페이스를 제공한다. STL 알고리즘을 직접 적용할 수 없다. element 타입, 순차..
https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 풀이방법 다익스트라 알고리즘을 이용해 풀 수 있다. priority queue로 다음 vertex를 고르지 않으면 시간 초과가 발생한다. 두 vertex 사이에 여러 간선이 존재할 수 있으므로, 그 중 가중치가 최소인 간선만 저장하기 위해 adjacency list를 unordered_map을 이용해 변형했다. 각 vertex는 unordered_map을 갖는데, uno..
Dijkstra's Algorithm 다익스트라 알고리즘은 한 vertex에서 다른 vertex들로 가는 최단 경로를 구하는 알고리즘이다. cf) A* 알고리즘: 다익스트라에 휴리스틱을 도입해 더 빠르다. 다익스트라 알고리즘은 한 가지 가정 하에 적용할 수 있다. 모든 edge의 가중치가 양수이다. 다익스트라 알고리즘에서 출발점으로부터 가까운 vertex부터 방문하는 이유는 해당 vertex까지의 거리가 더이상 업데이트될 수 없기 때문이다. 이때 음수 가중치가 허용된다면 이미 방문한 vertex일지라도 더 작은 값으로 업데이트될 수 있어 다익스트라 알고리즘이 제대로 작동하지 않는다. 다익스트라 알고리즘은 distance 벡터와 visited 벡터를 갖는다. distance 벡터는 inf로, visited..
Android Boot Sequence 안드로이드는 리눅스 기반의 운영체제이기 때문에 리눅스 부팅 과정과 흡사하다. 그리고 대부분의 안드로이드 기반 시스템은 ARM 프로세서를 사용한다. 따라서 일반적인 boot sequence에 대해 헷갈린다면, 먼저 이 글을 읽고 오자! 2020/05/25 - [Embedded System] - Generic Boot Sequence Generic Boot Sequence BOBO's Note Generic Boot Sequence 본문 Embedded System Generic Boot Sequence bobo_hee 2020. 5. 25. 23:32 Prev 1 2 3 4 5 6 ··· 8 Next bobo-dev.tistory.com 2020/05/26 - [Em..
일반적인 boot sequence에 대해 헷갈린다면, 이 글을 먼저 보고 오자! 2020/05/25 - [Embedded System] - Generic Boot Sequence Generic Boot Sequence BOBO's Note Generic Boot Sequence 본문 Embedded System Generic Boot Sequence bobo_hee 2020. 5. 25. 23:32 Prev 1 2 3 4 5 6 ··· 8 Next bobo-dev.tistory.com 임베디드 시스템의 Boot Sequence 일반적인 임베디드 시스템에서의 boot sequence는 다음과 같은 순서로 진행된다. ROM 코드: SoC에 위치한 ROM에 boot code를 저장해놓는다. ROM 코드는 스토..
Linux Boot Sequence 컴퓨터에 전원이 들어와 운영체제의 로그인 화면이 뜨기 전까지 여러 과정을 거치게 된다. 보통 다음과 같은 순서를 따른다. 컴퓨터에 전원이 들어오면 ROM에 저장된 BIOS 코드를 실행시킨다. BIOS란, Basic Input/Output System의 약자로, 부팅에 필요한 다양한 주변 장치(예. CPU, RAM, 디스크, USB 장치 등)를 인식하고, I/O 및 동작을 확인하여 초기화한다. 그 후, stage 1 부트로더를 로드한다. POST (Power On Self Test): 주변 장치의 상태 확인 및 초기화, 인터럽트, 메모리 범위, I/O 포트 등을 정리한다. UEFI BIOS: Legacy BIOS를 대체하는 새로운 시스템으로, 2TB 이상의 디스크를 인식..
Host와 Target 임베디드 소프트웨어를 개발할 때, host와 target으로 나뉜다. Host: 애플리케이션을 개발하는 머신 Target: 개발된 애플리케이션을 실행할 머신 host와 target은 다양한 방법으로 연결되는데 주로 serial 통신, 이더넷, JTAG 등으로 연결된다. Toolchain 툴체인은 소프트웨어를 개발하는 데에 필요한 툴들을 모아놓은 것이다. Native toolchain은 host에서 실행되어 host에서 실행되는 프로그램을 생성한다. 반면, cross-compiling toolchain은 host에서 실행되지만 target에서 실행될 프로그램을 생성한다. cross-compiling toolchain에는 다음과 같은 것들이 포함된다. Binutils: 해당 CPU 아..