본문 바로가기

분류 전체보기

 (61)
메모리 (Memory) 레지스터 ,캐시 -> HW관리(CPU) 메인 메모리, 보조기억장치 -> SW관리 (OS) Block : 보조기억장치와 주기억장치 사이의 데이터 전송 단위 (1~4KB) Word : 레지스터와 주기억장치 사이의 데이터 전송 단위 (16~64bits) running 마다 주소 재설정) (명령어 실행 순간 결정) (대부분의 OS가 사용) Fragmentation (단편화) -> 낭비되는 메모리 - 내부 단편화 : pratition 크기 > process크기 - 외부 단편화 : 남은 메모리 크기 > process크기 Continous Memory Allocation (연속 할당) -> 하나의 process를 떨어뜨리지 않고 연속해서 올림 - Fixed partition (FPM) : 메모리를 미리 고정된 크기로..
백준 17142번: 연구소 3 (C++) 문제 링크 : www.acmicpc.net/problem/17142 1. 바이러스가 있는 지점들을 모두 vector에 넣어주고 dfs로 m개의 모든 조합을 선택한다. 2. m개의 바이러스를 선택했으면 spread_bfs로 바이러스를 퍼뜨려준다. 3. 바이러스를 퍼뜨리며 시간을 위치에 기록한다. 4. 이차원 배열에 0이 존재하면 스킵, 다 퍼졌으면 최대시간을 반환한다. 5. 2,3,4를 반복하며 최소시간을 구한다. 바이러스가 퍼진 시간을 구할 때,,바이러스가 빈 공간에만 모두 퍼진시간을 구하는 것이다. 즉 아직 비활성 상태의 바이러스에 더욱 퍼질 수 있어도 이미 빈공간에 다 퍼졌으면 그것이 최소시간이다. #include #include #include using namespace std; int n; in..
프로세스 (Process) Job : 프로그램이 커널에 올라가기 전의 상태 (디스크에 있는 상태) Process : 프로그램이 커널에 등록되어 실행되는 상태 (하나 이상의 스레드) PCB(Process Control Block) : 프로세스의 관리에 필요한 정보 저장, 프로세스 생성할 때 생성. (커널의 영역에 저장되어 있음) Created : job을 커널에 등록해서 프로세스 생성, pcb 할당 Ready : 메모리 할당을 받고 cpu를 기다리고 있는 상태 Running : 프로세서를 할당받고 실행중인 상태 (interrupt나 time slice가 끝나면 교체 됨) Asleep(blocked) : I.O나 다른 이벤트를 기다리고 있는 상태 Suspended Ready : 메모리를 뺏긴 ready 상태, swap device 에..
백준 17140번: 이차원 배열과 연산 (C++) 문제 링크 : www.acmicpc.net/problem/17143 구현, 시뮬레이션 문제이다. 1. 행이 열보다 크면 R 연산으로 모든 행마다 벡터로 저장을 해서 sorting함수로 넘겨준다. 열이 행보다 크면 C 연산으로 모든 열마다 벡터로 저장을 해서 sorting 함수로 넘겨준다. 2. sorting 함수에서 sorting을 진행해준다. 2-1. 벡터를 탐색하며 num_count배열에서 해당 숫자의 index의 값을 증가시켜줌(숫자 개수 구하는 거임) 2-2 num_count를 탐색하며 벡터에 (숫자와 개수를) 쌍으로 넣어준다. 2-3 넣으준 벡터를 sort 라이브러리로 문제 조건대로 정렬시켜줌 3. sorting으로 정렬이 되면 그 뒤의 값들은 0으로 채워준다, row와 column 사이즈 갱신..
(시작 전에) 운영 체제 기본 프로세서(중앙처리장치) : 컴퓨터의 두뇌 레지스터 : 프로세서 내부에 있는 메모리(가장 빠름) - 프로그램 카운터(PC), 명렁어 레지스터(instruction register), 누산기(ACCumulator) 등 메모리 : 데이터 저장 장치 - 속도,가격 : 레지스터 > 캐시 > 메인 메모리 > 보조기억장치 - 레지스터, 캐시 둘다 프로세서 내부에 있음. - 프로세서는 메인메모리까지 밖에 접근 못함. 지역성(Locality) : 공간적 지역성, 시간적 지역성(지역성은 캐시 적중률과 밀접)(캐시는 블록 워드 단위로 가져옴) (장치) 드라이버 : 어떤 하드웨어를 사용하기 쉽게 제공하는 인터페이스(API) 운영체제 : 컴퓨팅 자원을 효율적으로 관리하여 사용자에게 서비스를 제공하는 system 운영체제의 역할..
백준 7569번: 토마토 (C++) 문제 링크 : www.acmicpc.net/problem/7569 배열을 전부 탐색해나가며 토마토를 익게 하면 당연히 시간초과가 난다. 이 문제는 bfs로 간단히 해결할 수 있다. bfs 알고리즘 : wlshddlek.tistory.com/8?category=883327 1. bfs로 토마토를 익게하며 제일 늦게까지 탐색되는 토마토가 몇일만에 탐색되었는지 구한다. 2. 토마토다 다익었으면 제일 늦게 익은 토마토 day를 반환, 안익은게 있으면 -1반환 *bfs로 탐색을 할 때 queue안의 각 점에서 모두 탐색을 한다는 것을 이용한다 -> 시작점을 여러개 넣어도 각 시작점에서 모두 탐색해 나감. #include #include using namespace std; class ins { public: in..
백준 1766번: 문제집 (C++) 문제 링크 : www.acmicpc.net/problem/1766 위상정렬 문제이다. 위상정렬 알고리즘 : wlshddlek.tistory.com/39?category=887828 위상정렬을 이용해야 한다. 위상정렬을 이용할 때 일반 큐가 아니라 우선순위 큐를 사용하면 실시간으로 탐색할 수 있는 것 중에 작은거 부터 탐색할 수 있다. #include #include #include using namespace std; int n, m; vector a[32002]; int indegree[32002]; void topology() //우선순위큐를 이용한 위상 정렬 { priority_queue pq; //실시간으로 선택할 수 있는 것 중 가장 작은거 선택 위함 for (int i = 1; i > m; f..
백준 1005번: ACM Craft (C++) 문제 링크 : www.acmicpc.net/problem/1005 위상정렬과 dp를 이용한 문제이다. 위상정렬 알고리즘 : wlshddlek.tistory.com/39?category=887828 1. 위상정렬 알고리즘으로 순서대로 건물을 짓는다. 1-1. 건물을 탐색할 때 마다 더 오래 걸리는 시간으로 갱신해준다. #include #include #include using namespace std; int time[1002]; vector a[1002]; int indegree[1002];// int d[1002];// int n,w; void topology() { queue q; for (int i = 1; i > test; for (int t = 0; t < test; t++) { int k; c..
위상 정렬 알고리즘 (Topology Sort) 위상 정렬 알고리즘 : 순서가 정해져 있는 작업을 순차적으로 탐색하는 알고리즘 위와 같은 그래프가 주어졌을 때 화살표는 작업의 순서를 나타낸다. ex) 1이 끝나면 3을 시작할 수 있다. ex) 2와 3이 끝나면 5를 시작할 수 있다. 단순하게 자신으로 들어오는 indegree가 모두 제거되면 자신의 일을 시작하면 된다. #include #include #include using namespace std; vector a[10]; int indegree[10]; int n = 7; void topology() { queue q; for (int i = 1; i
[프로그래머스] 방금그곡 (2018 KAKAO BLIND RECRUITMENT) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/17683 이번 문제는 시간복잡도를 고려할 필요없는 파씽문제이다. 그렇기에 연산적인 효율보다는 그냥 구현하기 편한대로 구현하였다. 1. 우선 파씽을 한다, 파씽을 하여 재생시간을 구해준 후 재생시간 동안만큼의 악보를 재작성한다. 2. 재작성한 악보에 주어진 음계m이 포함되어 있다면 조건과 일치하는 음악이다. 2-1 조건과 일치한 음악 중에 재생 시간이 가장 긴 것을 고른다. 2-2 재생 시간이 가장 긴 것 중에선 제일 앞쪽 제목을 선택 #include #include #include using namespace std; string m; vector musicinfos; string time_to_minute(st..

티스토리툴바