분류 전체보기 검색 결과

해당 글 223건

Operator new와 Allocator에 대한 이해

메모리 할당과 생성자 호출의 분리 C++에서 객체를 생성할 때 new를 쓸 수 있다. 그러나 new를 사용할 경우 os로부터 메모리를 얻어옴과 동시에 반드시 해당 메모리에 객체를 생성하고 초기화하게 된다. 하지만 컨테이너를 구현하기 위해서는 메모리를 얻어오는 기능과 객체를 생성하는 기능을 분리할 필요가 있다. 예를 들어 vector를 살펴보자. vector의 size는 실제 생성된 객체의 수를 나타내고, capacity는 os로부터 얻어온 메모리 공간의 수를 나타낸다. 그런데, new를 사용할 경우 os로부터 객체를 생성하지 않고 메모리만 얻어올 수 있는 방법이 없다. 그래서 capacity라는 개념도 존재할 수 없게 된다. operator new와 placement new 메모리 할당과, 객체의 생성을..
Project/STL 구현 2022. 6. 19. 19:20

[BOJ 24445] 알고리즘 수업 - 너비 우선 탐색 2 (C++)

알고리즘 수업 - 너비 우선 탐색 2 (Silver 2) 문제 전체 문제 보기 24445번: 알고리즘 수업 - 너비 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 풀이 정점의 개수 N개만큼 정점을 만들고 각 정점에서 인접한 노드들을 먼저 방문하는 BFS를 구현하여서 푸는 문제. 다만, 인접한 노드를 방문할 때 인접한 노드 인덱스의 내림차순으로 방문해야 하기 때문에 인접한 노드 인덱스 값을 내림차순으로 정렬하는 단계가 필요함. 코드 #include #include #inclu..
Algorithms/DFS & BFS 2022. 5. 14. 09:19

[운영체제(OS)] 메모리 계층 구조

메모리 계층 구조 메모리 계층 구조란 응답 시간을 기반으로 메모리의 종류를 구분한 단계를 의미한다. 응답 속도가 빠를 수록 비싸고, 응답 속도가 늦을 수록 저렴하다. 고성능 프로그램을 설계하기 위해서는 메모리 계층의 제한사항, 즉 각 구성 요소의 크기와 기능을 고려해야한다. 캐시 메모리 활용 캐시 메모리와 레지스터의 응답속도 차이로 인한 병목점을 개선하여 전체 성능을 개선하기 위해서 사용된다. 컴퓨터의 동작 흐름은 기본적으로 다음과 같다. 처리1. 명령어를 바탕으로 메모리에서 레지스터로 데이터를 읽어온다. (메모리에 접근) 처리2. 레지스터에 있는 데이터를 바탕으로 계산한다. (레지스터에 접근) 처리3. 계산 결과를 메모리에 쓴다. (메모리에 접근) 레지스터에만 접근하는 처리2의 과정에 비해서 메모리에 ..
Computer Science/OS 2022. 2. 13. 18:28

[BOJ 1915] 가장 큰 정사각형(C++)

가장 큰 정사각형(Gold4) 문제 전체 문제 보기 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 접근법 처음 문제에 접근할 때 완전 탐색이 가능한지 먼저 확인해보는 것이 중요합니다. 임의의 위치 \((r, c)\)에서 만들 수 있는 정사각형의 최대 크기를 탐색해보기 위해서는 \(O(n^4)\)의 계산량이 필요합니다. 아쉽게도 이번 문제에서는 \(n\)의 크기가 최대 \(1,000\)이기 때문에 완전 탐색으로는 풀 수 없는 문제입니다. 이번 문제는 동적계획법을 활용한 최적화가 필요합니다. 동적 계획법으로 풀기 위해서 점화식을 다음과 같이 세울 수 있습니다. // dp[r][c]..
Algorithms/DP 2021. 12. 16. 22:09