[1]

BFS(너비우선탐색) 알고리즘은 보통의 경우 tree나 graph의 노드들을 탐색하기 위해

queue 자료구조를 이용해 아래와 같은 순서로 동작한다.


1. queue가 비어있는지 확인한다. 비어있으면 종료한다.

2. 비어있지 않다면 queue의 head를 pop해 현재 노드로 접근한다.

3. 현재 노드에서 이동가능한 노드들 중 아직 방문하지 않은 노드를 queue에 push한다.

4. 1번으로 돌아간다.


[2]

하지만 여기서 queue에 push하는 조건을 아래와 같이 바꾸면 최단 거리를 구하는데 사용할 수 있다.


현재 노드에서 방문 가능한 노드 중 아직 방문하지 않은 노드

=>  현재 노드에서 방문 가능하고 (기존에 계산한 출발지에서 다음 노드까지의 거리)보다 (출발지에서 현재 노드까지의 거리 + 현재 노드에서 다음 노드까지의 거리)가 더 짧은 경우


위와 같은 방법을 사용하면 처음 queue에 넣은 노드로부터 접근 가능한 모든 노드들까지의 거리를 계산할 수 있게 된다.


하지만 위와 같은 방법을 사용하기 위해서는 기존의 방법에 비해 추가로 데이터가 필요하다.


출발지 노드로부터 다른 각 노드들까지의 거리를 저장하는 데이터가 필요하다.


초기에는 자기 자신까지의 거리는 0이며 다른 노드들까지의 거리는 무한대이지만 bfsf를 수행하면서 다른 노드들까지의 거리를 계속해서 업데이트 해주어야 한다. 그리고 더 이상 각각의 다른 노드들까지의 거리가 업데이트 되지 않는 시점에 알고리즘은 종료하게 될 것이다.


1. queue가 비어있는지 확인한다. 비어있으면 종료한다.

2. 비어있지 않다면 queue의 head를 pop해 현재 노드로 접근한다.

3. 현재 노드에서 이동가능한 노드들 중 (기존에 계산한 출발지에서 다음 노드까지의 거리)보다 (출발지에서 현재 노드까지의 거리 + 현재 노드에서 다음 노드까지의 거리)가 더 짧은 경우 해당 다음 노드를 queue에 push한다.

4. 다음 노드까지의 거리를 업데이트한다.

5. 1번으로 돌아간다.


[3]

여기서 위의 최단거리 계산 방법을 응용하면 또 다른 최단거리를 계산할 수 있다.


위의 조건을 아래와 같이 조금 수정해


(기존에 계산된 현재 노드에 접근이 가능한 다른 노드들부터 목적지까지의 거리) > (현재 노드부터 목적지까지의 거리 + 현재 노드에 접근이 가능한 노드부터 현재 노드까지의 거리)


인 경우에 queue에 넣도록한다면


위에서의 최단 거리가 처음 시작하는 노드로부터 다른 노드들까지의 거리를 계산한 것이라면


자기 자신을 제외한 다른 모든 노드들로부터 자기 자신까지의 거리를 계산하는 알고리즘이 된다.

'Computer > algorithm' 카테고리의 다른 글

BFS를 이용해 최단거리 구하기  (0) 2018.06.12

 virtual Box에 우분투를 설치하고 처음 실행하면 우분투의 해상도가 (800 * 600)인가로 고정이 되어서 화면이 굉장히 작고 설정창에서도 해상도 변경이 불가능한 상태로 되어있어서 굉장히 불편한데요. 이러한 문제는 virtual box에 게스트 확장 설치가 되어있지 않아서 발생한다고 합니다. 게스트 확장 설치 방법은 아래와 같습니다.


1. 우선 virtual box에서 우분투를 실행합니다.


2. 우분투의 부팅이 끝나면 아래 캡쳐화면과 같이 '장치 -> 게스트 확장 CD 이미지 삽입'을 클릭합니다.



3. 게스트 확장 설치에 필요한 권한을 얻기 위해 패스워드를 입력하라는 창이 뜨는데 우분투를 설치하면서 설정했던 비밀번호를 입력하시면 됩니다.


4. 터미널 창이 뜨면서 설치가 되는 과정이 출력되는데 설치가 끝난 후 터미널에 재시작하라는 메시지가 우분투를 재시작하시면 됩니다.


5. 재시작 후 부팅이 완료되면 달라진 화면을 보실 수 있습니다.


끝.


1. 자바로 작성된 코드를 컴파일해 바이트코드를 생성하기 위해선 우선 JDK가 필요하다.


JDK(Java Development Kit)는 자바 개발도구로써 자바를 이용해 개발하는데 필요한 프로그램들이 포함되어 있다.


 - JDK는 JVM(Java Virtual Machine, 자바가상머신), 자바클래스 라이브러리(Java API) 등을 포함하고 있다.



<구글에서 jdk로 검색하면 쉽게 jdk를 받을 수 있는 오라클 페이지로 갈 수 있다.>

http://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151.html


 - jdk는 자신의 컴퓨터 환경에 맞는 버전으로 다운받아야한다.

 예를 들어, 내 컴퓨터는 Windows8 64비트 운영체제이기 때문에 Windows x64버전을 다운받으면 된다.


2. JDK의 설치가 끝났다면 설치된 디렉토리의 bin디렉토리를 path에 추가해야한다. 


   (bin 디렉토리에는 자바로 개발하는데 필요한 주요 파일들이 들어있다.

    - javac.exe : 자바 컴파일러, 자바로 작성된 소스코드를 바이트코드로 변환한다.

    - java.exe : 자바 인터프리터, 바이트코드를 실행한다.

    - javap.exe : 역어셈블러, 컴파일된 클래스 파일을 원래의 소스로 변환한다.)


추가방법은 우선 제어판에서 시스템 항목을 찾아 들어가도록 한다. 아래와 같은 화면을 볼 수 있다.

(가지고 있는 노트북이 윈8이기 때문에 윈8 기준으로 설명했다.)



위와 같은 화면에서 오른쪽 아래쯤 보이는 설정 변경을 클릭한다.



그럼 위와 같은 화면을 볼 수 있는데 여기에서 고급탭을 선택하고 환경 변수를 클릭한다.



사용자 변수와 시스템 변수가 있는데 밑의 시스템 변수 에서 변수 이름이 Path인걸 찾고 편집을 눌러준다.



이제 변수값의 맨 뒤에 세미콜론( ; )을 붙여주고 bin폴더의 경로를 추가해준다.

예를 들어 내 경우엔 C:\Program Files\Java\jdk1.7.0_75\bin


그럼 이제 자바소스코드를 컴파일 할 수 있는 환경 설정은 끝이 났다.


3. 마지막으로 우리가 할 것은 자바소스코드를 작성하고 컴파일해보는 일.


소스 작성은 어느 텍스트 편집기를 사용하든 크게 상관은 없지만 개인적으로는 Notepad++이라는 편집기를 추천한다.

가볍고 간편한 느낌이 괜찮은 프로그램이고 무엇보다 공짜다.


<구글에서 notepad++로 검색하면 쉽게 다운로드 할 수 있는 페이지로 갈 수 있다.>


그럼 편집기를 이용해 아래와 같이 소스코드를 작성해보자. 무엇보다 저장할 때 확장자는 .java로 하는게 중요하다.



코드를 작성하고 저장했다면 이제 cmd를 실행한다.



cmd에서 저장한 자바소스코드가 있는 위치까지 이동한다.(이동하는 과정은 생략)

해당 위치에서 내 경우엔 위와 같이 test.java라고 되있는 자바소스코드를 확인할 수 있다.

그러면 컴파일을 하기 위해 명령어 javac test.java 라고 입력한다.

잠시 기다리면 다시 프롬프트가 뜰텐데 확인을 해보면 없었던 Hello.class라는 파일이 생긴 것을 확인할 수 있다.

소스코드가 정상적으로 컴파일 되었다는 소리다.

class 파일은 java Hello라는 명령어를 입력해 실행할 수 있다.

그럼 바로 밑에 줄에서 Hello, World라고 뜨면서 작성한 코드가 제대로 실행되는 것을 볼 수 가 있다.


끝.

'Computer > java' 카테고리의 다른 글

cmd를 이용해 Java(자바) 컴파일하기  (3) 2015.02.26
  1. 오옹 2015.09.18 15:16

    안녕하세요 포스팅 잘 봤습니다! 질문을 하나 드리고 싶은데요~제가 cmd로 java compile 및 run을 하려는데요,
    compile은 멀쩡히 가능한데 run을 하려고 java를 입력하면
    Error: could not open 'C:\Program Files\Java\jre8\lib\amd64\jvm.cfg'
    라는 오류 메시지가 뜨고 run이 안 되네요.
    사실 program files에 java 폴더는 존재하지만 이 안에는 jre8 같은 건 아예 존재하지 않거든요. java 프로그램이 들어 있는 디렉토리는 C:\jdk170\bin이고, 이 path는 이미 추가되어 있는데, 왜 run이 안 될까요? 제 생각에는 이 'C:\Program Files\Java\jre8\lib\amd64\jvm.cfg' 라는 경로 자체가 잘못된 것 같고 cmd가 java를 찾기 위해 다른 경로로 접근하게 하고 싶은데, 어떻게 하면 좋을까요?ㅠㅠ 빠른 답변 부탁드려요!

    • 죄진 Zerodark 2015.09.19 18:22 신고

      제가 오옹님의 컴퓨터 상태를 직접 본게 아니라서 정확한 답변은 드리가 힘들지만 자바 설치가 제대로 되지 않은 것 같아요. 완벽하게 삭제하시고 다시 설치하시는게 나을 것 같네요. 아래 링크에서 참고하시면 될거 같고요. (http://stackoverflow.com/questions/9051103/java-path-error-of-jvm-cfg)
      재설치가 부담스러우시면 이게 지금 경로 지정이 문제인 것 같은데 javac.exe와 java.exe 파일이 있는 C:\\Program Files\\Java\\jdk1.8.0_60\\bin 에 소스 코드를 이동시켜서 아래 제가 한 방법으로 하시면 재설치를 안하셔도 되지 않을까 싶네요 ㅠ
      도움이 됬음 좋겠습니다.
      ---------------------------------------------------
      C:\\Program Files\\Java\\jdk1.8.0_60\\bin>javac.exe hello.java

      C:\\Program Files\\Java\\jdk1.8.0_60\\bin>java.exe Hello
      Hello, World.
      ---------------------------------------------------
      * 아 그리고 저 폴더 내에서 cmd를 사용하시려면 반드시 관리자 권한이 있는 cmd를 사용하셔야 합니다.

  2. 정보 참고합니다. 2017.07.10 19:21

    감사합니다.

1. 리눅스(우분투) 설치


 가장 먼저 해야할 일은 역시 리눅스를 설치하는 일입니다.

 저는 여러 리눅스 중 우분투를 선택해서 설치해서 사용했구요..  제가 사용한 우분투 버전은 ubuntu-14.04.1-desktop-amd64 입니다.


 - 우분투 리눅스 : http://www.ubuntu.com/

 - VirtualBox : https://www.virtualbox.org/



2. 리눅스 환경 설정


 우분투의 설치가 끝난 이후에는 terminal을 실행시켜 아래와 같은 작업들을 해줍니다.

 

 (1) 첫번째로 sudo -s 명령어를 입력해 root 권한을 획득합니다.

     이때 2번째 빨간 밑줄과 같이 패스워드를 입력하라고 나오는데 우분투를 처음 설치하시면서 설정하셨던 패스워드를 입력하시면 됩니다.

     리눅스의 특징상 패스워드를 입력해도 아무것도 출력되지 않습니다.


 (2) 그 다음엔 sudo apt-get install ssh 명령을 입력해 우분투에 ssh를 설치해야합니다.



 (3) 명령어를 제대로 입력하면 터미널에 이런저런 말들이 많이 뜨는데요. 아래와 같은 물음이 나오면 Y y 를 입력해서 계속 진행합니다.



 (4) ssh의 설치가 끝나면 다시 명령어를 입력할 수 있는 프롬프트 메시지가 출력될거에요.

     그러면 이번에는 sudo apt-get install openssh-server 명령어를 입력해 openssh-server를 설치해줍니다.

     이 부분은 이전에 ssh를 설치하면서 이미 설치가 된 부분인 것 같지만 그래도 확인하는 겸 해보았습니다.

     뭔가 already the newest version 같은 메시지가 출력되는 걸 보면 이미 설치가 된게 맞는거 같네요 ㅋㅋ..



 (5) 설치가 된 ssh를 sudo /etc/init.d/ssh restart 명령어를 통해 재시작시켜줍니다.(/etc/init.d/ssh 는 절대경로에서의 ssh의 위치입니다.)

      그 다음에는 ifconfig 명령어를 통해 우분투의 ip주소를 확인해주어야하는데요. 아래에서 보시면 ip주소 형식을 따르는 inet addr가 10.0.2.15,

      127.0.0.1 두 개가 존재합니다. 하지만 여기서 저희에게 필요한 주소는 Link encap:Local Loopback 바로 밑에 있는 127.0.0.1 입니다.

      (127.0.0.1은 루프백 주소라고 하는데요. 자기 자신에게 패킷을 보낼 때 사용하는 주소라고 생각하시면 됩니다.)




3. 포트 포워딩(Port forwarding)


 포트 포워딩 방법을 설명하기 전에 포트 포워딩에 대해 좀 설명을 드리려고해요.

 우선 우리가 111.111.111.111 이라는 ip로 패킷을 전송한다고 가정해 볼게요.

 111.111.111.111의 ip주소를 가지고 있는 컴퓨터는 그 패킷을 받게 될 겁니다. 하지만 여기서 문제는 그 패킷을 어떻게 할거냐는 겁니다. 패킷은 어떤 정보를 담고 있는건데 그 정보를 어느 프로세스에게 보내야할 것이냐 이것을 결정해야 한다는 겁니다.

 그래서 그 패킷을 받을 프로세스를 결정해주어야 하는데 그걸 결정하는 번호가 바로 포트 번호입니다. 그렇기 때문에 네트워크에서 패킷을 보낼때는 보내는 쪽의 ip주소와 포트번호가 필요하고 받는 쪽의 ip주소와 포트번호가 있어야지만 패킷을 전송할 수 있습니다.

 포트 포워딩은 결국 특정 ip주소와 포트번호의 패킷을 받았을 때 그 패킷을 받을 특정 프로세스를 사용자가 미리 설정한 포트 번호를 통해 지정해주는 것을 의미한다고 할 수 있습니다.


 포트 포워딩은 설정은 virtualbox에서 해줘야합니다. virtualbox에서 설치한 우분투를 오른쪽 클릭하면 설정으로 들어가실 수 있는데요.

 거시서 네트워크 탭을 선택하시면 아래와 같은 화면의 중앙 아래쪽에서 포트 포워딩이라는 버튼을 보실 수 있습니다.(클릭해주세요 ㅋ)



 그러면 + 버튼을 눌러 포트 포워딩 규칙을 추가해주시고 호스트 ip는 127.0.0.1, 호스트 포트는 22, 게스트 포트는 22를 입력해줍니다.



이렇게 하시면 포트 포워딩 설정도 끝이 납니다.



4. 푸티를 이용한 접속


 그러면 마지막으로 푸티를 이용해 우분투에 접속을 해보겠습니다. 우선 푸티가 필요하겠죠???(첨부파일도 해두었습니다.)

 

 - putty : http://www.chiark.greenend.org.uk/~sgtatham/putty/download.html


 푸티를 실행하면 아래와 같은 화면이 나오게 되는데 host name(ip address)과 port, connection type을 아래와 같이 설정해주시고 Open 버튼을 클릭해 우분투에 접속해주시면 됩니다.(물론 우분투는 virtualbox를 통해 실행되어있는 상태여야 합니다.)

 => 127.0.0.1에 22이라는건 결국 자기자신의 22번 포트에 ssh 형식으로 접속하겠다는게 되는겁니다. 22번 포트에는 virtualbox를 통해 우분투를 등록해 놓았고 자기자신인 127.0.0.1로부터 패킷을 받은 컴퓨터는 22번 포트인 virtualbox의 우분투로 패킷을 보내게 될 겁니다.



putty.exe


 저는 실행했더니 아래와 같은 보안 알림 창이 뜨긴했는데 그냥 예 하시면 될거같아요ㅋㅋ...



 그리고 모든 과정이 끝나고 푸티를 통해 우분투에 접속을 성공한 모습입니다. login as: 라고 나오면 우분투 등록되어있는 사용자 중에 접속을 원하는 사용자 id를 입력하면 되고 저같은 경우는 euijin입니다. password도 우분투 접속할 때와 같이 입력해주시면 되고요. 그리고 명령어 프롬프트 메시지가 출력이 되면 콘솔환경에서 리눅스를 사용하실 수 있습니다.



- 끝 -


* 잘못된 정보나 오타에 대해서 지적해 주시면 빠른 시일내에 수정하도록 하겠습니다.

  1. 핫벅 2015.01.23 17:44

    감사합니다!!!

  2. 박재완 2016.03.06 00:44

    좋은 정보 감사합니다. 저는 칼리 로 하고 있습니다. 그런데 비밀번호 입력에서 자꾸 틀리다고 하는데 들어가는 과정에서 썻던 비밀번호 그대로 사용하는거죠?!

    • PaPhoPu 2016.03.06 22:39

      지나가던 사람입니다.
      원격으로 접속하실 운영체제에 들어있는 계정과 비밀번호를 입력하시면됩니다.
      쉽게말해서 컴퓨터 키면 비밀번호 쳐야되는데 그거 똑같이 넣으시면 됩니다.

  3. Ahran Kim 2016.06.03 17:42

    정말 감사합니다. 완전 속 시원하게 해결되었어요

  4. 질문자 2016.09.11 23:03

    안녕하세요 전 우분투 VMWARE Wprkstaion 을 사용하고 있는데 설정 창 이 좀 달른데 어떻게 해야 되나요??

    • 죄진 Zerodark 2016.09.11 23:05 신고

      우선 우분투에서 ssh 설치는 그대로 하시면 될것같고요. vmware에서 사용하는 네트워크 설정 창에서 NAT설정과 포트포워딩 설정을 동일하게 해주시면 될것같습니다. 자세한 내용은 제가 VMware를 사용하지 않아서 알려드리지 못할것같습니다 ㅠ 죄송합니다.

  5. Anthony 2016.12.04 16:23

    잘 보고, 참고하고 갑니다. 감사합니다!

- 유클리드 알고리즘(Euclideans Algorithm)

  : a, b, q, r 이 정수라고 가정할 때

    a = b * q + r  =>  gcd(a,b) = gcd(b,r)

    의 원리를 이용해 a,b의 최대공약수를 구한다.


- C/C++소스코드

#include <stdio.h>


int Eucl(int, int); //유클리드 알고리즘을 구현한 함수의 정의


int main(void){

int a, b, big; // a, b 입력받을 정수, big 수를 비교할 사용할 변수

int gcm; // 유클리드 알고리즘 함수의 반환값을 받기 위한 변수

scanf_s("%d %d", &a, &b); // a, b 두수를 입력 받는다.

   

if (a>b){ // a, b 비교해서 b쪽에 수가 오도록 정렬하는 조건문

big = a;

a = b;

b = big;

}


printf("%d", gcm = Eucl(a, b));

return 0;

}


int Eucl(int a, int b){

int remain; // 나머지를 받기 저장하기 위한 변수

remain = b%a; // b a 나눈 나머지를 remain 저장한다.


if (remain == 0) // remain 0이라는 것은 a a, b  최대공약수라는 것을 의미한다.
    return a;
else

return Eucl(remain, a); // 최대공약수를 찾지 못했으므로 유클리드 알고리즘을 반복한다.

}


+ Recent posts