이것저것

문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다. 당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마나 걸릴까? 입력 입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 개의 정수 L, R, C로 시작한다. L(1 ≤ L ≤ 30)은 상범 빌딩의 층 수이다...

Web Socket이란? 두 프로그램 간의 메시지를 교환하기 위한 통신 방법 중 하나 W3C와 IETF에 의해 자리잡은 표준 프로토콜 중 하나 W3C : 월드 와이드 웹을 위한 표준을 개발하고 장려하는 조직 IETF : 인터넷의 운영, 관리, 개발에 대해 협의하고 프로토콜과 구조적인 사안들을 분석하는 인터넷 표준화 작업 기구 현재 인터넷 환경(HTML5) 에서 많이 사용된다. Web Socket을 지원하는 브아주어의 경우 (Internet Explorer, Chrome 등) 은 Web Socket 프로토콜을 지원 Web Socket의 특징 양방향 통신 (Full-Duplex) 데이터 송수신을 동시에 처리할 수 있는 통신 방법 클라이언트와 서버가 서로에게 원할 때 데이터를 주고 받을 수 있다. 통상적인 H..

문제 N×M크기의 배열로 표현되는 미로가 있다. Untitled 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. 출력 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다...

문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다. 출력 첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 ..

문제 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다. 와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다. M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 M과 N, 그리고 K가 빈칸을 ..

Program (=실행시킬 수 있는 파일) 실행되기 전 상태의 명령어, 코드 및 정적인 데이터의 묶음 Processor (=실행을 하는 HW) 프로세스가 동작될 수 있도록 하는 HW (=CPU) (동작이란, 프로그램의 자원들이 메모리에 올라오고, 실행 되어야 할 코드의 메모리 주소를 CPU의 레지스터로 올리는 것을 의미한다.) "프로세서(CPU)는 한 순간에 하나의 프로세스만을 실행할 수 있다." 그러나 작업관리자를 실행시켜 보이면 여러개의 프로세스가 실행되고 있는 것을 볼 수 있다 그 이유는? OS가 짧은 시간에 실행할 프로세스를 교체하고 있기 때문에, 동시에 여러 개의 프로세스가 실행되고 있는 것처럼 느끼는 것이다 Process (= 실행 중인 파일) 실행 중인 Program OS로부터 시스템 자원을..

BFS는 인접한 노드부터 탐색했지만, DFS는 그러지 않다. 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 재귀를 사용하여 구현한다. 모든 노드를 방문하고자 하는 경우 사용된다. 시간복잡도 : O(N+E) void dfs(int curr){ visited[curr] = true; for(int next : adj[curr]){ if(!visited[next]){ dfs(next) } } }

루트노드 (혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. (인접한 노드 =⇒ 가까운 곳부터 먼저 간다) Queue 를 사용해서 구현할 수 있다. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다. 시간 복잡도 : O(N+E) ⇒ O(정점개수+간선개수) 다음 노드를 이미 방문했는지, 방문하지 않았는지를 기록해두는 배열이 필요하다. bool visit[50] : 기본값 false이므로 방문하면 true로 바꿔준다. 큐에 넣는 순간 visit을 true로 바꾸어주어야한다. (색칠된 곳은 visit[ ]=true) void bfs(){ vector visited(N, false); queue q; //q에 push와 visited true체크는 한 세트처럼 q...