솧로그

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net bfs 문제를 몇 달만에 풀어서 다 까먹었을까봐 걱정했는데 아주 쉬운 문제라서 그런지 잘 풀었다! 오랜만에 bfs를 푸는 만큼 쉬운 문제더라도 꼼꼼히 보자. bfs와 dfs 문제의 시간 복잡도는 O(V + E)이다. 이때 V는 노드의 개수, E는 간선의 개수이다. 주의해야 할 점은 다음과 같다. 방문 후에는 방문 처리를 해주어야 한다. 따라서 그림이면서 방문하지 않았을 경우에만 bfs를 시작하고, 이때..

프로세스의 주소 공간 프로그램이 실행되면 프로그램의 모든 코드와 데이터는 가상 메모리에 할당된다. 가상 메모리는 추상화된 메모리 공간으로, 각 프로세스마다 가상 메모리를 갖는다. 그러나 가상 메모리에 할당된 코드와 데이터는 물리적 메모리에 로드될 때까지 실제 메모리에 존재하지 않는다. 그리고 필요에 따라 물리적 메모리에 적재되거나 스왑 영역으로 스왑 아웃된다. 또한 가상 메모리 내의 논리적 주소를 물리적 메모리의 물리적 주소로 변환하는 과정이 필요한데, 이는 MMU(Memory Management Unit)라는 하드웨어 장치가 수행한다. 각각의 가상 메모리는 코드, 데이터, 스택으로 구성된다. 코드: 개발자가 정의한 프로그램 코드가 CPU가 수행할 수 있는 기계어로 변환되어 저장된다. 데이터: 전역 변수..

우리가 흔히 사용하는 운영체제는 여러 프로그램이 동시에 실행될 수 있는 다중 프로그래밍 환경에서 동작한다. 따라서 운영체제는 각 프로그램이 다른 프로그램의 메모리 영역이나 파일 영역을 침범하지 않도록 관리해야 한다. 이때 보안과 관련된 중요하고 위험한 명령들을 특권명령이라고 한다. 하드웨어 보안 운영체제는 하드웨어 보안을 위해 I/O 작업과 같이 디스크 파일에 접근하는 작업을 특권명령으로 삼아, 커널 모드에서만 실행할 수 있도록 한다. 따라서 사용자 프로그램이 맘대로 위험한 명령을 수행하는 것을 막는다. 메모리 보안 디스크뿐만 아니라 메모리의 경우에도 보안이 필요하다. 특히 메모리에 올라와 있는 OS의 코드(ex, 인터럽트 벡터와 인터럽트 처리 루틴)는 각별히 보안이 필요하다. 따라서 2개의 레지스터를 ..

컴퓨터 시스템의 구조 디바이스 컨트롤러와 로컬버퍼 디바이스 컨트롤러: 각각의 입출력 장치에는 컨트롤러가 있는데, 이는 해당 입출력 장치를 관리하는 일종의 작은 CPU이다(하드웨어). 로컬버퍼: 디바이스 컨트롤러는 들어오고 나가는 데이터를 임시로 저장하기 위한 작은 메모리 공간인 로컬 버퍼를 내장하고 있다. 로컬 버퍼는 주로 큐 형태로 구성되며, 선입선출 방식이다. 즉, 디바이스로부터 전송된 순서대로 데이터가 처리된다. DMA(Direct Memory Access) 원칙적으로 메모리는 CPU에 의해서만 접근할 수 있다. 따라서 CPU 외의 장치가 메모리의 데이터에 접근하기 위해서는 CPU에게 인터럽트를 발생시켜서 CPU가 컨트롤러의 로컬버퍼와 메모리 사이에서 데이터를 옮기는 일을 대신한다. 그러나 이 경우..

운영체제란? 운영체제(Operating System)란 컴퓨터 하드웨어 바로 윗단에 설치되는 소프트웨어를 말한다. 좁은 의미의 운영체제: 컴퓨터 전원을 켜면 운영체제는 이와 동시에 실행된다. 소프트웨어가 컴퓨터 시스템에서 실행되기 위해서는 메모리에 그 프로그램이 올라가 있어야 한다. 운영체제도 하나의 소프트웨어이기 때문에 전원이 켜짐과 동시에 메모리에 올라간다. 하지만 운영체제처럼 규모가 큰 프로그램이 모두 메모리에 올라간다면 한정된 메모리 공간의 낭비가 심할 것이다. 따라서 운영체제 중 항상 필요한 부분만 전원이 켜짐과 동시에 메모리에 올려놓고, 그렇지 않은 부분은 필요할 때 메모리에 올려서 사용하게 된다. 이때 메모리에 항상 올라가 있는 부분을 커널(Kernel)이라고 부르며 이를 좁은 의미의 운영체..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 이분 탐색으로 그냥 해당 값이 있는지 찾기만 하면 되는 게 아니라 몇 개 있는지를 찾아야 한다. 따라서 상한선과 하한선을 찾아서 몇 개인지 개수를 계산하면 된다. 입력 값을 배열에 저장하고 배열을 정렬한다. 상한선과 하한선을 찾고, (상한선 - 하한선)이 해당 값의 개수가 된다. 예를 들어 [1, 1, 2, 2, 2, 3]과 같이 배열이 있을 때, 값 2의 상한..

PDU PDU(Protocol Data Unit)는 동일 레이어 간에서 운반되는 데이터를 부르는 이름이다. OSI 7 계층에서 각 계층은 상위 계층으로부터 전달받은 데이터에 헤더 정보를 추가하는데, 이때 각 계층에서 부르는 데이터 단위의 이름이다. 4계층에서는 세그먼트, 3계층에서는 패킷, 2계층에서는 프레임이라고 부른다. 그리고 1계층에서는 2계층으로부터 전달받은 프레임을 비트로 다룬다. SDU SDU(Service Data Unit)는 상향/하향 레이어 간에 전달되는 정보를 말한다. 즉 PDU는 SDU와 헤더 정보인 PCI(Protocol Control Unit)로 이뤄진다. PDU = SDU + PCI Reference http://www.ktword.co.kr/test/view/view.php?m..

https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 어려운 문제는 아니고 그냥 구현 문제이다. 그런데 스티커 회전이라든지, map에 붙일 수 있는지 없는지 이차원 배열의 범위를 탐색한다든지 짜잘하게 신경써야 할 것이 많다. 그리고 그만큼 실수하기 쉬운 문제이다. 다행히 몇 번 디버깅하면서 맞출 수 있었는데, 그래도 다음에 다시 풀면서 꼼꼼히 생각하자는 의미로 기록한다. import java.io.BufferedReader; import java.io..

Set Set은 ADT로 다음과 같은 특징을 갖는다. 중복을 허용하지 않는다. 저장 순서를 유지하지 않는다. HashSet 자바에서는 Set 자료구조의 구현체로 HashSet을 제공한다. HashSet은 다음과 같이 Set 인터페이스를 구현하고 내부적으로 HashMap을 사용한다. public class HashSet extends AbstractSet implements Set, Cloneable, java.io.Serializable { private transient HashMap map; private static final Object PRESENT = new Object(); public HashSet() { map = new HashMap(); } } HashSet이 중복된 데이터를 허용하지..

Map Map은 ADT로 다음과 같은 특징을 갖는다. key-value 형태로 값을 저장한다. key는 중복을 허용하지 않고 value는 중복을 허용한다. 즉, 하나의 key에는 하나의 value만 가진다. 저장 순서를 유지하지 않는다. 해시 충돌 자바의 HashMap은 버킷의 위치를 정할 때 객체의 해시 값을 사용한다. 이때 해시 값은 int형으로 32비트이다. 따라서 어떤 데이터에 대해 나올 수 있는 해시 값은 2^32개이며 그 이상의 데이터들을 HashMap에 저장하려고 하면 몇 개의 데이터들은 해시 값이 같을 수밖에 없다. 그리고 2^32개의 해시 값에 따른 각각 다른 버킷을 메모리 공간에 할당한다면 이는 매우 비효율적이다. 따라서 HashMap에서는 메모리를 절약하기 위해 배열의 capacity..