본문 바로가기

2024/04

 (14)
[백준] 17182. 우주 탐사선 https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 예를 들어 n이 3이고 시작점이 0일 때, (0 ➡️ 1로 가는 거리 + 0 ➡️ 2로 가는 거리)가 아닌 (0 ➡️ 1로 가는 거리 + 1 ➡️ 2로 가는 거리)가 더 짧을 수도 있다. 즉, 시작점에서 각 노드로 가는 거리만 최소로 갱신할 것이 아니라, 모든 노드에서 모든 노드로의 거리를 최소로 갱신하여 비교해야 한다. 따라서 플로이드 워셜을 사용해야 한다. 플로이드 워셜을 통해 map 배..
[백준] 2531. 회전 초밥 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 투포인터 문제로 주의할 점은 다음과 같다. 최대 초밥 종류의 개수를 구해야하므로, 굳이 k 미만의 접시를 고를 필요가 없으며, 정확히 k개의 접시를 고르면 된다. 즉, 투포인터보다 슬라이딩 윈도우로 푸는 것이 더 적합하다! (start와 end가 함께 이동하며 그 범위가 k로 유지) 먹은 초밥을 배열로 관리한다(eat[30] = 1이면, 30번의 초밥을 1개..
[백준] 2146. 다리 만들기 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 이 문제의 핵심은, 섬들의 가장자리에서 bfs로 바다를 탐색하면 된다. 그러다가 다른 섬을 만났을 때 이동한 카운트가 가장 작은 것이 정답이다. 이렇게 푸는데 있어서 흐름은 다음과 같다. 우선 각 섬들을 bfs해서 각 섬들에 번호를 매겨주어야 한다(2, 3, 4, ...). 이는 나중에 바다를 탐색하다가 섬에 닿았을 때 시작 섬과 도착 섬이 같은 섬인지 아닌지를 구분하기 위함이다. 또 한번 각 섬들을 ..
인터럽트와 입출력 방식 인터럽트 CPU는 특별한 일이 없으면 현재 수행 중인 프로세스의 다음 명령을 순차적으로 수행한다. CPU는 매번 프로그램 카운터가 가리키는 곳에 있는 명령어를 수행한다. 따라서 현재 수행 중인 프로세스로부터 CPU를 회수해서 CPU가 다른 일을 수행하도록 하기 위해서는 인터럽트가 필요하다. 특권 명령 특권 명령은 운영체제 내에서 특정한 권한이 필요한 명령어를 말한다. 따라서 특권 명령을 실행하기 위해서는 일반 사용자 프로그램이 실행하는 것은 불가하고 인터럽트를 발생시켜 운영체제만 특권 명령을 실행할 수 있다. 즉, 모드 비트가 0일 때(=커널 모드)만 특권 명령을 실행할 수 있다. 인터럽트의 종류(발생 상황) 인터럽트는 인터럽트를 발생시키는 주체가 누구냐에 따라 하드웨어 인터럽트와 소프트웨어 인터럽트로 ..
스케줄러 스케줄러란 어떤 프로세스에게 자원을 할당할지를 결정하는 운영체제 커널의 코드를 의미한다. 즉, 스케줄러는 CPU가 어떤 프로세스를 실행할지 결정하는 역할을 한다.스케줄러의 종류장기 스케줄러(작업 스케줄러)역할: 시작 프로세스 중 어떤 프로세스에게 메모리를 할당하고 준비 큐에 삽입할 것인지를 결정한다. 즉, 새로운 프로세스가 실행되기 전에 동작한다. 즉, 장기 스케줄러는 메모리에 동시에 올라가 있는 프로세스의 수를 조절하는 역할을 한다. (degree of multiprogramming을 제어)주기: 상대적으로 덜 빈번하게 작동한다. 주로 새로운 프로세스를 실행하려 할 때 작동한다.중기 스케줄러시스템의 메모리 부담을 줄이기 위해 메모리에 있는 프로세스를 일시적으로 하드디스크로 내보내거나(스왑 아웃), 하드..
블로킹/논블로킹과 동기/비동기 처리 방식 블로킹(Blocking) / 논블로킹(Non-Blocking) 블로킹(Blocking)과 논블로킹(Non-Blocking)은 I/O 작업을 처리하는 방법이다. 블로킹: I/O 작업을 요청한 스레드는 I/O 작업이 완료될 때까지 봉쇄 상태가 되어 대기한다. 논블로킹: I/O 작업을 요청한 스레드는 I/O 작업이 완료될 때까지 대기하지 않고 다음 작업을 수행한다. 즉, 운영체제 관점에서 살펴보면 다음 블로그(https://olsohee.tistory.com/150)에서 설명하는 동기식 입출력 방식이 블로킹 방식이고, 비동기식 입출력 방식이 논블로킹 방식이다. 그리고 주의할 점은 블로킹 방식에서 I/O 작업을 요청한 스레드가 봉쇄 상태가 되었더라도, 그동안 CPU는 다른 스레드를 실행한다는 것이다. 네트워크 ..

티스토리툴바