룰루랄라 알고리즘

Graph 완전 그래프 Edge의 수가 최대인 그래프 n개의 vertex 일 때 최대 edge 수 : n(n-1)/2 경로의 길이 경로 상에 있는 edge의 수 단순 경로(simple path) 처음과 마지막을 제외한 vertex가 다른 경로 그래프 표현 방법 분석 G에 존재하는 edge 수 검사, or G가 연결되었는지 검사 인접 행렬 : n(n-1)/2 개의 항 조사 -> O(n^2) 인접 리스트 : O(n+e) Digraph에서 vertex의 in-degree 조사 인접 행렬 : O(n) 인접 리스트 : O(n+e) DFS (깊이 우선 탐색) 로직 1. 출발 정점 v의 인접 리스트부터 방문 2. v에 인접하면서 아직 방문하지 않은 정점 w를 선택 3. w를 시작점으로 하여 다시 dfs 시작 4. r..

전 세계 컴퓨터의 70%는 정렬을 하는데 시간을 보내고 있다 할 정도로 중요하고, 값 비싼 연산인 정렬을 파헤쳐보자. 전 세계 컴퓨터 공학자들의 Bible로 불리는 C로 쓴 자료구조의 높은 퀄리티의 코드를 하나하나 씹어 먹어보자! (Y 대학 Prof. Cho의 강의력과 학생들을 향한 헌신에 감사하며 작성하는 글입니다.) Insertion Sort (삽입 정렬) Time Complexity 최선 평균 최악 Space Complexity Stable Insertion n n^2 n^2 1 Yes 대부분의 데이터가 sorting 되어 있을 경우 효과적이다. 데이터가 역순으로 sorting 되었을 때 최악의 성능 데이터 수가 n개일 때 성능 최선 최악 비교 n n^2 / 2 교환 0 n^2 / 2 삽입 정렬의 ..

프로세스 생성 fork() 부모 프로세스를 똑같이 복제하여 새로운 자식 프로세스를 생성 새로운 프로세스를 생성하는 유일한 방법 코드, 데이터, 스택, 힙 등을 똑같이 복제 fork()는 한 번 호출되면 두 번 리턴함 (호출 후에는 프로세서가 둘이기 때문에) #include #include pid_t fork(void); //새로운 자식 프로세스를 생성 //자식 프로세스에게는 0 //부모 프로세스에게는 자식 프로세스 ID를 리턴 자식은 부모의 fd 테이블을 복사한다 자식에게 상속되지 않는 성질 fork()의 반환 값 프로세스 ID 파일 잠금 속성 설정된 알람과 시그널 fork1.c 자식 프로세스를 생성하는 코드를 짠 후 프로세스의 실행 결과를 확인해 보자 #include #include /* 자식 프로세스..

패키지 클래스와 인터페이스가 너무 많아지면 관리 하기 어렵고, 중복되지 않게 이름 붙이기도 어려움. 클래스나 인터페이스의 컴파일된 클래스(.class) 파일들을 하나의 디렉토리에 묶어 놓은 것. 계산기 프로그램 위와 같이 PackageEx 라이브러리에 서로 다른 패키지 app, lib를 만들고 각각 GoodCalc, Calculator를 작성하여 계산기 프로그램을 만들어보자! Calculator 클래스 추상 클래스 Calculator을 lib 패키지에 선언 package lib; public abstract class Calculator { public abstract int add(int a, int b); public abstract int subtract(int a, int b); public ab..

다중 상속이 가능한 인터페이스를 활용하여 도서 관리 프로그램을 작성해 보자 Lendable 인터페이스 CheckIn, CheckOut 함수를 추상 메소드로 가지는 대출가능 관리 인터페이스 Lendable 선언 public interface Lendable { final static byte BORROWED = 1; //상수지정 final static byte NORMAL = 0; abstract void checkOut(String borrower, String date) throws Exception; //abstract 생략가능, 추상메소드에는 public 생략가능 abstract void checkIn(); } CDInfo 클래스 CD 정보를 가지는 클래스 public class CDInfo { S..

Interface Java는 클래스의 다중 상속을 허용하지 않기 때문에 다중 상속 기능이 필요한 경우에 클래스 대신 interface를 활용하여 구현한다. interface의 특징 멤버는 추상 메소드와 상수로만 구성된다. 모든 메소드는 추상 메소드이며 선언시 abstract 생략 가능 모든 메소드는 public이며 선언시 public 생략가능 상수도 public static final을 생략하여 선언할 수 있음 인터페이스의 객체를 생성할 수 없다. 다른 인터페이스에 상속될 수 있다. public interface Clock { public static final int ONEDAY = 24; abstract public int getMinute (); abstract public int getHour (..

상속과 추상 클래스를 활용하여 다양한 메시지 전송 프로그램을 작성해보자. 추상 클래스 MsgSender 메세지 전송의 기본적인 기능을 가지는 MsgSender를 추상 클래스로 선언 abstract class MsgSender { String title; String sendName; public MsgSender(String title, String sendName) { this.title = title; this.sendName = sendName; } abstract void sendMsg(String recipnt); } EmailSender 클래스 추상 클래스인 MsgSender를 상속받아 데이터 필드를 추가하고 sendMsg 함수의 구체적인 기능을 구현하는 EmailSender 클래스 생성 pu..

상속을 활용하여 다양한 계좌 프로그램을 작성해보자. Account 클래스 가장 기본 계좌 클래스인 Account.java 작성 public class Account { //final을 추가하면 상속이 금지됨 //abstract를 추가하면 객체가 추상화 되어 상속등 활용은 가능하지만 그자체의 객체 생성은 하지 못한다 String accountNo; String ownName; int bal; Account(String accountNO, String ownName, int bal){ this.accountNo = accountNO; this.ownName = ownName; this.bal = bal; } void printAccount() { System.out.println("계좌번호: " + acco..

프로세스 리눅스에서 프로그램이 실행되는 과정 사용자가 프로그램을 쉘 프롬프트에서 지정하여 실행 : 내부적으로 현재 실행 중인 프로그램(shell) 내에서 fork() & exec() 시스템 호출을 통해 새로운 프로그램이 실행됨 C 시작 루틴 : 컴파일러가 실행 파일에 C 시작 루틴을 포함 시킴. 이 루틴은 exec로부터 전달받은 명령줄 인수, 환경 변수를 main 함수로 전달하는 역할을 수행함 프로그램 실행 종료 Main 함수의 실행이 끝나면 exit( main (argc, argv) )를 호출 C 시작 루틴은 프로그램의 실행이 끝나면 main 함수로 부터 반환 값을 받아 exit 한다. 정상 종료 : Main 함수 return 0 -> C 시작 루틴이 Exit(0) 을 호출 -> 커널 수행 - > sc..

파일 시스템 물리적으로 디스크 혹은 다양한 저장장치들로 구성된 저장공간을 논리적 형태로 변환시켜 관리하며 사용자가 이를 접근하여 사용할 수 있도록 해준다. df : 파일 시스템에 대한 디스크 사용 정보를 보여준다. du [-s] 파일명* : 파일 혹은 디렉토리의 사용량을 보여준다. 파일을 명시하지 않으면 현재 디렉토리 내의 모든 파일들의 사용 공간을 보여준다. 파일 시스템 구조 부트 블록 : 파일 시스템 시작부에 위치하고 보통 첫 번째 섹터에 위치. 부트 스트랩 코드가 저장되는 블록 슈퍼 블록 : 전체 파일 시스템에 대한 정보를 저장 (총 블록수, 사용 가능한 i-노드 개수, 사용 가능한 블록 비트 맵, 블록의 크기, 사용 중인 블록 수, 사용 가능한 블록수 ) i-리스트 : 각 파일을 나타내는 모든 i..