Heap 은 binary tree 형태로 값을 저장하되, 루트 노드에 max heap이면 최댓값이, min heap 이면 최솟값이 저장되는 자료구조를 말한다. 최댓값이나 최솟값을 구해야 하는 경우, heap이라는 자료구조를 사용하면 굉장히 편하게 구할 수 있다. 우선순위 큐는 기본 큐 구조와 달리 입력 순서가 아닌 우선순위 순서로 자료를 저장하는 자료구조를 말한다. 우선순위 큐 (Priority Queue)는 Heap을 사용하여 구현하는데 우선순위에 따른 오름차순 정렬은 Min Heap으로, 내림차순 정렬은 Max Heap으로 구현할 수 있다. 물론, java 에 Priority Queue 라이브러리가 있기 때문에 바로 사용할 수 있지만, 공부를 위해 라이브러리를 사용하지 않고 짜보았다. 먼저, Min ..
[알고리즘] Java로 구현하는 쉬운 Merge Sort (병합 정렬, 합병 정렬)
알고리즘을 시작할 때 가장 먼저 배워야 할 것은 정렬, 즉 sorting이라고 생각한다. 버블 정렬, 선택 정렬, 퀵 정렬 등 많은 정렬이 있지만, 내가 사용하는 것은 병합 정렬이다. 병합 정렬(=합병 정렬)의 시간복잡도는 O(nlogn)인데, 왜 이 시간 복잡도가 나오는지 먼저 알아보자. 병합 정렬은, 원소가 저장되어 있는 배열을 계속 쪼개서 길이가 1인 배열을 만들고, 그 이후 정렬하면서 합치는 알고리즘이다. Merge sort 는 binary tree 형태로 쪼개기 때문에 가질 수 있는 최대 깊이는 log n 이 된다. 이때, 각 분할 (n개) 별로 합병을 진행하므로, 총 시간 복잡도는 O(nlogn)이 된다. 이때, quick sort는 최악의 경우 O(n^2)의 시간 복잡도를 가지게 되는데, m..
[프로그래밍언어] Formal parameter, Actual parameter, 그리고 parameter passing
우선, parameter에는 formal parameter와 actual parameter가 있다. 예제 코드를 통해 formal parameter와 actual parameter를 비교해보자. class Solution { public static void main(String[] args) throws Exception { int a = 1; int b = 2; System.out.println(getSum(a,b)); } public static int getSum(int x, int y) { return (x+y); } } - Formal parameter : 함수(subprogram)를 정의할 때와 함수 안에서 사용되는 parameter (x, y) - Actual parameter : 함수(s..
이번 포스팅은 중요한 내용을 담고 있다. 이번에 다룰 내용은 참 많은데, 주제는 Variable이다. 이 Variable에 대해서 name, binding time, blocks, global variable (전역 변수), local variable (지역변수), memory allocation, lifetime, named constant (이름 상수), Type에 대해 알아보도록 하겠다. 1. Name Name은 정말 간단하게 변수의 이름을 말한다. int a; 에서는 a가 변수 이름이다. 이 이름은 간단하지만, 제약이 있는 경우가 있다. 예를 들면 int for = 1; 이런 식으로 for라는 실제 사용되는 단어로 변수의 이름을 설정할 수 없다. 이런 단어들을 predefined name이라고 한..
고급언어의 기능으론 다음의 3가지가 있다. 1. Data Abstraction 2. Process Abstraction 3. Data & Process Abstraction 1은 메모리에 저장되는 데이터 타입을 의미한다. 예를 들면, char, int, double, boolean, string 같은 것 말이다. 특히 변수, 배열, 구조체 등으로 메모리 블록에 명칭을 부여하는 기능도 제공한다. 2는 기계어 명령 여러 개를 구조화 시킨 것을 의미한다. 예를 들면, if, for, while 같은 구문과 함수, 프로시저 등이다. 3은 Class, Module, Package를 의미한다. 고급언어는 다음과 같은 특성을 가진다. 1. 단순성 (overall simplicity) : 어떤 현상을 단순하게 하여 쉽..
프로그래밍 언어는 개발자라는 직업을 선택한 사람들에게 가장 기초가 되는 과목이다. 개인적으로 학부생 시절에 이 수업을 들으면서, 이런 걸 과연 왜 배우는 걸까? 의미가 있을까? 외우기 위주 수업이라고 재미없다고 생각했다. 하지만, 졸업을 하고 나니, 프로그래밍 언어라는 과목이 얼마나 중요한지 깨달았고, 퇴근한 금요일 밤에 예전에 했던 수업 필기를 찾아서 정리하려고 한다. 퇴근한 금요일 밤에 이 게시물을 작성하는 것 만으로도, 지금 학부생인 분들께 프로그래밍 언어라는 수업을 열심히 들어야 한다는 생각이 꼭 들길 바란다. 내가 참고한 책은 수업 교재였던 'Concepts of Programming Languages, 10th edition, Robert W. Sebesta'이다. 이 책에 의하면, 프로그래밍..
MSP (Microsoft Student Partner) 란 컴퓨터학과 학생들이 모여서 MS의 기술을 세미나를 통해 소개하는 활동을 하는 대외활동이다. 이 활동을 2학년 2학기부터 했는데 정원은 한 50명쯤 되는 것 같다. 여러 대학교에서 컴퓨터학과 학생들이 모인다. MSP 구성원들은 진짜 개발을 엄청 잘하시고, 다양한 정보를 가지고 계신 갓..도 있는 반면, 나처럼 컴퓨터학과지만 컴퓨터 잘 모르고, 배우고 싶어 하는 사람들도 많다. 일단 이 활동을 통해 모든 분야에 대해서 완벽히 알지는 못해도, 수박 겉핥기 식으로 어떤 분야가 있고 ~한 걸로 코딩하고 ~하는데 쓰인다. 이런 정보나, 어떤 회사가 좋고 어떤 회사가 도둑놈인지에 대한 정보도 얻게 되었다. 특히 여러 분야에 대해 겉핥기 식으로 알게 된 것이..
network layer : logical communication between hosts transport layer : logical communication between processes UDP : unreliable, unordered delivery (best-effort), connectionless (user-datagram-protocol) - no connection establishment (which can cause delay), simple, small segment header, no congestion control) - multimedia application streaming에 사용된다. (loss tolerant but rate sensitive) (DNS, SNMP,..