백준 | 1766번. 문제집 - 위상 정렬 문풀
⬛ 백준 1766번. 문제집 - 위상 정렬 문풀 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제 민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다. 어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 27.
![백준 | 1005번. ACM Craft - 위상 정렬 문풀](http://i1.daumcdn.net/thumb/C120x120/?fname=https://blog.kakaocdn.net/dn/2oyty/btsD3cVyGYg/EHVmA5odqGfbtnzaCdVslK/img.png)
백준 | 1005번. ACM Craft - 위상 정렬 문풀
⬛ 백준 1005번. ACM Craft - 위상 정렬 문풀 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 27.
백준 | 2252번. 줄세우기 - 위상 정렬 문풀
⬛ 백준 2252번. 줄세우기 - 위상 정렬 문풀 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 27.
![8회차 운영체제 | 데드락, 동기화(뮤텍스, 세마포어) 등 내용 정리](http://i1.daumcdn.net/thumb/C120x120/?fname=https://blog.kakaocdn.net/dn/dlsgEu/btsDWJfBfUi/WWTh01cZDB5yMQY8B5Iq70/img.png)
8회차 운영체제 | 데드락, 동기화(뮤텍스, 세마포어) 등 내용 정리
OS 데드락 데드락 조건 4가지 동기화(뮤텍스, 세마포어, 모니터, 스핀락, 어토믹 설명) 들어가기 전 동시다발적으로 실행되는 프로세스(스레드)들은 서로 협력하며 영향을 주고받는다. 이때, 자원의 일관성을 보장하기 위해 프로세스 동기화를 고려해야 한다. 실행 문맥을 갖는 모든 대상은 동기화 대상이다. (스레드도 프로세스도 동기화 대상) 프로세스 동기화 동기화란? 여러 프로세스가 공유 자원에 동시에 접근해도 '공유 자원의 일관성'을 유지하는 것 프로세스들의 수행 시기를 맞추는 것 실행 순서를 위한 동기화와 상호 배제를 위한 동기화가 있다. 1) 실행 순서 제어: 프로세스를 올바른 순서대로 실행되도록 제어 2) 상호 배제 : 동시에 접근해서는 안 되는 자원(=공유 불가능 자원)에 하나의 프로세스만 접근하게 ..
- [스터디] CS 기술 면접 준비/CS_운영체제 [Operating System]
- · 2024. 1. 26.
백준 | 2887번. 행성 터널 - MST 문풀
⬛ 백준 2887번. 행성 터널 - MST 문풀 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 25.
7회차 운영체제 | 세그멘테이션, 페이징, 단편화 관련 질문 정리
24.01.23 질문 정리 | 24.04.12 답변 재정리 1) 페이징과 세그멘테이션 기법을 비교 - 페이징과 세그먼테이션 기법 모두 불연속적으로 메모리에 할당하는 방식인데, 고정 크기인 페이지 단위로 쪼개냐, 가변적인 세그먼트 단위로 쪼개냐 차이 - 페이징의 경우 각 프로세스를 가상 메모리에는 (고정 크기인) 페이지 단위로 쪼개고, 이를 실제 메모리의 프레임에 매핑시키는 방식으로 동작합니다. 고정 크기로 쪼개기 때문에 내부 단편화가 발생할 수 있습니다. - 세그먼테이션 기법은 각 프로세스를 논리적 단위인 (가변 크기) 세그먼트 단위로 분할하여 서로 다른 위치에 할당시킵니다. 크기가 저마다 다르고 논리적 단위로 쪼개기 때문에 외부 단편화가 발생할 수 있습니다. 2) 페이징에서 주소 변환을 할 때 TLB ..
- [스터디] CS 기술 면접 준비/CS_운영체제 [Operating System]
- · 2024. 1. 24.
![백준 | 1647번. 도시 분할 계획 - MST(크루스칼) 문풀](http://i1.daumcdn.net/thumb/C120x120/?fname=https://blog.kakaocdn.net/dn/cB9OC6/btsDQ5WMI2w/KCYNUKsnlDvrvZyfOj3jj0/img.png)
백준 | 1647번. 도시 분할 계획 - MST(크루스칼) 문풀
⬛ 백준 1647번. 도시 분할 계획 - MST(크루스칼) 문풀 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 24.
백준 | 1197번. 최소 스패닝 트리 - MST(크루스칼) 문풀
⬛ 백준 1197번. 최소 스패닝 트리 - MST(크루스칼) 문풀 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 24.
MST | 최소 비용 신장 트리 (MST) 개념 간략한 정리
신장 트리 : n개 정점 무방향 그래프에서 간선 n-1개 부분 그래프 최소 비용 신장 트리 그래프에서 모든 노드 연결 시 사용하는 엣지 가중치 합 최소로 하는 트리 n개 정점 갖는 무방향 그래프에서 모든 노드를 연결한 신장 트리 구성할 때 간선 가중치 합 최소인 트리 MST는 엣지 가중치 최소를 사이클 없고, 단절점 없이 만드는 게 목표다. 에지를 기준으로 하는 알고리즘 [최소 비용 신장 트리 조건] 정점 n개 간선 n-1개 사이클 X : 사이클 포함 시 가중치 합이 최소가 될 수 없으므로 뺀다. 단절점 없는 (연결 그래프) → 최소비용 신장트리를 구현할 알고리즘의 종류 1) 크루스칼 (Kruskal) 알고리즘 모든 간선 가중치 오름차순 정렬 후, 모든 정점이 연결될 때까지 계속해서 작은 가중치를 사이클..
- 코딩 테스트 [준비]/[개념] 알고리즘 추가 정리 _ 2024
- · 2024. 1. 24.
![7회차 운영체제 | 세그멘테이션, 페이징, 내부 단편화, 외부 단편화 내용 정리](http://i1.daumcdn.net/thumb/C120x120/?fname=https://blog.kakaocdn.net/dn/EtxuX/btsDRo8Pkq9/GkSglN7bKSykfBOxdWUbjk/img.png)
7회차 운영체제 | 세그멘테이션, 페이징, 내부 단편화, 외부 단편화 내용 정리
세그멘테이션, 페이징 (내부단편화 ,외부단편화) 가상 메모리 등장 배경 📌 메인 메모리의 용량은 한정적입니다. 기존에는 프로그램 전부를 메모리에 올려 실행을 하다 보니, 물리 메모리보다 큰 용량의 프로그램을 실행할 수 없었습니다. 이러한 문제를 해결하기 위해서 가상 메모리 개념이 등장합니다. 또한, 프로세스의 모든 부분은 항상 필요한 것이 아니라서, 현재 실행에 필요한 부분만을 메모리에 올림으로써 해결하는 것입니다. → 가상 메모리 기법은 실제 메모리 크기와 프로세스가 올라갈 메모리 위치를 신경 쓰지 않고, 메모리를 이용할 수 있도록 지원하는 기술이다. 가상 메모리 ⬛ 가상 메모리 (Virtual Memory) 가상 메모리는 메모리가 실제 메모리보다 많아 보이게 하는 기술로, 어떤 프로세스가 실행될 때 ..
- [스터디] CS 기술 면접 준비/CS_운영체제 [Operating System]
- · 2024. 1. 22.
백준 | 10775번. 공항 - 그리디 & 유니온 파인드 문풀
⬛ 백준 10775번. 공항 - 그리디 & 유니온 파인드 문풀 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 21.
백준 | 1976번. 여행 가자 - 유니온 파인드 문풀
⬛ 백준 1976번. 여행 가자 - 유니온 파인드 문풀 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 20.
백준 | 4195번. 친구 네트워크 - 유니온 파인드 문풀
⬛ 백준 4195번. 친구 네트워크 - 유니온 파인드 문풀 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 문제 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 20.