분류 전체보기

[백준 8980] 택배 C++

8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 그리디 | 정렬 1. 문제 해결 아이디어 [백준 1700] 멀티탭 스케줄링 C++ 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면 hyeo-noo.tistory.com 위 문제와 비슷한 느낌이다. 미래에 배송될 정보들을 모두 알고 있으므로 마을에 도착해서 박스를 받을 때마다, 먼저 도착하는 마을에 배..

Cache Lab csim.c #1

cache lab에서 csim.c를 통해 cache의 동작 방식을 시뮬레이션해보자! SystemSoftware - Cache Memory #1 cache memory에 대해서 알아보자 Locality Temporal locality(시간 지역성) : 최근에 접근했던 data나 명령이 가까운 미래에 다시 사용될 가능성이 높다. (마지막으로 사용된 시간이 오래될수록 다시 사용될 hyeo-noo.tistory.com cache lab을 하기 위해서 반드시 이해해야 할 개념이 있다. cache에 접근하기 위한 address bit의 구조 cache 메모리 자체의 구조 cache에 data를 mapping 하는 방식 해당 개념에 대해서 알쏭달쏭하다면 위 링크를 통해서 이해하고 오자! cache lab tar 파일..

[백준 1167] 트리의 지름 C++

1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 트리, DFS 약 7개월 전에 자료구조 수업에서 트리를 공부하고 풀어보려고 시도했었지만 실패했었던 문제 알고리즘 수업에서 트리의 지름을 구하는 '머리끄댕이' 알고리즘을 배우고 이 문제가 생각나서 적용해서 풀어보았더니 바로 풀림! 1. 문제 해결 아이디어 트리의 지름을 구하기 위한 ㅈㅎㄱ 교수님의 '머리끄댕이' 알고리즘을 알아보자 이러한 트리가 존재하고 지름을 구하기 위해 쭉 늘려보았다 여기서 X는 트리에 있는 임의의 정점이다. X를 잡고 쭉 늘어..

[백준 1328] 고층 빌딩 C++

1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 다이나믹 프로그래밍 1. 문제 해결 아이디어 일반적인 dp문제는 작은 부분 문제들을 해결하면서 큰 문제의 답을 찾는 느낌인데 이 문제는 조금 다른 느낌이다. (도저히 안 풀려서 힌트를 얻었다) 일단 dp배열은 dp[최대 높이][왼쪽에서 보이는 건물 수][오른쪽에서 보이는 건물 수] 이렇게 설정했다. dp배열을 정해주는 건 어렵지 않았다. 그리고 bottom up 방식으로 푸는 게 좋을 것 같다는 느낌이 크게 들었었다. 그런데 점화식을 도출하기가 정말 어려웠다. ..

SystemSoftware - Cache Memory #2

SystemSoftware - Cache Memory #1 cache memory에 대해서 알아보자 Locality Temporal locality(시간 지역성) : 최근에 접근했던 data나 명령이 가까운 미래에 다시 사용될 가능성이 높다. (마지막으로 사용된 시간이 오래될수록 다시 사용될 hyeo-noo.tistory.com cache write방식에 대해서 알아보자 Cache Write는 어떤 방식으로 동작할까? 만약 cache에 write를 했는데 hit가 발생한 경우 Write-through : cache에 데이터를 입력하고 메모리에 바로 작성한다. (cache와 메모리의 정보는 항상 같음) 비용이 많이 든다는 단점이 존재. Write-back : 일단 cache에 수정사항을 입력하고 메모리에는..

SystemSoftware - Cache Memory #1

cache memory에 대해서 알아보자 Locality Temporal locality(시간 지역성) : 최근에 접근했던 data나 명령이 가까운 미래에 다시 사용될 가능성이 높다. (마지막으로 사용된 시간이 오래될수록 다시 사용될 가능성이 낮아짐) Spatial locality(공간 지역성) : 최근에 접근했던 주소와 가까운 data가 미래에 다시 사용될 가능성이 높다. 아래로 갈수록 느리면서 용량이 크고 가격이 싼 저장공간이 위치한다. 위로 갈 수록 용량은 적지만 속도가 빠르고 비싼 저장공간이 위치한다. cache의 메모리 공간은 일정한 크기의 blocks으로 나뉘어진다. cache에서 읽어 들일 수 있는 크기를 일정한 단위로 지정하는 것이다. 위 그림을 보면 CPU가 14번 블럭을 요청했고 cac..

[백준 4811] 알약 C++

4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 다이나믹 프로그래밍 1. 문제 해결 아이디어 dp[한 조각 알약의 개수][반 조각 알약의 개수]를 통해서 메모이제이션을 해주면 쉽게 풀린다. 한 조각 알약이 0개라면 앞으로 반 조각을 먹는 경우밖에 없으므로 return 1을 하는 기저 조건이 된다. 재귀 함수 내부에서는 한 조각 알약의 개수가 0보다 크면 한 조각을 빼고 반 조각을 추가해서 재귀 호출을 하고 마찬가지로 반 조각 알약의 개수가 0보다 크면 반 조각만 빼고 재귀호출을 하는 식으로 구현을 했다. 2. 코드 top d..

[백준 2240] 자두나무 C++

2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 다이나믹 프로그래밍 1. 문제해결 아이디어 cnt초가 지났고, s번 움직였고, 사람 자두가 loc에 있을 때의 최댓값을 메모이제이션 해주었다. 사람의 위치가 그대로 라면 cnt가 T가 되기 전까지 진행이 가능하다. 사람의 위치를 바꾼다면 s가 W가 되기 전까지 위치를 바꿀 수 있다. 현재 위치에 따라서 자두를 먹는지, 못 먹는지를 판단해서 결과에 1을 더할지 말지를 결정한다. 2. 코드 top-down 방식으로 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 ..

[컴퓨터 구조] Control Unit

[컴퓨터 구조] Instruction Set 컴퓨터의 Instruction set에 대해서 알아보자 Ex ) 3 + 6 = 9 Operands : '3', '6' Operator : '+' 명령어 사이클의 기본 상태 Diagram을 알아보자 Instruction fetch : 메모리에 있는 명령어를 가져오는 작업(Op.. hyeo-noo.tistory.com Instruction과 Operand설명 Micro-Operations이 무엇인지, 실제 control을 위해서 어떤 기법들이 사용되는지 알아보자 Micro-Operations 위 그림을 살펴보면 Instruction을 Fetch 해서 decoding 하고 Operand의 주소를 계산해서 Operand를 Fetch 하고(Multiple operand..

SystemSoftware - Creating Processes #2

SystemSoftware - Creating Processes #1 OS에서 process를 만드는 방식에 대해서 알아보자 process는 fork()라는 syscall을 통해서 child process를 생성한다. fork를 호출한 process가 parent process가 되고, 새로 생긴 process가 child가 process이다... hyeo-noo.tistory.com int wait(int *child_status) child를 reaping하기 위해서 명시적으로 child가 종료할 때까지 기다리는 syscall return : child의 pid 값 만약 int *child_status 가 null이 아니라면 문제가 발생한 것이다. 이때 여러개의 매크로를 통해서 어떤 문제가 발생했는지..