Chap12 그래프, 그래프 탐색 1. 그래프의 개념 그래프 G1의 노드 V(G1) = {0,1,2,3,4} 그래프 G1의 간선 E(G1) = {(0,1) ..} ()는 무방향. {..} 는 방향이 있는 간선. G1은 방향그래프. 분리된 그래프 : 모든 루트가 연결되어있지 않고 분리되어있지만 하나의 그래프임. 연결된 그래프 용어 정리 완전 그래프 : 간선 수가 최대. 모든 각 노드에 모든 노드로의 간선이 존재. 완전그래프인 방향그래프에 n개의 노드가 있으면 간선의 수는 n(n-1), 무방향이면 n(n-1)/2 인접 : 두 노드를 직접 연결하는 간선이 존재하면 두 노드는 인접하다고 함 부속 : 두 노드를 직접 연결하는 간선이 존재하면 그 간선에 양쪽 노드가 부속된다고 함. 부분 그래프 : 그래프의 간선들과..
전체 글
삼시세끼 잔잔하게 개발하는 프로그래밍 수련기 : Spring boot, Algorithm, AndroidChap11 검색(탐색) 선형 검색 앞에서부터 하나씩 찾아봄 이진 검색 절반씩 잘라서 중간값을 탐색해나가는 방법 해시 탐색 해시테이블(크기 = 버킷*슬롯) 버킷 : 해시될 키 값의 범위. 해시함수에 들어갔다 나온 값이 같으면(동의어) 같은 버킷에 저장됨 슬롯 : 같은 버킷에 저장될 수 있는 키 값 개수 충돌 : 동의어가 나타나서 다른 값이 같은 버킷에 저장되는 경우 오버플로우 : 충돌로 저장하려는 값의 슬롯이 이미 꽉 찬 경우 오버플로우가 일어남 식별자밀도=적재밀도 : 같은 말. 테이블 크기에 비해 저장된 데이터 수 비율을 의미.(키값=식별자=데이터) 해시 함수 : 계산이 편해야 하고 충돌을 최소화할 수록 좋음. mid-square : 식별자를 제곱해서 가운데 부분 값을 사용함 division : 나머지..
Chap10 정렬 선택 정렬 첫번째 자리에 올 값, 두번째 자리에 올 값.. 순서로 탐색해서 발견 시 해당 위치의 값과 자리 교환 비교 n(n-1)/2 회 교환 n-1 회 => O(n^2) 버블 정렬 맨 첫 값부터 바로 옆 값과 비교해 교환할지 말지 결정. 끝까지 가면 마지막 값부터 정렬 완료됨. 반복 비교 n(n-1)/2 회 교환 n(n-1)/2 회 (최악 : 비교할 때마다 교환) => O(n^2) 개선 - 중간 단계에서 정렬 완료된 경우. 현 단계에서 데이터 이동이 일어나지 않으면 다음 단계들을 수행하지 않고 종료 삽입 정렬 앞에서부터 현재 값을 앞쪽이 이미 정렬되어있는 값들 사이의 알맞은 위치에 삽입함(삽입하는 과정은 현재 위치에서 바로 앞 값과 비교해서 교환 결정하며 앞쪽으로 보냄. 계속 비교 교..
Chap8 트리 트리 삽입삭제가 편함 이진검색의 장점을 이용해 빠른 검색 가능 루트의 레벨 = 1 차수 : 노드의 부속트리 개수. 리프노드는 차수가 0임 부모, 자식, 조상, 자손 관계 등.. 트리 저장(구현)방법 n-링크표현법 모든 노드에 무조건 n개의 링크를 두고 각 자식노드의 링크를 저장함(남는 공간 있음) 왼쪽자식노드-오늘쪽형제노드 표현법 모든 노드에 링크 두개씩. - 효율적 왼쪽링크에는 첫번째 자식노드, 오른쪽 링크에는 자신의 형제노드를 연결함 차수가 n인 어떤 트리라도 이 방법을 이용하면 이진트리형태로 저장해 낭비되는 공간을 줄일 수 있음(간선을 다시 그리고 시계방향으로 45도 정도 돌림) 이진트리 자식노드의 수가 2개 이하(0~2개)인 트리 자식노드에 순서가 있음 - 똑같이 자식노드가 1개라..
3. Branch&Bound 분기한정법 State Space Tree활용 최적해 구하기에 적용 가능. Backtracking보다는 최적해를 구하기 위해 모든 해의 한계값(직접x)을 계산해 고려함. 각 노드에 대한 한계값bound을 계산함. 해당 노드는 bound보다 큰 값을 가질 확률이 없음. bound값이 지금까지의 최적해보다 좋은가?로 최적해 값을 업데이트하고 노드의 promising여부를 판단함. promising하지 않은 노드의 자식노드는 탐색하지 않음. 0-1 Knapsack 문제 state space tree : 왼쪽으로 가면 현재 아이템을 담지 않는 걸로, 오른쪽으로 가면 현재 아이템을 담는 걸로 함. 루트에서 리프노드까지의 모든 경로가 해답후보임 최적해를 찾는 문제이므로 전체를 다 탐색하기..
2. BackTracking 백트래킹(되추적) 막히면 왔던 길을 되돌아가서 다시 찾는다 최적화 문제와 결정 문제(yes/no) 해결 우리가 해줄 것은 해가 만족해야 하는 조건bound정하기! State Space Tree 활용으로 promising여부 확인(bound) n-Queens문제 n개의 Queen을 한 체스판에 가로세로대각선 방향으로 위치가 겹치지 않도록 배치하는 문제. State Space Tree 상태공간트리 : 문제해결의 중간 사태를 각 노드로 나타낸 트리 루트에서 리프노드까지의 모든 경로가 해답의 후보이며 그 중 답이 되는 경로를 Answer States라 함 답이 나올 가능성이 전혀 없는 노드를 유망하지 않은non-promising 노드, 그렇지 않은 노드를 유망한promising 노드..
미쳐 복습해 기억안나 1. Dynamic Programming 동적 프로그래밍 작은 부분문제들부터 모두 해결한 후 부분 문제들의 해를 이용해 큰 문제를 해결하는 방법(부분 문제들 사이에 의존적) Bottom-up 한 번 구한 값은 절대 바뀌지 않고, 여러번 사용될수 있음 최적성원칙 Principle of Optimality : 최종해는 최적의 부분해들로 이루어져 있어서 최종해 안에 최적의 부분해들이 포함됨 최적성원칙 Principle of Optimality 를 만족하는 문제에서만 동적 프로그래밍 사용 가능 최적화 문제 : 주어진 문제에 대하여 가장 최적인 해답을 찾는 문제 shortest path문제 - all pairs shortest paths 문제(alll to all 알고리즘) 각 정점에서 다른..
Chap9. 소프트웨어 관리 (Chap9중 일부 9.5) 05. 소프트웨어 컴파일 gcc : 기능)C언어 컴파일러 패키지 aptitude show gcc : gcc설치 vi hello.c : hello라는 이름의 c파일 작성 gcc hello.c : hello라는 이름의 c파일 컴파일하기 a.out : 컴파일 후 자동으로 만들어지는 실행파일명 ./a.out : 해당 실행파일 실행하기 **파일 실행 시에는 현재 경로까지 같이 써주어야 함 gcc -o hello hello.c : 컴파일 시 옵션 사용해 실행파일명을 지정할 수 있음 make : 기능) makefile의 내용을 실행함. 이를 활용해 makefile파일에 설정된 정보에 따라 여러 소스 파일을 컴파일해 링크해서 하나의 실행파일로 만들도록 할 수 있..
Chap15. 리눅스 보안의 기초 01. 정보보안의 기초 물리적 / 기술적 / 관리적 보안 : 보안의 다양한 측면 기밀성, 무결성, 가용성 : 보안은 정보를 보호하면서 이 세가지를 유지하는 것 CIA삼각형 Confidentiality기밀성 : 허가받은 사용자만이 접근 가능 Intigrity무결성 : 정보가 변조되지 않았음을 보장하는 것 Availability가용성 : 필요할 때에 허가된 사용자가 정보에 접근할 수 있는 것 보안 기본 조치 불필요한 서비스 통제 : 꼭 필요하지 않은 서비스 포트는 차단. 불필요한 서비스를 제거하거나 방화벽에서 패킷을 필터링하는 방법을 함께 활용하는 것이 바람직 소프트웨어 패치 실시 : 패치가 나오면 즉시 설치하기 주기적 점검 백업 : 주기적으로 하여 문제 발생 시 빠른 복구..
Chap14. NFS, 삼바Samba 01. NFS NFS (Network File System) : 네트워크를 통해 다른 시스템의 디스크를 연결하여 사용하는 것 [서버에서] sudo apt-get install nfs-common nfs-kernel-server rpcbind : NFS패키지 설치. /etc/exports : NFS서버 설정 파일. 클라이언트에 제공할 디렉터리와 클라이언트 주소+NFS옵션을 나열함 chmod 707 /home/share : 클라이언트에 제공할 디렉터리를 만들고 해당 디렉터리의 권한 변경 후 위 파일에 기록 rw : NFS서버 디렉터리에 읽기, 쓰기를 모두 허용한다는 NFS옵션 sudo systemctl restart nfs-kernel-server : NFS서버 재시작 ..
Chap13. DB서버, 웹서버 01. 데이터베이스 데이터베이스 : 관련성을 가진 데이터들을 데이터 간의 주복성을 최소화 해서 체계적으로 모아둔 것 관계형 데이터베이스 : 데이터를 테이블로 표현. SQL(Strudtured Query Language) 로 조작. 데이터 베이스 에는 하나 이상의 테이블들이 있음 필드 = 컬럼column = 열 레코드 = row = 행 = 튜플(터플, tuple) 키 : 각 레코드를 구분할 수 있는 필드값. 중복불가. 기본키PK 등이 있음 varchar(10) / char(10) / int / float / date / date / time : 테이블 필드의 자료형들 varchar(n) : 최대 n개의 크기를 가질 수 있는 가변variable 문자열. char와 달리 현재 ..
Chap12. 원격 접속, FTP 01. 텔넷과 SSH telnet : 기능)원격에서 리눅스에 접속하는 프로그램. 텔넷 서버와 텔넷 클라이언트가 있어야 사용 가능 xinetd : 텔넷 서버를 동작시키는 슈퍼데몬 sudo apt install xinetd, sudo apt-get install telnetd : 데몬과 텔넷서버 설치 /etc/xinetd.conf : 이 파일에서 xinetd의 설정을 함 sudo systemctl start xinetd : 데몬 시작(ps -ef | grep xinetd 로 작동 확인) telnet 0 또는 telnet localhost : localhost(현재 내 컴퓨터)에 있는 텔넷서버에 접속(한 컴 내에 클라이언트와 텔넷서버가 같이 있는 상황. 0말고 0.0.0.0도..
Chap11. 네트워크설정 01. 네트워크 기초 프로토콜 : 컴퓨터 간 데이터를 어떻게 주고받을 것인가에 대한 통신 규약 TCP/IP프로토콜 : 인터넷이 따르는 프로토콜. 5단계 중 전송계층 프로토콜 TCP와 네트워크 계층 프로토콜 IP를 의미. 5계층으로 이루어짐. ATNLP 아래부터 1계층~5계층 Application응용 계층 : 사용자가 사용하는 응용프로그램. (포트번호 : 응용프로그램들을 구별하기 위한 번호).데이터 출발. Transport전송 계층 : 응용프로그램(포트번호 사용)으로 데이터 전달. TCP 프로토콜 사용. 데이터를 패킷으로 자름.(TCP=어떻게자를까). Network네트워크 계층 : 주소 관리, 경로 탐색. IP프로토콜 사용. 패킷별로 서버쪽의 IP주소를 붙임(IP프로토콜의 일) ..
Chap10. 사용자 관리 01 사용자 계정 관련 파일 /etc/passwd 파일 : 사용자 계정 정보 저장 파일 구조 - 로그인 ID : x : UID : GID : 설명 : 홈 디렉터리 : 로그인 셸 GID에는 기본그룹. x는 사용자 암호를 저장하던 곳 (/etc/shadow 파일에 암호 저장) UID가 같으면 리눅스는 같은 사용자로 판단 /etc/shadow 파일 : 사용자 암호 정보 저장 파일 구조 - 로그인 ID : 암호 : 최종변경일 : MIN : MAX : WARNING : INACTIVE : EXPIRE : Flag 한번 변경(설정) 후 MIN날 수 이상, MAX날 수 이하로 사용해야함. WARNING 날 수 전부터 알림. INACTIVE날 수 까지는 날짜가 지나도 사용 가능(봐줌). Fl..