Blog me

문제루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브는 3×3×3개의 작은 정육면체로 이루어져 있다. 퍼즐을 풀려면 각 면에 있는 아홉 개의 작은 정육면체의 색이 동일해야 한다.큐브는 각 면을 양방향으로 90도 만큼 돌릴 수 있도록 만들어져 있다. 회전이 마친 이후에는, 다른 면을 돌릴 수 있다. 이렇게 큐브의 서로 다른 면을 돌리다 보면, 색을 섞을 수 있다.이 문제에서는 루빅스 큐브가 모두 풀린 상태에서 시작한다. 윗 면은 흰색, 아랫 면은 노란색, 앞 면은 빨간색, 뒷 면은 오렌지색, 왼쪽은 초록색, 오른족은 파란색이다.루빅스 큐브를 돌린 방법이 순서대로 주어진다. 이 때, 모두 돌린 다음에 가장 윗 면의 색상을 구하는 프로그램을 작성하시오. 입력첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 ..

문제철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다...

문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딫히면 게임이 끝난다.게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다.(즉, 몸길이는 변하지 않는다.) 사..

스택(Stack) 이란? 메모리안의 데이터들을 효율적으로 관리하게 도와주는 자료 참조 방식FILO(First in Last out) : 처음에 오는 데이터가 제일 마지막에 나간다.LIFO(Last in First out) : 제일 마지막에 들어온 데이터가 제일 처음에 나간다. 스택 구현 방법1. 1차원 배열- 구현이 상대적으로 쉬우나 인풋 사이즈를 미리 알아야 함.2. 리스트- 구현이 상대적으로 어려우나 제한된 사이즈로부터 자유로움. 스택 주요 기능1. Push스택에 데이터를 추가하는 기능2. Pop스택의 최상위 데이터를 빼내어서 가져오는 기능3. Top / Peek 제일 최근에 들어간 데이터, 최근의 데이터 public class Stack { private int MAX_SIZE; private in..

페이징(Paging) 페이지(Page) 단위의 논리-물리 주소 관리기법대부분의 운영체제에서 활용되는 메모리 관리기법필요조건- 논리 주소 공간과 물리 주소 공간을 분리하여 주소의 동적 재배치 허용- 전용 하드웨어(MMU)로 논리주소와 물리주소 변환이 필요 페이징의 주소표현- 페이지 번호(p)와 페이지 오프셋(d)- 논리 주소 공간의 크기가 2^m, 페이지의 크기가 2^n일 때, 상위(m-n)비트는 페이지 번호, 하위 n비트는 오프셋 페이징의 특징- 연속된 논리 주소 공간을 독립적으로 사용하고 주소변환은 하드웨어나 운영체제가 처리하기 때문에 사용자/프로세스의 편의성- 프레임 단위의 비연속적 메모리 할당이기 때문에 동적 메모리 할당에 따른 문제가 없음. (외부 단편화 없음)- 다만 페이지라는 4킬로바이트의 비..

메모리란? - 주소로 접근 가능한 워드 혹은 바이트의 배열 - 메모리의 역할o CPU가 직접 접근하는 유일한 저장장치o 메모리 시스템은 데이터가 아닌 주소(메모리의 위치)로만 관리- 메모리는 프로세스에게 주소공간을 할당함 : 주소 바인딩(Address binding)o 일반적으로 프로세스에게 할당될 실제 메모리 영역은 실행 전에는 고정되지 않음.o 주소 바인딩은 주소 공간들 사이의 변환/매핑 개념 o 주소 바인딩 시점1. 컴파일 시간 (Compile time)소스를 컴파일 하는 중에 적제될 메모리 주소를 생성위치가 변경되면 다시 컴파일 해야하기 때문에 이 시점에 주소 바인딩을 하는 경우는 아주 간단한 프로그램 뿐2. 적재 시간 (Load time)컴파일러는 재배치 가능(relocatable) 코드를 생성..

교착상태(Deadlock)- 두개 이상의 프로세스가 각각 어떤 자원을 소유하고 있으면서 다른 프로세스가 소유한 자원을 추가로 요청하여 기다리고 있는 상황 - 필요조건 1. 상호배재 (Mutual Exclusion) : 한번에 오직 한 프로세스 만이 자원을 활용할 수 있다. 2. 점유와 대기 (Hold and wait) : 프로세스가 적어도 하나의 자원을 점유하면서 다른 프로세스가 점유하고 있는 자원을 추가로 얻기위해 대기한다. 3. 비선점 (No preemption) : 점유된 자원은 강제로 해체될 수 없고, 점유하고 있는 프로세스가 작업을 마치고 자원을 자발적으로 해체한다. 4. 순환대기 (Circular wait) : 대기하고 있는 프로세스 집합 {P0, P1, ... , Pn} 에서 P0은 P1이 ..

정부 "5G 구축 협조하자"..통신사 "망 부담 덜어달라"(종합)- 유영민 장관, 5G망 선도 구축 협조 당부.."설비 공동 사용" - 통신사 "망 투자 부담 계속 커져".."비용 일부 CP와 나눠야"2014년 이후 4년만에 열린 과기정통부(舊 미래부) 장관과 통신 3사 CEO들의 간담회에서는 5G 구축과 서비스 개시와 관련된 협조 부분이 거론됐다. 불필요한 경쟁을 막고 비효율적인 투자를 막기 위해 관로나 전주 등 설비에 대한 공동 사용이 필요하다는 인식도 공유했다. 망 구축과 유지 비용 증가에 따른 부담을 콘텐츠 제공자(CP)들과 나누자는 의견도 개진됐다. 실질 대안중 하나로 ‘제로레이팅’이 언급됐다. 제로레이팅은 네이버나 카카오 등 망을 사용하는 콘텐츠 제공자 망 비용 일부를 부담하는 형태다. 통신 ..

동기화 (Synchronization) - 동시에 실행되는 프로세서들의 실행을 제어하여 원하는 실행 순서에 따라서 실행 시점을 맞추는 것- 공유되는 데이터의 일관성 보장- 임계 영역(공유데이터를 동시에 조작할때 실행의 특정 순서가 달라질 수 도 있는 영역) 문제를 해결하는 것 락 (Lock)- 한 프로세스가 임계 영역에 해당하는 코드를 실행하고 있을 때 다른 프로세스가 임계영역으로 진입하지 못하도록 하는 것- 임계영역으로의 진입 가능성 확인과 동시에 진입 거부를 원자적(프로그램이 중간에 끼어들 수 없음)으로 한번에 처리 - 락킹(locking)을 원자적으로 처리하는 하드웨어 명령어o TestAndSet()한 워드의 내용을 확인하고 수정하는 연산을 원자적으로 처리o Swap()두 워드의 내용을 서로 교환하..

스레드(Thread) - 실과 같이 흘러가는 프로그램의 흐름- CPU 이용의 기본 단위로서, 독립적으로 실행되는 코드 집합- Light Weight Process(경량의 프로세스) 라고 부르기도 함- 하나의 프로세스 내에 반드시 하나 이상의 스레드 존재o 하나의 프로그램을 여러개의 스레드로 동시에 혹은 나누어서 병렬적으로 수행- 각 스레드는 스레드 ID, 프로그램 카운터(PC), 레지스터 집합, 스택을 독립적으로 소유- 같은 프로세스 내의 여러 스레드는 코드(텍스트 영역), 데이터 영역, 열린 파일 등의 시스템 자원을 공유o 독립적인 주소 공간(메모리)은 없으며 다른 스레드와 공유 멀티 스레드(Multi Thread)- 운영체제의 여러작업을 수행하기 위해 프로세스를 늘리는 것 보다, 스레드를 늘리는 것이..