본문 바로가기

전체 글

 (253)
[ 백준 / C++ ] 1647 : 도시 분할 계획 [ 문제 ] 1647번: 도시 분할 계획 [ 접근방법 ] 전체 마을 대상으로 MST를 구하고 이를 구성하는 최장 간선을 제외하면 유지비의 합을 최소로 마을을 나눌 수 있다. 프림 알고리즘을 활용하여 MST의 총 가중치를 계산하였다. 프림 알고리즘은 MST의 시작점을 하나 정하고, MST와 연결된 최소 가중치 간선을 기준으로 확장하는 방식이다. 최소 가중치 간선을 선택하는 과정에서 우선순위 큐를 활용하여 시간복잡도를 줄였다. [ 소스코드 ] #include #include #include using namespace std;int cal(const vector>> &adj){ int ret = 0, cnt = 0; vector visited(adj.size(), false); priorit..
[ 운영체제 ] 파일 시스템 [ 출처 ]혼자 공부하는 컴퓨터 구조 + 운영체제 15강https://www.youtube.com/watch?v=isj4sZhoxjk[ 파일과 디렉토리 ]파일 시스템 ( file system ) = 파일과 디렉토리를 관리하는 운영체제 내의 프로그램 파일과 디렉토리 = 보조기억장치의 데이터 덩어리 파일 = 보조기억장치에 저장된 관련 정보의 집합 = 의미 있고 관련 있는 정보를 모은 논리적 단위 = 파일을 다루는 모든 작업은 운영체제에 의해 이루어짐 = 파일을 연산하려면 운영체제에 시스템 호출을 통해 접근해야 함 디렉토리 = 윈도우에서는 폴더( folder ) = 여러 계층으로 파일 및 폴더를 관리하는 트리 구조 디렉토리 = 최상위 디렉토리( 루트 디렉토리, / ), 서브 디렉토리 = 디렉..
[ 운영체제 ] 페이징 [ 출처 ]혼자 공부하는 컴퓨터 구조 + 운영체제 14강https://www.youtube.com/watch?v=isj4sZhoxjk[ 연속 메모리 할당 ]연속 메모리 할당 = 프로세스를 연속적인 메모리 공간에 할당 스와핑 = 현재 사용되지 않는 프로세스들을 보조기억장치의 일부 영역( 스왑 영역 )으로 쫒아내고( 스왑 아웃 ), 그렇게 생긴 빈 공간에 새 프로세스 적재( 스왑 인 ) = "프로세스들이 요구하는 메모리 공간 크기 > 실제 메모리 크기" 일 때 유용 메모리 할당 = 프로세스는 메모리의 빈 공간에 할당되어야 함 = 어떤 빈 공간에 할당하는지에 따라 3가지 방식 존재 1. 최초 적합 ( first-fit ) = 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다 적재 가능한 공..
[ 운영체제 ] 교착 상태 [ 출처 ]혼자 공부하는 컴퓨터 구조 + 운영체제 13강https://www.youtube.com/watch?v=isj4sZhoxjk[ 교착 상태란 ]교착 상태가 발생할 조건1. 상호 배제 = 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태2. 점유와 대기 = 자원을 할당 받은 상태에서 다른 자원을 할당 받기를 기다리는 상태3. 비선점 = 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태4. 원형 대기 = 프로세스들이 원의 형태로 자원을 대기하는 상태 위 네 가지 조건 중 하나라도 만족하지 않으면 교착 상태가 발생하지 않음위 네 가지 조건을 모두 만족하면 교착 상태가 발생할 수 있음[ 교착 상태 해결 방법 ]교착 상태 해결 방법 = 예방, 회피, 검출 후 회복..
[ 운영체제 ] 동기화 [ 출처 ]혼자 공부하는 컴퓨터 구조 + 운영체제 12강https://www.youtube.com/watch?v=isj4sZhoxjk[ 동기화란 ]동시다발적으로 실행되는 프로세스들은 서로 협력하고 영향을 주고 받음 = 이 과정에서 자원의 일관성을 보장해야 함 = 프로세스(+스레드)들의 동기화를 고려해야 함 (프로세스) 동기화란? = 프로세스들의 수행 시기를 맞추는 것 = 실행 순서 제어 + 상호 배제 1. 실행 순서 제어 = 프로세스를 올바른 순서대로 실행하기2. 상호 배제 = 동시에 접근해서는 안되는 자원에 하나의 프로세스만 접근하기 공유 자원과 임계 구역1. 공유 자원 = 여러 프로세스 혹은 스레드가 공유하는 자원 = 전역 변수, 파일, 입출력장치, 보조기억장치, ...2. 임계 구역 ..
[ 백준 / C++ ] 4150 : 피보나치 수 [ 문제 ] 4150번: 피보나치 수 [ 접근방법 ] 문제 자체는 dp를 통해 쉽게 풀 수 있다. 그러나, long long을 넘어가는 큰 수를 처리해야 할 순간이 올 때 문제가 발생한다. bn이라는 구조체를 정의하여 큰 수를 처리하였는데, 일의자리부터 15자리씩 끊어 dt라는 벡터에 저장하였다.이렇게 되면 총 1500자리의 수를 처리할 수 있게 된다. dp 연산에 필요한 덧셈은 구조체 bn에 대한 operator+를 정의하여 처리하였다.각 순서에 맞는 dt 벡터 원소끼리 더하며 15자리를 넘어가는 경우는 carry 변수를 통해 처리했다. 구조체를 출력하는 경우에는 먼저 유효한 dt 벡터 원소를 찾아주고 15자리에 맞춰 나머지 원소들을 차례대로 출력했다. [ 소스코드 ] #include #include ..
[ 백준 / C++ ] 16938 : 캠프 준비 [ 문제 ] 16938번: 캠프 준비 [ 접근방법 ] 브루트포스를 통해 가능한 경우를 전부 체크한다. n번째 문제를 2 ^ ( n - 1 ) 이라고 하면 선택할 문제의 총합을 하나의 수로 표현할 수 있고,비트마스킹을 통해 특정 문제를 선택했는지 판별할 수 있다. 판별하는 과정에서 선택한 문제 개수, 최소 및 최대 난이도, 난이도 총합을 계산하여 문제조건에 만족하는지 체크한다. O( n * ( 2 ^ n ) ) 시간복잡도에 n ≤ 15 이므로 충분하다. [ 문제 ] #include #include #include using namespace std;int main(){ ios::sync_with_stdio(0); cin.tie(0); int n, l, r, x; cin >> n >> ..
[ 백준 / C++ ] 1461 : 도서관 [ 문제 ] 1461번: 도서관 [ 접근방법 ] 시작점 0을 기준으로 가장 멀리 있는 책이 있는 방향을 마지막에 방문하는 것이 전체 걸음수를 최소로 만든다. 마지막 이동은 다시 0으로 돌아올 필요가 없으므로 한 번만 걸음수를 계산하면 되고,나머지는 0을 기준으로 왕복해야 하므로 2번 계산한다. [ 소스코드 ] #include #include using namespace std;int f(priority_queue &pq, int m){ int ret = 0; while (!pq.empty()) { int x = pq.top(); for (int i = 0; i > n >> m; priority_queue pq1, pq2; while (n--) { ..

티스토리툴바