솧로그

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개..

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 이 문제의 핵심은, 섬들의 가장자리에서 bfs로 바다를 탐색하면 된다. 그러다가 다른 섬을 만났을 때 이동한 카운트가 가장 작은 것이 정답이다. 이렇게 푸는데 있어서 흐름은 다음과 같다. 우선 각 섬들을 bfs해서 각 섬들에 번호를 매겨주어야 한다(2, 3, 4, ...). 이는 나중에 바다를 탐색하다가 섬에 닿았을 때 시작 섬과 도착 섬이 같은 섬인지 아닌지를 구분하기 위함이다. 또 한번 각 섬들을 ..

경쟁 상태(Race Condition) Race Condition이란, 여러 개의 프로세스가 동시에 공유 데이터에 접근할 때 실행 순서에 따라 결과 값이 달라지는 현상이다. 따라서 이런 경쟁 상태에서는 각 프로세스가 공유 데이터에 동시에 접근하지 못하도록 접근 순서를 제어하는 동기화가 필요하다. 경쟁 상태은 CPU가 하나인 경우에도 발생하는데, CPU가 하나인 경우에는 동시에 하나의 프로세스만 실행할 수 있고, 또 각각의 프로세스는 자신의 주소 공간에만 접근할 수 있는데 경쟁 상태가 발생하는 이유는 뭘까? 예를 들어 다음과 같은 상황이 있다. 프로세스 A는 특권 명령을 수행하려는데, 자신이 직접 수행할 수 없으므로 운영체제에게 부탁하기 위해 시스템 콜을 발생시킨다. CPU 제어권이 운영체제로 넘어오고, ..

인터럽트 CPU는 특별한 일이 없으면 현재 수행 중인 프로세스의 다음 명령을 순차적으로 수행한다. CPU는 매번 프로그램 카운터가 가리키는 곳에 있는 명령어를 수행한다. 따라서 현재 수행 중인 프로세스로부터 CPU를 회수해서 CPU가 다른 일을 수행하도록 하기 위해서는 인터럽트가 필요하다. 특권 명령 특권 명령은 운영체제 내에서 특정한 권한이 필요한 명령어를 말한다. 따라서 특권 명령을 실행하기 위해서는 일반 사용자 프로그램이 실행하는 것은 불가하고 인터럽트를 발생시켜 운영체제만 특권 명령을 실행할 수 있다. 즉, 모드 비트가 0일 때(=커널 모드)만 특권 명령을 실행할 수 있다. 인터럽트의 종류(발생 상황) 인터럽트는 인터럽트를 발생시키는 주체가 누구냐에 따라 하드웨어 인터럽트와 소프트웨어 인터럽트로 ..

스케줄러란 어떤 프로세스에게 자원을 할당할지를 결정하는 운영체제 커널의 코드를 의미한다. 장기 스케줄러(작업 스케줄러) 시작 프로세스 중 어떤 프로세스에게 메모리를 할당하고 준비 큐에 삽입할 것인지를 결정한다. 장기 스케줄러는 메모리에 동시에 올라가 있는 프로세스의 수를 조절하는 역할을 한다. (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는 다른 스레드를 실행한다는 것이다. 네트워크 ..

링크 계층 링크 계층은 네트워크 계층의 한 단계 아래 계층으로, 링크 계층의 전송 단위는 프레임이다. 링크 계층을 이해함으로써 패킷이 라우터로 이동하는 그 과정을 좀 더 구체화시켜 이해할 수 있을 것이다. 이더넷(Ethernet) 이더넷은 링크 계층에서 같은 네트워크 간에 통신을 할 때 사용되는 프로토콜로, 컴퓨터, 서버, 라우터, 스위치 등의 네트워크 장치들을 연결하여 데이터를 전송하고 네트워크를 구성한다. 따라서 이더넷을 사용하여 연결된 장치들은 같은 네트워크 내에 속해야 한다(LAN(Local Area Network)). LAN에서 이더넷을 사용하면 데이터는 주로 이더넷 스위치나 허브를 통해 전송된다. 이더넷 프레임 Destination Address: 도착지 MAC 주소 Source Address..

네트워크 계층, IP 프로토콜 네트워크 계층의 대표적인 프로토콜은 IP(Internet Protocol)이고, 전송 단위는 패킷이다. 패킷의 데이터 부분에 전송 계층의 세그먼트가 담기게 된다. 즉 패킷의 구성은 "IP 헤더(20바이트) + TCP 헤더(20바이트) + 애플리케이션 메시지"라고 할 수 있다. 즉, IP 패킷의 최소 크기는 애플리케이션 메시지를 제외한 40바이트이다. 실제로 네트워크 상에 돌아다니는 IP 패킷을 보면 40바이트 크기의 패킷을 발견할 수 있는데, 그 예로 데이터를 잘 받았다는 피드백의 ACK 용도인 패킷이 있다. IP 프로토콜의 특징은 다음과 같다. 상위 계층에서 전송받은 데이터에 헤더를 붙여 패킷을 만든다. 비연결형 프로토콜로 패킷을 수신지까지 전송하지만 전송 완료를 보장하지..

전송 계층전송 계층은 어플리케이션 계층 바로 아래에 위치하며, 좀 더 구체화된 개념이다. 전송 계층에서의 전송 단위는 세그먼트이며, 세그먼트는 데이터와 헤더 부분으로 나뉜다. 애플리케이션 계층으로부터 받은 메시지가 데이터 부분에 들어가고, 부가 정보가 헤더 부분에 들어간다. 전송 계층의 대표적인 프로토콜로 TCP와 UDP가 있다. UDPUDP는 비연결형 통신 방법으로, TCP와 달리 신뢰성을 보장하지 않는다. 이때 비연결형이라는 것은 다음 사진과 같이 소켓과 소켓 간의 일대일 매핑이 이뤄지지 않는 것은 말한다.즉, 송신지 소켓과 수신지 소켓이 연결되었는지 확인하지 않고 보낸다(connectionless). 그리고 TCP와 달리 전송된 세그먼트에 대한 ACK 응답을 받는 과정이 없다. 따라서 데이터가 제대..

소켓(Socket) 소켓은 네트워크에서 프로세스 간 통신을 가능하게 하는 연결부라고 할 수 있다. 서로 다른 머신에 존재하는 프로세스 간 통신을 위해서는 연결을 위한 인터페이스가 필요하다. 이때 각 머신의 운영체제가 제공하는 네트워크 연결과 관련된 시스템 콜을 소켓 api라고 한다. 네트워크에 연결하기 위한 소켓은 통신 프로토콜에 맞게 만들어져야 한다. 따라서 소켓의 종류는 다음 두가지로 나뉜다. TCP 소켓: TCP 상에서 동작하는 소켓 (소켓 스트림) UDP 소켓: UDP 상에서 동작하는 소켓 (소켓 데이터그램) TCP 소켓을 통한 통신 흐름(소켓 api) 서버 소켓 socket() 소켓을 생성한다. 이때 인자로 소켓의 종류를 지정할 수 있다. TCP 소켓을 위해서는 SOCK_STREAM, UDP 소..