배열 arr[]과 위치 s, t가 있을 때, arr[s], arr[s+1], … , arr[t-1]을 오른쪽으로 한 칸씩 이동하고, arr[t]는 arr[s]로 복사하는 것을 ’1만큼 오른쪽으로 회전시켰다’고 한다.
예를 들어 길이가 8인 배열에서 s=2, t=6이면 다음 그림처럼 바뀐다.
길이가 n인 배열의 위치는 0, 1, 2, … , n-1이다.
문제 : k를 인자로 받아서 k만큼 오른쪽으로 회전시키는 함수를 작성하라. 단, 1만큼 오른쪽으로 이동시키는 과정을 k번 반복해서는 안 된다.
조건 1 : 작성하는 언어에는 제한이 없습니다. 조건 2 : 답안으로 작성하신 글 제목에는 ‘문제로 풀어보는 알고리즘 0.3 생각해보기 풀이’라는 문장이 들어가야 합니다. (저희 블로그에도 트랙백을 걸어주세요.)
(주의: 이 코딩 인터뷰는 인사이트 입사와는 무관합니다. ㅡㅁㅡ /)
구체적인 조건에 대한 언급은 없지만 별도의 메모리는 사용하지 않는게 좋겠다는 생각이 들었다.
그리고 1만큼 오른쪽으로 이동시키는 과정을 k번 반복해서는 안된다고 하니 O(n)으로 풀기를 원하는구나.
해결전략은 코드와 같다.
#include <stdio.h>
const int MAX_ELEM = 10;
void rotate(int *array, int s, int t, int k)
{
int range = (t - s + 1);
int idx = s, cycle = s;
int insert, save;
if (k % range == 0) return ;
if (k > range) k %= range;
insert = save = array[s];
for(int i = 0; i < range; i++)
{
insert = save;
int nextIdx = idx + k;
// invalid range check
if (nextIdx > t) {
nextIdx = (nextIdx % (t+1)) + s;
}
save = array[nextIdx];
array[nextIdx] = insert;
idx = nextIdx;
// avoid cycle
if (idx == cycle) {
idx++; cycle++;
save = array[idx];
}
}
}
int main()
{
int array[MAX_ELEM];
// make test set
for(int i = 1; i <= MAX_ELEM; i++) {
array[i-1] = i;
}
rotate(array, 0, 6, 3);
// print result
for(int i = 0; i < MAX_ELEM; i++)
printf("%d ", array[i]);
printf("\n");
return 0;
}
간단히 설명하면, 저장될 곳에 있는 값을 변수에 저장해둬서 덮어쓰더라도 값을 보존시켜가는 방식이다.
그 다음 이동은 지금 덮어씌워진 위치에서 시작한다. 현재 덮어쓴 자리에 있던 값은 저장해두었기 때문에
다음 위치에 저장할 값을 보존할 수 있다. 마찬가지로 다음 위치에 있는 값을 save에 저장하고,
서버: Node.js 설치. 웹서버와 WebSocket 통신을 처리하기 위한 프로세스가 동작하고 있음.(아래 코드 참고)
다음과 같이 chrome 옵션에서 WebRTC 기능을 사용해야 한다.
HTML5 관련 객체
화상통화를 구현하기 위해서는 3가지 객체(?)에 대해 알아야 한다. 다음은 화상통화에서의 각 객체의 기능이다.
(자세한 사용법은 하단의 코드를 참고)
1. webkitGetUserMedia
- 사용자 카메라와 마이크를 이용하기 위해서 사용한다.
2. webkitDeprecatedPeerConnection 또는 webkitPeerConnection
- media(카메라, 마이크) 관련 정보와 데이터를 교환하는데 사용한다.
3. WebSocket
- 서버쪽으로 통신에 필요한 정보를 송신해서 다른 client와 연결을 맺기 위한 통로로 사용한다.
- 채팅기능을 추가한다면 이 통로를 통해 채팅 메시지가 송수신 될 것이다.
테스트 환경 구성도
테스트 환경 구성은 그림과 같다. 동작과정은 크게 2가지로 나뉜다.
처음에는 통신에 필요한 정보를 교환하는 과정인데 여기에 SDP(Session Description Protocol)가 사용된다.
쉽게 말해서 내가 보내려고 하는 정보는 영상이랑 음성이고, 위치는 어디고.. 하는 정보를 교환한다는 말이다.
이 과정이 끝나면 양쪽 클라이언트의 브라우저간에 통신 채널이 열리고 둘이 알아서 영상/음성 데이터를 주고받는다.
물론! 이 과정에서 개발자가 해줘야 할일은 아주 적은 부분에 불과하다. 하지만 짐작했다시피 서버에는 릴레이 기능이
포함되어있어야 한다. 처음에 클라이언트들은 서버와 WebSocket을 이용해서 채널을 열어놓는다.
한쪽에서 통화요청을 하면 열어둔 채널을 통해 요청 메시지를 전송하고, 서버는 이 메시지를 다른 클라이언트에게 전달한다.
요청 메시지(SDP)를 받은 클라이언트는 이에 대해 응답하고, 자신의 정보도 보내준다. 그럼 최초에 통화요청한 클라이언트는
이 메시지를 받은 후 응답하고 드디어 통화가 시작된다. SDP 메시지는 크롬에서 알아서 만들어주므로
우리가 할일은 WebSocket을 이용해서 데이터를 서버로 보내는일과 적절한 타이밍에 미디어 정보를 붙이는(?)일 뿐이다.
코드
백문이 불여일견이라.
Back-end script(broadcast.js)
#!/usr/bin/env node
var WebSocketServer = require('websocket').server;
var http = require('http');
var clients = [];
var idlist = [];
var id = 0;
var server = http.createServer(function(request, response) {
console.log((new Date()) + ' Received request for ' + request.url);
response.writeHead(404);
response.end();
});
server.listen(8080, function() {
console.log((new Date()) + ' Server is listening on port 8080');
});
wsServer = new WebSocketServer({
httpServer: server,
// You should not use autoAcceptConnections for production
// applications, as it defeats all standard cross-origin protection
// facilities built into the protocol and the browser. You should
// *always* verify the connection's origin and decide whether or not
// to accept it.
autoAcceptConnections: false
});
function originIsAllowed(origin) {
// put logic here to detect whether the specified origin is allowed.
return true;
}
wsServer.on('request', function(request) {
if (!originIsAllowed(request.origin)) {
// Make sure we only accept requests from an allowed origin
request.reject();
console.log((new Date()) + ' Connection from origin ' + request.origin + ' rejected.');
return;
}
var connection = request.accept(null, request.origin);
clients.push(connection);
idlist.push(request.key);
console.log((new Date()) + ' Connection accepted.');
connection.on('message', function(message) {
if (message.type === 'utf8') {
console.log('Received Message: ' + message.utf8Data);
for(var i = 0; i < idlist.length; i++) {
if (idlist[i] != request.key) {
cli = clients[i];
msg = message.utf8Data;
cli.sendUTF(msg);
}
}
}
else if (message.type === 'binary') {
console.log('Received Binary Message of ' + message.binaryData.length + ' bytes');
connection.sendBytes(message.binaryData);
}
});
connection.on('close', function(reasonCode, description) {
console.log((new Date()) + ' Peer ' + connection.remoteAddress + ' disconnected.');
});
});
Front-end script(webconf.html)
<!DOCTYPE html>
<html>
<head>
<script type="text/javascript">
var localVideo;
var remoteVideo;
var localStream;
var pc = null;
var wsock;
var remoteSrc = null;
var STUN_CONF = "NONE";
// 초기화 함수. 연결요청, 연결수신 client 공통.
initialize = function() {
console.log("Initializing");
localVideo = document.getElementById("localVideo");
remoteVideo = document.getElementById("remoteVideo");
resetStatus();
// 카메라, 마이크 열기
getUserMedia();
// server와 websocket을 열어둔다.
openChannel();
// 연결요청 버튼 click시 SDP정보 교환 시작
document.getElementById("join").onclick = function() {
rtcStart();
}
}
resetStatus = function() {
setStatus("Initializing...");
}
function openChannel() {
// SDP 정보 교환을 위해, 서버와 연결한다.
url = "ws://192.168.25.114:8080";
wsock = new WebSocket(url);
wsock.onopen = function() {
console.log("open");
}
// 서버로부터 메시지를 받을 때 처리.
wsock.onmessage = function(e) {
console.log("S->C:");
console.log(e.data);
// 연결 요청을 받는 client를 위한 코드. 수신측 client는 일단 메시지를 받아야 한다.
// peerConnection 객체를 생성하고 자신의 media stream을 연결한다.
if (pc == null) {
createPeerConnection();
pc.addStream(localStream);
}
// SDP message는 아래 함수로 넘겨주면 된다. 응답은 알아서 해주므로..
pc.processSignalingMessage(e.data);
}
wsock.onclose = function(e) {
console.log("closed");
}
}
// 카메라, 마이크 자원을 얻는다.
getUserMedia = function() {
try {
navigator.webkitGetUserMedia({audio:true, video:true}, onUserMediaSuccess,
onUserMediaError);
console.log("Requested access to local media with new syntax.");
} catch (e) {
try {
navigator.webkitGetUserMedia("video,audio", onUserMediaSuccess,
onUserMediaError);
console.log("Requested access to local media with old syntax.");
} catch (e) {
alert("webkitGetUserMedia() failed. Is the MediaStream flag enabled in about:flags?");
console.log("webkitGetUserMedia failed with exception: " + e.message);
}
}
}
// peerConnection 생성
createPeerConnection = function() {
try {
// STUN서버 주소와 SDP 메시지를 보내는 함수를 넣어준다.
pc = new webkitDeprecatedPeerConnection(STUN_CONF,
onSignalingMessage);
console.log("Created webkitDeprecatedPeerConnnection with config");
} catch (e) {
console.log("Failed to create webkitDeprecatedPeerConnection, exception: " + e.message);
try {
pc = new webkitPeerConnection(STUN_CONF,
onSignalingMessage);
console.log("Created webkitPeerConnnection with config.");
} catch (e) {
console.log("Failed to create webkitPeerConnection, exception: " + e.message);
alert("Cannot create PeerConnection object; Is the 'PeerConnection' flag enabled in about:flags?");
return;
}
}
pc.onconnecting = onSessionConnecting;
pc.onopen = onSessionOpened;
pc.onaddstream = onRemoteStreamAdded;
pc.onremovestream = onRemoteStreamRemoved;
}
// 연결을 요청하는 client를 위한 함수
// join 버튼을 누르면 동작한다.
rtcStart = function() {
setStatus("Connecting...");
console.log("Creating PeerConnection.");
createPeerConnection();
console.log("Adding local stream.");
// 자신의 media를 연결시킨다. peerConnection을 생성한 이후에 반드시 해줄 것.
pc.addStream(localStream);
}
setStatus = function(state) {
footer.innerHTML = state;
}
// media관련 함수들
onUserMediaSuccess = function(stream) {
console.log("User has granted access to local media.");
var url = webkitURL.createObjectURL(stream);
localVideo.style.opacity = 1;
localVideo.src = url;
localStream = stream;
}
onUserMediaError = function(error) {
console.log("Failed to get access to local media. Error code was " + error.code);
alert("Failed to get access to local media. Error code was " + error.code + ".");
}
// signaling 관련함수들
onSignalingMessage = function(message) {
console.log('C->S: ' + message);
// 열어둔 websocket으로 SDP 메시지를 전송한다.
// peerConnection을 생성하자마자 바로 SDP 메시지를 보낸다.
wsock.send(message);
}
onSessionConnecting = function(message) {
console.log("Session connecting.");
}
onSessionOpened = function(message) {
console.log("Session opened.");
}
onRemoteStreamAdded = function(event) {
console.log("Remote stream added.");
var url = webkitURL.createObjectURL(event.stream);
remoteVideo.style.opacity = 1;
remoteVideo.src = url;
remoteSrc = url;
setStatus("<input type=\"button\" id=\"hangup\" value=\"Hang up\" onclick=\"onHangup()\" />");
}
onRemoteStreamRemoved = function(event) {
console.log("Remote stream removed.");
}
onHangup = function() {
console.log("Hanging up.");
localVideo.style.opacity = 0;
remoteVideo.style.opacity = 0;
pc.close();
pc = null;
setStatus("You have left the call.");
}
</script>
</head>
<body onload="initialize();">
<div id="container">
<div id="local">
<video
width="25%" height="25%" id="localVideo" autoplay="autoplay" style="opacity: 0;
-webkit-transition-property: opacity;
-webkit-transition-duration: 2s;">
</video>
</div>
<div id="remote">
<video width="25%" height="25%" id="remoteVideo" autoplay="autoplay"
style="opacity: 0;
-webkit-transition-property: opacity;
-webkit-transition-duration: 2s;">
</video>
</div>
<div id="footer"></div>
</div>
<button id="join">join</button>
</body>
</html>
WebSocket echo 테스트 코드를 조금만 수정하면 아주 간단한 채팅 어플을 만들 수있다.
이런것이 모두 web에서 가능하다는 것!!
back-end script (broadcast.js)
var WebSocketServer = require('websocket').server;
var http = require('http');
var clients = [];
// 임의로 ID부여하기 위함
var idlist = [];
var id = 0;
var server = http.createServer(function(request, response) {
console.log((new Date()) + ' Received request for ' + request.url);
response.writeHead(404);
response.end();
});
server.listen(8080, function() {
console.log((new Date()) + ' Server is listening on port 8080');
});
wsServer = new WebSocketServer({
httpServer: server,
// You should not use autoAcceptConnections for production
// applications, as it defeats all standard cross-origin protection
// facilities built into the protocol and the browser. You should
// *always* verify the connection's origin and decide whether or not
// to accept it.
autoAcceptConnections: false
});
function originIsAllowed(origin) {
// put logic here to detect whether the specified origin is allowed.
return true;
}
wsServer.on('request', function(request) {
if (!originIsAllowed(request.origin)) {
// Make sure we only accept requests from an allowed origin
request.reject();
console.log((new Date()) + ' Connection from origin ' + request.origin + ' rejected.');
return;
}
var connection = request.accept(null, request.origin);
clients.push(connection);
// 임의로 id값을 할당함. request.key값으로 client 구분
idlist[request.key] = id++;
console.log((new Date()) + ' Connection accepted.');
connection.on('message', function(message) {
if (message.type === 'utf8') {
console.log('Received Message: ' + message.utf8Data);
// 브로드캐스팅!!
clients.forEach(function(cli) {
msg = idlist[request.key]+ ': ' +message.utf8Data;
cli.sendUTF(msg);
});
}
else if (message.type === 'binary') {
console.log('Received Binary Message of ' + message.binaryData.length + ' bytes');
}
});
connection.on('close', function(reasonCode, description) {
console.log((new Date()) + ' Peer ' + connection.remoteAddress + ' disconnected.');
});
});
front-end script (websocket.html)
<!DOCTYPE html>
<title>WebSocket Test Page</title>
<script>
var log = function(s) {
console.log(s);
if (document.readyState !== "complete") {
log.buffer.push(s);
} else {
document.getElementById("output").innerHTML += (s + "\n")
}
}
log.buffer = [];
url = "ws://192.168.25.114:8080";
w = new WebSocket(url);
w.onopen = function() {
log("open");
w.send("thank you for accepting this Web Socket request");
}
w.onmessage = function(e) {
console.log(e.data);
log(e.data);
}
w.onclose = function(e) {
log("closed");
}
window.onload = function() {
log(log.buffer.join("\n"));
document.getElementById("sendButton").onclick = function() {
console.log(document.getElementById("inputMessage").value);
w.send(document.getElementById("inputMessage").value);
}
// 간지나게 엔터키 누르면 메시지 날림
document.getElementById("inputMessage").onkeypress = function() {
if (event.keyCode == '13') {
value = document.getElementById("inputMessage").value
w.send(value);
document.getElementById("inputMessage").value = "";
}
}
}
</script>
<input type="text" id="inputMessage">
<button id="sendButton">Send</button>
<pre id="output"></pre>
Node.js에는 기본적으로 WebSocket 모듈이 들어있지 않은 모양이다. 그래서 따로 설치를 해줘야 한다.
모듈 설치에는 npm(Node Package Manager)이라는 것을 사용하면 편하다.
다음과 같이 npm과 WebSocket 모듈을 설치할 수 있다. npm은 /usr/local/bin에 설치된다.
shell> curl http://npmjs.org/install.sh | sh
shell> cd /usr/local/bin
shell> ./npm install websocket
WebSocket echo Front/Back-end script
이제 필요한 준비가 모두 끝났다. 구미에 맞는 서버를 구현해서 띄워놓고 테스트를 해보자.
/usr/local/bin에 다음 파일을 만들어둔다.
ws_server.js
#!/usr/bin/env node
var WebSocketServer = require('websocket').server;
var http = require('http');
var server = http.createServer(function(request, response) {
console.log((new Date()) + ' Received request for ' + request.url);
response.writeHead(404);
response.end();
});
server.listen(8080, function() {
console.log((new Date()) + ' Server is listening on port 8080');
});
wsServer = new WebSocketServer({
httpServer: server,
// You should not use autoAcceptConnections for production
// applications, as it defeats all standard cross-origin protection
// facilities built into the protocol and the browser. You should
// *always* verify the connection's origin and decide whether or not
// to accept it.
autoAcceptConnections: false
});
function originIsAllowed(origin) {
// put logic here to detect whether the specified origin is allowed.
return true;
}
wsServer.on('request', function(request) {
if (!originIsAllowed(request.origin)) {
// Make sure we only accept requests from an allowed origin
request.reject();
console.log((new Date()) + ' Connection from origin ' + request.origin + ' rejected.');
return;
}
var connection = request.accept(null, request.origin);
console.log((new Date()) + ' Connection accepted.');
connection.on('message', function(message) {
if (message.type === 'utf8') {
console.log('Received Message: ' + message.utf8Data);
connection.sendUTF(message.utf8Data);
}
else if (message.type === 'binary') {
console.log('Received Binary Message of ' + message.binaryData.length + ' bytes');
connection.sendBytes(message.binaryData);
}
});
connection.on('close', function(reasonCode, description) {
console.log((new Date()) + ' Peer ' + connection.remoteAddress + ' disconnected.');
});
});
다음과 같이 Front-end script를 구현한다. (반드시 Back-end 코드와 같은 위치에 있을 필요는 없다)
websocket.html
<!DOCTYPE html>
<title>WebSocket Test Page</title>
<script>
var log = function(s) {
console.log(s);
if (document.readyState !== "complete") {
log.buffer.push(s);
} else {
document.getElementById("output").innerHTML += (s + "\n")
}
}
log.buffer = [];
// 아래 값은 상황에 맞게 변경할 것
url = "ws://192.168.25.114:8080";
w = new WebSocket(url);
w.onopen = function() {
log("open");
w.send("thank you for accepting this Web Socket request");
}
w.onmessage = function(e) {
console.log(e.data);
log(e.data);
}
w.onclose = function(e) {
log("closed");
}
window.onload = function() {
log(log.buffer.join("\n"));
document.getElementById("sendButton").onclick = function() {
console.log(document.getElementById("inputMessage").value);
w.send(document.getElementById("inputMessage").value);
}
}
</script>
<input type="text" id="inputMessage" value="Hello, Web Socket!"><button id="sendButton">Send</button>
<pre id="output"></pre>
코드를 보면 알 수 있듯이 Front-end 코드는 거의 해줄게 없다.
WebSocket 객체에 onopen, onmessage, onclose callback 함수만 걸어놓고 그 안에서 필요한 처리만 해주면 된다.
테스트
Front-end 파일(websocket.html)이 있는 곳에서 다음과 같이 웹 서버를 실행한다.
웹서버로는 python으로 구현된 SimpleHTTPServer를 이용했다. (기본설치되어 있었음. 없으면 설치해야....)
python -m SimpleHTTPServer 8888
그리고, Back-end(ws_server.js) 파일이 있는 곳에서 자신이 만든 echo 서버를 실행시킨다.
