NineTwo meet you

벨만 포드 (Bellman-Ford) 단일 시작점 최단 경로 알고리즘 음수 간선 포함 가능 동작 과정 그래프에서 최단 경로가 한 정점을 두 번 지나는 일은 없다. 최단 경로는 최대 V개의 정점을 갖기 때문에 잘해야 V-1개의 간선을 가질 수 있다. 따라서 모든 간선에 대한 완화 과정은 V-1번이면 충분하다. 음수 사이클 판정 완화를 V번 시도하면 된다. 음수 사이클이 존재하지 않다면 V-1번이면 최단 거리를 찾아낼 수 있다. 만일 V번째 완화 과정에서 한번더 완화가 성공한다면 이는 음수 사이클이 존재한다고 생각할 수 있게 된다. static int n; // 정점의 개수 static int m; // 간선의 개수 static ArrayList[] al = new ArrayList[n+1]; // 그래프의..

다익스트라(Dijsktra) 단일 시작점 최단거리 알고리즘 너비 우선 탐색(BFS)과 유사한 형태를 가진 알고리즘 큐 대신 우선순위 큐(PriorityQueue)를 사용해 최단 거리를 기준으로 정점을 배열해 문제를 해결 음수 간선을 포함할 수 없음 동작 과정 출발 노드 방문 및 출발 노트 최소 비용 0으로 초기화 출발 노드 기준 각 노드별 최소 비용 저장 방문하지 않은 노드 중 가장 최소 비용 노드 선택 해당 노드를 거쳐 특정 노드로 가는 경우 고려해 최소 비용 갱신 3,4 반복 1. 기본 그래프 확인 2. 출발 노드 방문 및 출발 노트 최소 비용 0으로 초기화한다. 출발 노드 0의 최소 비용을 0으로 초기화한다. 3. 출발 노드 기준 각 노드별 최소 비용 저장한다. 출발 노드 0을 기준으로 연결된 노드..

DFS(depth-first search)란? 그래프 이론에서 많이 사용되는 탐색 알고리즘 중 하나다. 현재 정점에서 인접한 간선들을 하나씩 점검하다 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라가는 탐색 알고리즘이다. 이전까지 거쳐온 정점을 기억하기 위해서 재귀를 사용한다. 또한 그래프의 모든 정점이 간선을 통해 연결되어 있다는 보장이 없기 때문에 그래프의 전체 구조를 파악하기 위해서 DFS로 풀 수 있는 유명한 문제를 살펴보겠습니다. 위상 정렬(topological sort) 그래프의 순서를 정렬하기 위한 방법이다. 각 정점의 의존 관계를 간선으로 표현한 의존성 그래프(dependency graph)의 순서를 나타내기 위해 사용된다. 이 그래프의 가장 큰 특징은 사이클이 없..

port 번호 동일한 Ip주소를 가진 시스템내에서 프로세스를 구분하기 위한 번호다. 0부터 65535까지 16bit의 주소로 되어있다. 0 ~ 1023 흔히 well - known 포트로 알려진 system port이다. 잘알려진 서비스들이 주로 사용한다. 1024 ~ 49151 registerd 포트로 user port다. 응용프로그램들이 주로 사용한다. 49152 ~ 65535 Dynamic 포트로 주로 접속하는 용도로 사용된다. port번호 확인 각각 os에 다음과 같은 경로에서 port번호를 확인할 수 있다. 리눅스 /etc/service 윈도우 C:\Windows\System32\drivers\etc\servises 윈도우에서 확인한 port번호 더보기 # Copyright (c) 1993-20..

명령어를 이용한 압축 및 해제 compress gzip 압축 compress -v 압축할파일명 해제 uncompress 압축한파일명 확장자 .Z 압축 gzip -v 압축할파일명 해제 gunzip 압축한파일명 확장자 .gz 거의 사용하지 않고 패키지 설치해야한다. 압축시 원본이 사라진다. 해제시 압축했던 파일이 사라진다. 많이 사용한다. 압축시 원본이 사라진다. 해제시 압축했던 파일이 사라진다. bzip2 zip 압축 bzip2 -v 압축할파일명 해제 bunzip2 압축한파일명 확장자 .bz2 압축 zip -v 압출할파일명 압축할파일목록 해제 unzip 압축한파일명 확장자 .zip gzip보다는 적게 사용한다. 압축시 원본이 사라진다. 해제시 압축했던 파일이 사라진다. 거의 사용하지 않는다. 압축했던 원본..

아카이브 여러개의 파일들을 하나로 묶는 기술이다. 하지만 용량은 줄지 않는다. tar tar 기능옵션(s) 아카이브파일명 묶을파일목록(s) 기능 옵션 (-안붙임) 기능 설명 c 새로운 tar 파일을 생성합니다. t tar 파일의 내부 내용들의 리스트를 확인합니다. x tar 파일을 해체합니다. f 아카이브 파일이나 테이프 장치를 지정하며 항상 옵션 마지막에 입력해야 합니다. 만일 아카이브 파일을 '-'로 지정하였으면 이는 tar 명령어가 tar 파일로부터 standard input으로 읽어들이거나, standard output으로 tar파일을 생성한다는 것을 의미합니다. v tar 명령어 수행과정을 자세히 출력합니다. h 아카이브 하려는 파일이 심볼릭링크파일인 경우 원본을 아카이브합니다. 생성 원본 파일..

프로세스 프로세스는 실행된 프로그램을 의미합니다. 프로세스 종류 항목 설명 부모 프로세스 다른 프로세스를 생성 할 수 있는 프로세스 자식 프로세스 부모 프로세스로부터 만들어지는 프로세스 데몬 프로세스 일반적으로 사용자가 직접 실행시키지 않고 파일이름 끝에 d를 붙여서 사용 커널에 의해 구동되며 백그라운드에서 특정 서비스를 구성하기 위해 구동 고아 프로세스 자식 프로세스는 작업이 종료되면 부모 프로세스로 돌아가는데 돌아가기 전 부모 프로세스가 종료된 경우를 의미 init프로세스가 해당 프로세스가 종료될 수 있게 도움 좀비 프로세스 자식 프로세스가 종료를 위해 프로세스 리스트라 불리는 목록에서 종료 승인을 대기 하고 있는 상태의 프로세스 시스텝에 존재하는 리소스를 반납하지 않은 상태로리스트에 남아있는 프로세..

쉘 스크립트 기본적으로 시스템 명령어와 프로그래밍 구문으로 이루어져 있다. 쉘 프로그래밍을 사용하면 반복적인 작업을 자동화할 수 있다. 프로그래밍 언어 쉘 스크립트 언어 소스파일 -> 컴파일 -> exe 실행 파일 소스파일 -> 인터프리터가 즉시 명령 수행 스크립트 언어에 비해 빠르고 강력함 인터프리터가 즉시 실행해 사용이 용이함 소스코드를 실행파일로 변환하기 위해 컴파일을 거쳐야 함 프로그래밍 언어에 비해 느리고, 강력한 기능 구현에는 한계 존재 C , ... shell script , python script , ... 쉘 스크립트 실행 sh $sh 스크립트파일명 chmod $chmod +x 스크립트파일명 $./스크립트파일명 변수의 종류 종류 설명 환경 변수 쉘 환경과 관련된 정보를 저장하는 변수로 ..

메타 문자 쉘에서 특별한 의미를 가지는 일반 기호를 의미한다. 경로 이름 메타 문자 ~ 현재 로그인된 사용자의 홈디렉토리를 의미한다. cd ~ 현재 사용자의 작업 디렉토리로 이동 cd ~userA userA라는 사용자의 작업 디렉토리로 이동 cd ~+ 현재 작업 디렉토리를 이동 cd ~- 이전 작업 디렉토리로 이동 - 이전 작업 디렉토리를 의미 파일 이름 대체 메타 문자 * 아무것도 없거나 하나 이상의 문자를 대체하는 문자로 사용됩니다. ? 하나의 문자를 대체하는 문자로 사용됩니다. [] 하나의 문자를 대체하는 문자의 범위를 지정할 수 있으며 검색용으로 사용된다. [문자1-문자3] ls file[A-Z] 연속된 문자를 검색시 사용한다. fileA, ... fileZ까지 검색된다. [문자1문자2...] l..

퍼미션 유닉스/리눅스 시스템의 모든 파일과 디렉터리는 퍼미션들의 집합으로 구성되어있으며 다중 사용자 환경에서 이는 가장 기초적인 보안 방법이라 할 수 있다. 퍼미션은 시스템상에 존재하는 파일에 대한 읽기, 쓰기, 실행에 대한 접근부여 여부를 결정하며 ls -l과 ls -n명령으로 확인 할 수 있다. 파일의 속성 속성 설명 - regular file 일반 파일로 바이너리 파일이거나 아스키 텍스트 파일입니다. d directory file 디레토리 파일입니다. b block device file 블록 장치 파일입니다. c character device file 캐릭터 장치 파일 즉 원시 장치 파일입니다. D Door file 도어 파일 입니다. s socket file 소켓 파일 입니다. l symbolic..