본문 바로가기

컴퓨터 공학/Algorithm18

[알고리즘] C언어로 익히는 자료구조 및 알고리즘 총정리 C언어로 익히는 자료구조 및 알고리즘 총정리 공학 관련 전공자라면 피할 수 없는 알고리즘, 졸업하고 나서도 치뤄야 하는 코딩 테스트가 있습니다. 아무리 거대해 보이는 산이라도 기초 체력이 있다면 충분히 정상에 오를 수 있듯이, 알고리즘 문제를 해결할 때도 기본을 이해하는 것이 가장 중요할 것입니다. 저도 최근에 알고리즘 지식을 꼼꼼히 복습해야하는 상황히 생겨서.. 예전에 공부했던 이지스 퍼블리싱의 '자료구조와 함께 배우는 알고리즘 입문(C언어편)'와 오렌지 미디어의 '윤성우의 열혈 자료구조' 책을 가지고 정리하는 시간을 가졌습니다. 이 곳에 정리한 글을 하나씩 연재할 계획입니다. 포스팅하는대로 링크를 활성화하겠습니다. 1. 기본 알고리즘 - 자료구조와 알고리즘 개념 - 시간복잡도, 공간복잡도란? - 빅-.. 2020. 9. 29.

[알고리즘] 큐(Queue) 개념/용도/삽입/삭제/검색(C언어) 큐(Queue) 개념/용도, C언어로 삽입/삭제/검색 구현하기, 예제 스택은 출입구가 하나였다면 큐는 2개인 자료구조입니다. 스택과 마찬가지로 자료의 삽입과 삭제에 대한 규칙이 있는 자료구조 중 하나입니다. 선입선출(first in first out)로 먼저 들어간(enqueue) 데이터가 먼저 삭제(dequeue)됩니다. 영어로 Queue도 한 줄로 서있는 상태를 의미하니 아래 그림을 기억하면 좋을 것 같습니다. 데이터가 10, 20, 30 순으로 삽입되었으면 삭제도 10, 20, 30 순입니다. 즉, 삽입 순서와 삭제순서가 같죠. 언제나 가장 처음에 있는 자료만 제거 가능하고, 중간 자료에 임의 접근 안 됩니다. ■ 큐의 삽입 en + queue = enqueue 1. ~속에 넣다 1 대기줄 큐에 넣.. 2020. 7. 11.

[알고리즘] 스택(Stack)의 삽입/제거/검색(C언어) 스택(Stack)의 삽입/제거/검색(C언어) C언어로 자료구조 스택의 삽입, 제거, 검색의 예를 코드로 보겠습니다. 스택(Stack)의 개념을 파악하고 싶다면 아래 글을 먼저 읽어주세요. 스택이란? 글 보러가기 ■ 스택의 삽입 최대 8개의 요소가 들어갈 수 있는 스택입니다. 값을 삽입할 때 배열에서 사용하는 insert를 스택에서 push로 사용합니다. C 언어로 구현한 코드를 보겠습니다. enum { MAX_NUMS = 8}; int s_nums[MAX_NUMS]; // 8개 요소를 넣을 수 있는 배열 생성 size_t s_num_count = 0; // 데이터를 넣을 자리(인덱스) void push (int n){ assert(s_num_count < MAX_NUMS); s_nums[s_num_cou.. 2020. 7. 10.

[ 알고리즘 ] 스택(Stack)의 개념과 용도 스택(Stack)의 개념과 용도 ■ 스택의 용도 모바일 게임 중에 한창 유명했던 어플리케이션 STACK이 있습니다. 떨어지는 블럭을 잘 쌓아야 하는 게임인데 최근에는 4D로도 나온것 같더라고요. 이처럼 스택(Stack)은 영어 단어로 쌓여있는 더미라는 뜻입니다. 배열과 달리 스택은 삽입과 삭제에 대한 규칙이 있습니다. 삽입할 때 1, 2, 3, 4 순이었다면, 삭제는 4, 3, 2, 1 순으로 해야 합니다. 중간에 있는 요소를 제거하는 것은 원칙상 불가능합니다. 즉, 중간 자료의 임의 접근이 안됩니다. 이런 제약이 있는 스택, 주로 어느 용도로 사용될까요? ■ 스택의 용도 1. 자료의 순서를 뒤집는데 유용합니다. 스택의 요소를 하나씩 뽑아서 배열에 저장합니다. 그럼 배열의 요소가 뒤집어집니다. 이런 식으.. 2020. 7. 10.

[ 알고리즘 ] 연결 리스트(Linked List) 용도 / 오늘날 사용 빈도 연결 리스트(Linked List) 용도/사용빈도 1. 배열의 한계를 극복하기 위해 배열(or 배열 기반 리스트)의 한계 - 배열은 정형화돼서 색인으로 접근해야 합니다. - 초기에 메모리 공간을 잡아두고, 변경이 불가능합니다. - 삭제 시 데이터의 이동(복사)가 빈번히 발생합니다. 하지만 연결리스트는 메모리 크기가 얼마인지 중요하지 않습니다. 노드 하나 만들어 놓고 필요할 때마다 만들어 연결하기 때문에 길이가 자유롭습니다. 데이터를 삽입/삭제할 때도 위치만 안다면 삭제하고 복사할 필요없이 진행할 수 있습니다. 이런 개념은 연결 리스트는 배열보다 메모리를 좀 더 자유롭게 사용하면서 다음 것(데이터)를 가리킬 수 있는 방식으로 볼 수 있습니다. 2. 삽입, 삭제가 빈번한 경우에 사용 연결 리스트에서는 삽입,.. 2020. 7. 9.

[ 알고리즘 ] 추상 자료형(ADT) 란? 추상 자료형(ADT) 란? 추상 자료형이란 구체적인 완성 과정을 언급하지 않고, 순수하게 기능이 무엇인지 나열한 것입니다. 예를 들어 설명하기 위해 C언어 기반으로 구조체 하나를 정의하겠습니다. 구조체를 기반으로 리모콘을 의미하는 구조체를 정의하였습니다. Remote이라는 자료형의 정의인 셈입니다. 하지만 컴퓨터 공학적 측면에서는 자료형의 정의가 구조체 정의만으로 완성되는 것이 아닙니다. Remote을 기반으로 하는 연산의 종류를 결정하는 것도 추가해야합니다. 즉, 아래의 두 가지를 다 충족시켜야 합니다. 1. 구조체의 정의 2. 그 구조체와 관련된 연산의 종류 여기서 연산은 +,- 의 기본 연산이 아니라 Remote을 기반으로 제공할 수 있는 기능 관련 연산을 의미합니다. 아래와 같은 것들이 될 수 있.. 2020. 7. 9.

[ 알고리즘 ] 연결리스트(Linked List) 삽입/조회(그림으로 이해하기) 연결리스트(Linked List) 삽입/조회(그림으로 이해하기) ■ 연결 리스트 개념 이해 연결리스트는 여기저기 흩어져있는 데이터를 다룹니다. 일렬로 데이터를 처리하는 배열과 큐와는 완전히 다른 개념입니다. 위 그림처럼 데이터가 서로 떨어져 있을 수 있는 이유는 동적 메모리를 할당하기 때문입니다. 연결리스트에서 메모리에 있는 자료형을 노드라고 부릅니다. 데이터를 저장하는 장소와 다음 데이터를 가리키는 포인터 변수로 구성되어 있습니다. 처음노드를 가리키는 노드는 없어서 head라고 부릅니다. 마지막노드는 가리켜야할 다음 데이터가 없어서 null 포인터를 가지고 있습니다. ■ 연결 리스트 삽입 - 15와 30 사이에 20를 삽입하고 싶으면 포인터 2개만 변경해주면 됩니다. - 15 데이터의 포인터 변수는 2.. 2020. 7. 9.

[ 알고리즘 ] 하노이 타워(The Tower of Hanoi) 재귀 함수로 구현하기 (C언어) C언어로 하노이 타워(The Tower of Hanoi) 재귀 함수로 구현하기 하노이 타워 문제는 1883년 프랑스 수학자에 의해 처음 소개되었습니다. 하나의 막대에 쌓여 있는 원반을 다른 막대에 그대로 옮겨야 하는 문제인데, 막대 3개를 이용할 수 있고, 다음 제약조건을 만족시켜야 합니다. 막대 A에서 막대 C로 옮기기 위해서 막대 B를 잘 활용해야 합니다. 직접 연습장에서 어떻게 옮길 것인지 그림으로 그려보고 아래 과정을 확인해보세요. 원반1, 2번을 막대 B에 옮겨다 놓으면 원반 3번을 막대 C에 올길 수 있습니다. 그럼 원반1,2번을 막대 B로 옮겨야 합니다. 이것이 하노이 타워 문제 해결의 핵심입니다. 즉, 모든 원반(3개)를 옮기기전에 우선 두 개의 원반을 막대 B에 옮기는 문제부터 해결해야 .. 2020. 7. 9.

[ 알고리즘 ] 연결리스트(Linked List) 삭제 (그림으로 이해하기) 연결리스트(Linked List) 삭제 (그림으로 이해하기) - 이미 삭제할 위치를 알면 O(1) 걸립니다. - 20을 바로 제거하는 것이 아니라 앞 노드가 다음 노드를 가리키게 하면 됩니다. 여기서 주의할 점은 해당 노드를 바로 삭제해버리면 그 다음 노드에 접근이 불가하니 '삭제될 노드가 가리키는 다음 노드의 주소 값'을 별도로 저장해 두어야 합니다. 관련 글 연결 리스트 삽입/조회하는 방법 연결 리스트 용도 ------------------------------ 알고리즘 개념 모아보기 ------------------------------ 2020. 7. 9.

[ 알고리즘 ] 이진 탐색 알고리즘의 재귀적 구현(C언어) last) // 탈출 조건 return -1; // -1 반환은 탐색의 실패 의미 mid = (first+last)/2; if(array[mid] == target) return mid; // 탐색된 타켓의 인덱스 값 반환 else if (array[mid] > target) return BinarySearchRecur(array, first, mid-1, target); else return BinarySearchRecur(array, mid-1, last, target); } int main(void) { int arr[]={1, 3, 4, 7, 8}; int index; index = BinarySearchRecur(arr, 0, sizeof(arr)/sizeof(int)-1, 3); if(inde.. 2020. 7. 8.

[ 알고리즘 ] 재귀의 활용_피보나치 수열 구현(C언어) 재귀의 활용_피보나치 수열 구현(C언어) 피보나치 수열은 재귀적인 형태를 띠는 대표적인 수열입니다. 앞의 두 수를 더해서 현재의 수를 만들어가는 수열이라 처음 두 개의 수(0,1)이 주어진 상태에서 만들어집니다. 피보나치 수열의 n번째 위치의 값을 반환하는 함수를 코드로 구현보겠습니다. #include int Fibo(int num) { if(num == 1) // 수열의 첫번째 자리를 요구하면 0 반환 return 0; else if(num == 2) // 수열의 두번째 자리를 요구하면 1 반환 return 1; else // 수열의 세번째 자리 이상을 요구하면 return Fibo(num - 1) + Fibo(num - 2); } int main(void) { int i; printf("피보나치 수열.. 2020. 7. 8.

[ 알고리즘 ] 재귀함수의 디자인 사례_팩토리얼 구현(C언어) 재귀함수의 디자인 사례_팩토리얼 구현(C언어) 정수 n의 팩토리얼은 n!로 표시합니다. n! = n x (n-1) x (n-2) x (n-3) x ... x 2 x 1 따라서 3!은 3 x 2 x 1 입니다. #include int Factorial(int num) { if(num == 0) // 탈출조건 return 1; else return num * Factorial(num - 1); // 재귀 개념 활용 } int main(void) { printf("3!은 %d입니다.\n",Factorial(3)); return 0; } ------------------------------ 알고리즘 개념 모아보기 ------------------------------ 2020. 7. 8.

[ 알고리즘 ] 재귀 함수의 기본 원리 이해하기 [ 알고리즘 ] 함수의 재귀적 호출의 이해 재귀함수란 다음과 같이 함수 내에서 자기 자신을 다시 호출하는 함수를 의미합니다. 완료되지 않은 함수를 다시 호출하는 것이 가능한가요? 네 가능합니다. 아래 그림으로 더욱 쉽게 재귀함수의 흐름을 파악해봅시다. 다음 그림은 Recursive 함수가 호출되면, Recursive 함수의 복사본이 만들어집니다. 그리고 그 복사복인 실행되고, 그 안에서 Recursive 함수가 호출가 호출되면 또 복사본이 만들어집니다. 실제로 함수를 구성하는 명령문은 CPU로 이동(복사)되어서 실행됩니다. 따라서 이 재귀함수 역시 얼마든지 CPU로 이동이(복사가) 가능합니다. 그럼 위의 예제의 호출 결과는 어떨까요? Recursive 함수에서 문자열 출력하고, Recursive 함수 호.. 2020. 7. 8.

[ 알고리즘 ] 빅-오 표기법이란? [ 알고리즘 ] 빅-오 표기법이란? 빅오 표기법은 대문자 O를 사용하기 때문에 빅(Big) 오(O)라고 부릅니다. 앞 글에서 이진 탐색 알고리즘의 시간 복잡도 함수를 구하면서 최악의 경우의 비교연산 횟수는 k+1에서 +1이 중요하지 않다고 했습니다. 왜 그렇게 말할 수 있는지 빅-오 표기법을 통해 설명하겠습니다. (이해를 위해 이전 글을 읽어오시면 좋습니다.) 먼저 빅-오에 대한 설명을 위해 하나의 예로 시간 복잡도 함수를 봅시다. 시간 복잡도 함수를 T(n)를 구하는 이유는 데이터의 수 n이 증가에 따라 연산횟수의 변화 정도를 판단하기 위해서입니다. (중요) 오차 없이 시간 복잡도를 함수를 구할 수 없고, 구할 필요도 없다는 겁니다. 즉, 근사치(approximtation) 식으로 구성해도 됩니다. 그.. 2020. 7. 6.

[ 알고리즘 ] 이진 탐색이란? 시간의 복잡도 계산하기 이진 탐색이란? 시간의 복잡도 계산하기 배열을 대상으로 이진 탐색 알고리즘을 적용하기 위해서는 배열에 저장된 데이터가 정렬되어 있어야 합니다. 즉, 이진 탐색 알고리즘은 정렬된 데이터가 아니면 적용이 불가능합니다. 그럼 이해를 위해 그림을 먼저 보겠습니다. 다음과 같이 정렬된 배열이 있습니다. 배열의 요소 중 3은 어느 인덱스에 있는지 알고 싶다고 가정하겠습니다. 1. 배열의 가운데를 찾기 위해 인덱스의 시작과 끝을 더해 2로 나눕니다. 2. 인덱스 3에 있는 요소와 목표값이 같은지 비교합니다. 3. 아니네요. 인덱스 3에 있는 요소(7)는 목표값(3)보다 큽니다. 4. 범위를 0~2로 하여 다시 인덱스의 시작과 끝을 더해 2로 나눕니다. 5. 인덱스 1에 있는 요소와 목표값이 같은지 비교합니다. 6. .. 2020. 7. 5.

[ 알고리즘 ] 순차 탐색(Linear Search) 이란? 시간 복잡도 계산하기 순차 탐색(Linear Search) 이란? 최악의 경우 시간 복잡도 계산하기 순차 탐색이란 말 그대로 맨 앞에서부터 순서대로 탐색을 하는 알고리즘입니다. 순차 탐색 알고리즘을 적용한 코드를 보겠습니다. ※ 윤성우의 열혈 자료구조 책에서 코드 참고하였습니다. 위의 코드 중 실제로 순차 탐색 알고리즘을 구현하는 부분입니다. for문을 통해 인덱스를 1씩 증가하여 배열를 처음부터 끝까지 목표값과 비교(==)합니다. 그래서 배열(arr)에서 목표값(target)을 찾으면 그 값의 인덱스(i)를 반환합니다. 이제 위의 코드를 토대로 시간 복잡도(Time complexity) 를 분석해볼까요? 데이터의 수 n에 대한 연산 횟수의 함수 T(n) 구해봅시다. 연산 횟수라 했으니까 이 알고리즘에서 사용된 연산자 2020. 7. 4.

좋은 알고리즘을 평가하는 요소(시간복잡도, 공간복잡도) 좋은 알고리즘을 평가하는 요소(시간복잡도, 공간복잡도) 지금 잠시 차🚗를 새로 구입한다고 생각해보세요. 1) 집에서 회사까지 이동만 할 수 있는 차 2) 집에서 회사까지 소음 적고, 연비 좋고, 오르막 길에서 기를 쓰지 않아도 속도내며 이동할 수 있는 차 둘 중에 어느 차를 선택하실 겁니까? 아마 대부분이 2번을 고를 겁니다. 우리는 잘 동작하는 것은 물론이고 성능까지 보장받기 원하니까요. 알고리즘에도 똑같이 적용됩니다. 그저 잘 동작하는 자료구조와 알고리즘(이하 '알고리즘'으로 총칭)을 찾는다면 필요한 기능만 보면 되겠죠. 하지만 성능도 따지고 싶기 때문에 알고리즘을 분석할 줄 알아야 합니다. 크게 두 가지 요소가 있습니다. 특정 상황에서 1) 어떤 알고리즘이 더 빠른가? 2) 어떤 알고리즘이 메모리를.. 2020. 7. 3.

자료구조와 알고리즘 개념 쉽게 이해하기 자료구조와 알고리즘은 무엇인가 '알고리즘은 자료구조에 의존적이다.'라는 말을 들어본 적이 있을 것입니다. 도대체 자료구조와 알고리즘이 뭐길래 저런 관계가 성립이 되는 걸까요? 개념을 파악하기 위해 프로그램의 간단한 정의를 봅시다. 프로그램은 크게 두가지를 합니다. 1) 데이터의 표현 (자료구조) 2) 데이터의 처리 (알고리즘) 1) 데이터 표현에는 데이터를 저장하는 일을 포함됩니다. 여러분은 이미 데이터를 저장해본 적이 있습니다. 정수를 저장하기 위해 int형 변수를 선언하고, 다양한 정보를 활용하기 위해 배열을 사용했죠. 넓은 의미로 int형 변수와 배열은 자료구조의 일종입니다. 2) 그렇게 표현된 데이터(int형 변수나 배열)를 가지고 문제를 해결하는 것이 알고리즘입니다. 간단한 코드를 보겠습니다. .. 2020. 7. 3.

이전 1 다음

티스토리툴바