Brute force Study

자바로 프로그램 작성하기 "Hello, world." 출력하기 코드 class Hello { public static void main(String[] args) { System.out.println("Hello, world."); // 화면에 글자를 출력 } } 위 코드를 editor를 통해 작성한 다음 Hello.java로 저장 (이 때, class의 이름 'Hello'가 대소문자까지 정확히 같아야 함) 자바 컴파일러를 통해 소소 코드(Hello.java)로 부터 클래스파일(Hello.class)를 생성 자바 인터프리터로 실행(java.exe) > javac Hello.java > java Hello Hello, world.java 코드 설명 class 클래스 이름 { /* 주석을 제외..

자바(Java Programming Language) 자바란? 썬 마이크로시스템즈에서 개발하여 1996년 발표한 객체지향 프로그래밍 언어 자바의 특징 운영체제(플랫폼)에 독립적이다 자봐로 작성된 프로그램은 운영체제의 종류에 관계없이 실행이 가능함 가비지 컬렉터(garbage collector)가 자동적으로 메모리를 관리해줌 프로그래머가 메모리를 따로 관리하지 않아도 된다. 네트워크와 분산처리, 멀티쓰레드, 동적 로딩(Dynamic Loading)을 지원 JVM(Java Virtual Machine) 일반적인 application의 코드는 OS를 거쳐 하드웨어로 전달 일반 application은 OS와 바로 맞붙어 있기 때문에 OS 종속적 다른 OS에서 실행시키기 위해서는 application을 해당 OS..

스택(Stack)의 응용 - 미로 탐색 미로 탐색 문제 미로에 갇힌 주인공이 출구를 찾는 문제 미로가 서로 연결된 여러 개의 방 또는 칸으로 구성되어 있다고 가정 출구를 찾는 과정 기본적인 방법은 시행착오 방법으로서 하나의 경로를 선택하여 한 번 시도해보고 안되면 다시 다른 경로를 시도 이 때, 현재의 경로가 안 될 경우에 다른 경로를 선택해야 하므로 다른 경로들이 어딘가에 저장되어 있어야 함 현재 위치에서 가능한 경로 중에서 가장 가까운 경로를 저장해야 유리함 가장 최근에 저장한 경로가 쉽게 추출되도록 스택을 사용 현재 위치에서 갈 수 있는 방들의 좌표를 스택에 저장한 후 막다른 길을 만나면 아직 가보지 않은 방 중에서 가장 가까운 방으로 다시 돌아가서 새로운 경로를 찾는다 한 번 지니간 방을 다시 가..

스택(Stack)의 응용 - 후위 표기 수식의 계산 수식 수식은 연산자와 피연산자, 괄호로 이루어져 있음. 연산자들은 우선순위가 있어 우선순위가 높은 연산자가 먼저 계산된다. 컴퓨터는 스택을 이용하여 수식을 계산한다. 중위 / 후위 / 전위 표기 수식 중위 표기 수식 사람들이 일반적으로 수식을 표기하는 방식 연산자가 피연산자 사이에 있으면 중위 표기 수식 후위 표기 수식 연산자가 피연산자 뒤에 있으면 후위 표기 수식 전위 표기 수식 연산자가 피연산자 앞에 있으면 전위 표기 수식 예시 2 + 3 * 4 (중위) 234*+ // 후위 표기 수식 +2*34 // 전위 표기 수식 a * b + 5 (중위) ab*5+ // 후위 표기 수식 +*ab5 // 전위 표기 수식 (1 + 2) * 7 (중위) 12+7* ..

스택(Stack)의 응용 - 괄호 검사 문제 괄호 검사 문제 프로그램에서 괄호들의 쌍이 올바르게 사용되었는지를 판단하는데 스택을 이용 괄호의 검사 조건 3가지 왼쪼 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다. 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다. 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 교차하면 안 된다. example { A [(i + 1)] = 0; } // 오류 X if ((i == 0) && (j == 0) // 오류 : 조건 1 위반 A [ (i + 1] ) = 0; // 오류 : 조건 3 위반 의사 코드 check_matching(expr): while (입력 expr이 끝이 나면): ch top = -1; } // 공백 상태 검출 함수 int is..

스택 LIFO(Last-In First-Out) in Korean, 후입 선출 가장 최근에 들어온 object가 가장 위에 있어 먼저 나가게 된다. 스택의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다. 스택 상단(stack top) : 스택에서 입출력이 이루어지는 부분 스택 하단(stack bottom) : 스택 상단의 반대쪽인 바닥부분 요소(element) : 스택에 저장되는 것 공백 스택(empty stack) : 스택에 요소가 하나도 없을 때 그러한 스택 자료의 출력순서가 입력순서의 역순으로 이루어져야 할 경우에 매우 긴요하게 사용된다. ex. Undo(되돌리기) 기능 ex. 함수 호출 함수가 실행히 끝나면 자신을 호출한 함수로 되돌아간다. 시스템 스택에는 함수가 호출될..

배열의 응용 : 희소행렬 행렬을 표현하는 첫 번째 방법 : 2차원 배열을 사용 #define MAX_ROWS 100 #define MAX_COLS 100 int matrix[MAX_ROWS][MAX_COLS]; 단점 : 많은 항들이 0으로 되어 있는 희소행렬의 경우메모리의 낭비가 심하게 됨 첫 번째 방법을 통해 전치행렬 구하기 #include #define ROWS 3 #define COLS 3 // 행렬 전치 함수 void matrix_transpose(int A[ROWS][COLS], int B[ROWS][COLS]) { for (int r = 0; r

배열의 응용 : 다항식 $ p(x)=a_nx^n + a_{n-1}x^{n-1}+ ... + a_1x + a_0 $를 배열을 이용하여 표현해보자 첫 번째 방법 : 모든 차수의 계수값을 배열에 저장 (ex. 10x^5 + 6x + 3) #define MAX_DEGREE 101 // 다항식의 최대 차수 + 1 typedef struct { int degree; float coef[MAX_DEGREE]; } polynomial; polynomial a = {5, {10, 0, 0, 0, 6, 3}} 문제점 : 대부분의 항의 계수가 0인 희소 다항식의 경우에 공간의 낭비가 심함 장점 : 다항식의 덧셈이나 뺄셈 시에 같은 차수의 계수를 쉽게 찾을 수 있어 알고리즘이 간단해짐 ex) 두 다항식을 더하는 프로그램 차수..

리스트에 대한 설명은 다음을 참조 [자료구조] 배열을 이용한 리스트 구현 순차리스트 구현 ArrayList.h #ifndef __ARRAY_LIST_H__ #define __ARRAY_LIST_H__ #define TRUE 1 #define FALSE 0 #define LIST_LEN 100 typedef int LData; typedef struct _ArrayList { LData arr[LIST_LEN]; int numOfData; int curPosition; } ArrayList; typedef ArrayList List; void ListInit(List *plist); void LInsert(List *plist, LData data); int LFirst(List *plist, LData ..

배열을 이용한 리스트 구현 - 순차 리스트, 연결 리스트 순차 리스트 : 배열을 기반으로 구현된 리스트 연결 리스트 : 메리의 동적 할당을 기반으로 구현된 리스트 --> 두 리스트는 ADT(기능)는 동일, 구현방법만 다름. 리스트의 특징 저장형태 : 데이터를 나란히 저장한다. (어느 방향으로 저장하든 상관 없다.) 저장 특성 : 중복이 되는 데이터의 저장을 허용. --> 배열과 연결을 기반으로 함. 배열 기반 리스트의 단점 배열의 길이가 초기에 결정되어야 함. 변경이 불가능 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어남. 배열 기반 리스트의 장점 데이터의 참조가 쉽다. 인덱스 값 기준으로 어디든 한 번에 참조 가능. 리스트 자료구조의 ADT(기능) 리스트의 초기화 void ListInit(L..