백준 | 3655번. 최종 순위 - 위상 정렬 문풀
⬛ 백준 3655번. 최종 순위 - 위상 정렬 문풀 https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 문제 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표하려고 한다. (작년에는 순위를..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 29.
8회차 운영체제 | 데드락, 동기화(뮤텍스, 세마포어) 등 질문 정리
24.01.26 나온 질문 공유 1) 뮤텍스와 스핀락이 어떤 상황에 적합한지 - 뮤텍스 : 대부분의 상황에서 뮤텍스가 더 효율적이다. - 스핀락 : 임계구역 내 작업 시간이 문맥 교환 시간보다 빠를 때는 스핀락이 더 효율적이다. 2) 데드락의 발생 조건 4가지 상호 배제/ 점유 대기/ 비 선점/ 원형 대기 3) 동기화 문제가 무엇인지 설명 동기화 문제 - 스레드가 동시에 공유자원에 대한 접근할 때, 원자적으로 수행되지 않아 일관적이지 않게 됨 4) 세마포어와 뮤텍스의 차이 세마포어 - 여러 자원에 접근 가능, 락을 건 주체가 락을 해제가능 뮤텍스 차이 - 공유자원이 한개일 때 사용 가능, 락을 건 주체 아니어도 락 해제 가능 5) 회피 기법 중 은행원 알고리즘 단점 자원 할당량을 미리 알아야하는데 미리 ..
- [스터디] CS 기술 면접 준비/CS_운영체제 [Operating System]
- · 2024. 1. 27.
백준 | 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 - 위상 정렬 문풀
⬛ 백준 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회차 운영체제 | 데드락, 동기화(뮤텍스, 세마포어) 등 내용 정리
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(크루스칼) 문풀
⬛ 백준 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회차 운영체제 | 세그멘테이션, 페이징, 내부 단편화, 외부 단편화 내용 정리
세그멘테이션, 페이징 (내부단편화 ,외부단편화) 가상 메모리 등장 배경 📌 메인 메모리의 용량은 한정적입니다. 기존에는 프로그램 전부를 메모리에 올려 실행을 하다 보니, 물리 메모리보다 큰 용량의 프로그램을 실행할 수 없었습니다. 이러한 문제를 해결하기 위해서 가상 메모리 개념이 등장합니다. 또한, 프로세스의 모든 부분은 항상 필요한 것이 아니라서, 현재 실행에 필요한 부분만을 메모리에 올림으로써 해결하는 것입니다. → 가상 메모리 기법은 실제 메모리 크기와 프로세스가 올라갈 메모리 위치를 신경 쓰지 않고, 메모리를 이용할 수 있도록 지원하는 기술이다. 가상 메모리 ⬛ 가상 메모리 (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.
백준 | 1717번. 집합의 표현 - 유니온 파인드 문풀
⬛ 백준 1717번. 집합의 표현 - 유니온 파인드 문풀 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 문제 초기에 n+1 개의 집합이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작성하시오. 입력 첫째 줄에 n,m 이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 20.
백준 | 1956번. 운동 - 플로이드에 대한 RE 풀이
https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 문제 V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다. 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자. 당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다. 단, 당신은 운동을 매..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 1. 19.
6회차 운영체제 | 메모리 구조 관련 질문 정리
24.01.19 금 질문 내용 | 24.04.04 답변 업데이트 1) 메모리 구조에서 데이터 영역는 어떤 정보가 들어가는지 설명 - BSS 영역 (Block Started by Symbol) : 명시적으로 초기화 되지 않은 XX (전역, 정적 변수들 저장됨) - Data 영역 : 명시적으로 초기화 된 OO (전역, 정적 변수들 저장됨) 2) 메모리 영역에서 런탐임에 할당되는것들 - 영역 크기/사이즈 : (런타임) 힙 | (정적) 코드, 데이터, 스택 크기 - 메모리 할당 : (런타임) 힙, 스택 | (정적) 코드, 데이터 3) 다른 메모리 영역을 (침범) 접근하려 할 때 어떤일이 발생하는가? CPU 예외 > OS 예외처리를 통해 프로세스 종료 시킨다. 인터럽트 = 하드웨어 + 소프트웨어(트랩) 트랩 - ..
- [스터디] CS 기술 면접 준비/CS_운영체제 [Operating System]
- · 2024. 1. 19.