전체 글

[자료구조] 단순한 정렬 : 버블 정렬, 선택 정렬, 삽입 정렬

버블 정렬(Bubble Sort) : 인접한 두 개의 데이터를 비교하여, 정렬순서 상 위치가 바뀌어야 하는 경우에 두 데이터의 위치를 바꿔나가는 방식이다. 오름차순으로 데이터를 정렬한다고 가정했을때, 큰 값을 뒤로 보내는 방식으로 구현된다. #include void BubbleSort(int arr[], int n) { int i, j; int temp; for(i=0; i

[자료구조] 배열을 기반으로 구현한 List에서 "삭제" 구현

배열을 기반으로 구현한 List에서 "삭제"를 담당하는 LRemove 함수를 정의할 때 인덱스와 데이터의 개수 때문에 자주 헷갈리는 부분을 정리하려고 한다. 위와 같이, C라는 데이터를 삭제하는 함수를 구현한다고 해보자. 이때 C라는 데이터가 삭제되고 나면, 뒤에 저장된 나머지 데이터들은 한칸씩 앞으로 이동시켜서 그 빈공간을 메꿔야 할 것이다. LData LRemove(List * plist) { int rpos = plist->curPosition; int num = plist->numOfData; int i; LData rdata = plist->arr[rpos]; for(i=rpos; iarr[i] = plist->arr[i+1]; (plist->numOfData)--; (plist->curPosi..

[Algorithm] 에라스토테네스의 체 : 소수 구하기

#에라스토테네스의 체 에라스토테네스의 체란 일정 범위 내의 소수를 찾는 가장 효율적인 알고리즘이다. 알고리즘의 원리는 어떤 수의 배수는 소수가 될 수 없다는 원리에 착안하여, 어떤 수의 배수가 되는 수들을 지워나가는 식이다. 1. 2 ~ N 까지의 자연수 중 먼저 소수를 찾는다(해당 범위에서는 2부터 시작됨) 2. 그 소수(2)를 제외한, 나머지 N까지의 수 중 우리가 찾은 소수(2)의 배수들을 모두 지운다. 3. 다음 소수(3)를 찾고 이 수를 제외한, 나머지 N까지의 수 중 방금 우리가 찾은 소수(3)의 배수들을 모두 지운다. 4. 위 과정을 N의 제곱근까지 반복한다(소수점은 내림한다). 해당 과정을 반복하고나면, 지워지고 남은 수들이 모두 소수가 된다. #구현 #include #include #de..

[Algorithm] 순차 탐색(Sequential search)과 이진 탐색(Binary search)

순차 탐색(Sequential search) 순차 탐색이란 나열된 데이터를 처음부터 끝까지 하나하나 순차적으로 탐색하면서 원하는 데이터를 찾는 방법을 말합니다. 코드 구현이 쉽고 알고리즘이 간단하다는 장점이있지만, 다른 탐색에 비해 상대적으로 시간이 많이 걸리는 단점이 있습니다. 최악의 경우, 순차 탐색은 1부터 n까지 모든 데이터를 탐색해야하기 떄문에 순차 탐색의 시간복잡도는 O(n)이 됩니다. #include int main(){ int ary[10] = {1, 3, 6, 2, 4, 5, 10, 8, 7, 9}; int len = sizeof(ary)/sizeof(int); int target = 0; scanf("%d", &target); int index = FirstFind(ary, len, t..

[Algorithm] 시간 복잡도(Time complexity)와 Big-O 표기법

무엇이 좋은 코드(Clean code)인가? 우리가 어떤 코드를 작성할 때, 이 코드가 좋은 코드인지를 판별할 수 있는 기준은 무엇이 있을까요? 누군가 우리에게 와서 좋은 코드를 작성해달라고 부탁한다면, 우리는 어떤 기준에 맞추어서 코드를 작성해야 할까요? 개발자들 사이에서, 좋은 코드를 판별하는 기준은 일반적으로 다음과 같은 두 가지 기준으로 설명합니다. 1. Readable (가독성) 다른 사람이 봤을 때, 일반적으로 깨끗하고 누구나 우리의 코드를 이해할 수 있는지에 대한 것입니다. 2. Scalable (확장성) 내부의 유지 보수가 쉽고 확장가능하며 좋은 생산성과 효율을 가지는 코드에 관한 추상적인 개념입니다. 우리는 Big-O를 이용해서 프로그램을 실행시키는데 걸리는 시간과 그 효율성의 측면에서 ..

[Java] Constructors in Subclasses with inheritance, Super method

상속이 있는 Subclass의 Constructor 호출 및 실행 과정에 대해서 알아보려 합니다. /* 코드 출처는 H. M. Deitel, P. J. Deitel , Java How to Program (Early Objects), Global Edition, 11th Edition, Pearson임을 밝힙니다. */ // Fig. 9.7: BasePlusCommissionEmployeeTest.java // BasePlusCommissionEmployee test program. public class BasePlusCommissionEmployeeTest { public static void main(String[] args) { // instantiate BasePlusCommissionEmplo..

[C] 포인터와 배열과의 관계, 그리고 포인터 연산

앞서 포인터에 대한 기초 개념을 간단하게 살펴보았다. 포인터가 어렵다고 많이 얘기하지만, 사실 그 악명에 비해 포인터의 개념자체는 크게 어렵지 않다. 포인터와 배열의 관계를 살펴보기에 앞서 다음 내용을 읽어보고 가도록하자. 배열의 또 다른 이름은 포인터이다. 정확하게는 그 값을 바꿀 수 없는 상수형 포인터이다. #포인터와 배열의 관계 다음 코드를 먼저 살펴보자. #include int main() { int arr[3] = { 1, 2, 3 }; printf("배열의 이름 : %p \n", arr); // 0000001DD735F838 printf("배열의 첫번쨰 원소 : %p \n", &arr[0]); // 0000001DD735F838 printf("배열의 두번쨰 원소 : %p \n", &arr[1]..

[C] 포인터의 기초 개념

#포인터의 선언과 초기화 포인터(pointer)는 프로그래밍 언어에서 다른 변수, 혹은 그 변수의 메모리 공간 주소를 가리키는 변수를 말한다. 어렵게 생각할 필요없이, 포인터 또한 우리가 지금까지 써왔던 int, double과 같이 하나의 변수이다. int형은 정수를 저장하고, double형이 실수를 저장하듯이 포인터 변수는 메모리의 "주소"를 저장한다.(포인터 변수를 줄여서 포인터라고 한다) 다음 코드를 보면 포인터의 개념이 잡힐 것이다. #include int main() { int num1 = 10; int* p; // 포인터 변수 p의 선언 p = &num1; // 포인터 변수 p의 초기화 // int* p = &num1; 와 같이 선언과 동시에 초기화 할 수 있다. printf("num1의 주소..

[Algorithm] 최대공약수(Gcd) : 유클리드 호제법 원리

#유클리드 호제법 유클리드 호제법이란 두 자연수 사이의 최대공약수(Gcd)를 구하는 알고리즘 중 하나이다. 두 자연수 a, b(a>b)에 대하여 a를 b로 나눈 나머지를 r이라고 하자. 그러면 Gcd(a, b) = Gcd(b, r)와 같고, r = 0이 될때까지 이 과정을 반복했을때 b의 값이 두 수의 최대공약수가 된다. #예시 두 수 1248과 462의 최대공약수를 유클리드 호제법을 이용하여 구해보자. a = 1248, b = 462라 하면 1248 = 462 * 2 + 324 이때 Gcd(1248, 462) = Gcd(462, 324)이고, 다시 a= 462, b = 324라 하면 462 = 324 * 1 + 138 마찬가지로 Gcd(462, 324) = Gcd(324, 138)이다. 이 과정을 r ..