분류 전체보기 썸네일형 리스트형 <자료구조 알고리즘> 정렬 (버블정렬) 정렬이란? 선형 자료구조(배열 등)의 원소들을 특정한 순서(오름차순 내림차순등)로 나열하는 것을 이야기 한다. 정렬 자체가 목적일 때도 있겠지만 대부분 검색등의 다른 알고리즘의 전처리 과정으로 사용되는 경우가 많다. 정렬알고리즘 종류 Permutaion Sort, Selection Sort , bubble sort , Quick Sort , Insertion Sort , Merge Sort 등 굉장히 많은 종류의 정렬알고리즘이 있다. 각 알고리즘의 방식과 구현방법, 시간복잡도를 알아보도록 하자. 이 글에서는 오름차순을 기준으로 설명하도록 하겠다. Bubble sort (버블 정렬) 버블 정렬은 인접한 두 원소의 크기를 비교한는 방법의 정렬알고리즘이다. 배열의 앞에서 부터 두개의 원소의 크기를 비교하여 앞.. 더보기 <자료구조 알고리즘> 큐 구현 큐 구현 이번에는 큐을 구현해보자. 동적 배열을 이용해서도 구현을 할 수 있기는 하겠지만 크기가 계속 바뀌어야 하니 굉장히 비효율 적일 것이다. 또한 중간에 있는 데이터에 접근하는 일도 없을 테니 연결리스틀 사용하는 것이 더 효율적일 것이다. 데이터를 삽입하는 곳을 rear(뒤) 삭제하는 곳을 front(앞)이라고 하고 연결리스트 양 끝의 주소를 rearNode와 frontNode에 계속 저장해 놓을 것이다. 연결리스트가 연결되어있는 방향을 잘 보아야 한다. 위 사진과 같이 각 노드의 다음노드는 더 늦게 추가된 데이터를 가르키고 있어야 한다. 삽입 할 때에는 연결리스트의 한쪽 끝(rear)에 데이터를 넣고 그 주소를 rearNode에 저장한다. 삭제 할 때에는 frontNode에 다음 노드를 저장(fro.. 더보기 <자료구조 알고리즘> 큐 큐란? 배열처럼 선형 구조의 자료구조(뭔가 한 줄이라는 느낌)이며 양쪽 끝에서 접근할 수 있고 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 자료구조이다. 스택은 데이터를 쌓는 데에 반해 큐는 데이터를 밀어 넣는다고 생각하면 쉽다. 자 차근차근 알아보도록 하자. 1. 종이컵 디스펜서 정수기 옆에 종이컵을 뽑아 먹을 수 있게 달려있는 종이컵 디스펜서 한 번 쯤은 써 보았을 것이다. 종이컵 디스펜서와 큐의 구조가 굉장히 비슷하다. 종이컵을 뽑을 때에는 아래에서 뽑고 종이컵을 보충해 줄 때에는 위에서 넣는다. 항상 맨 아래의 종이컵만 뽑을 수 있다. (중간에 있는 것을 먼저 뽑을 수는 없다.) 위에서 종이컵을 빼 내거나 아래에서 집어 넣을 수는 없다. 따라서 .. 더보기 <자료구조 알고리즘> 스택 구현 스택 구현 이번에는 스택을 구현해보자. 구현은 동적 배열을 이용해서도 구현을 할 수 있기는 하지만 중간에 있는 데이터에 접근하지는 않을 것이고 끝에 추가 삭제를 많이 할 테니 연결 리스트를 사용하는 것이 더 효율적일 것이다. 옆 그림과 같이 일반 연결 리스트를 이용해서 쉽게 구현할 수 있다. head가 가르키는 곳이 스택의 가장 윗부분이다. 데이터를 추가할 때는 새로운 노드의 다음 노드로 원래 head노드를 저장하고 head가 새로운 노드를 가르키게 하면 된다. 데이터를 꺼낼 때는 head가 가장 위 노드의 다음 노드를 가르키게 하면 된다. 코드로 구현해 보면 다음과 같다. template struct list { T val; list* next; list() : val(NULL), next(NULL) .. 더보기 <자료구조 알고리즘> 스택 스택이란? 배열처럼 선형 구조의 자료구조(뭔가 한 줄이라는 느낌)이며 한 쪽 끝에서만 제한적으로 접근할 수 있는 LIFO( last in first out) 구조의 자료구조이다. 이름 그대로 데이터를 쌓는 자료구조이다. 자 차근차근 알아보도록 하자. 1. 하노이 탑 스택을 알아보자면서 갑자기 웬 하노이 탑이 나오냐고? 일단 아래 사진처럼 하노이 탑의 기둥 하나만 떠올려 보자. 하노이탑은 기둥에 원판을 이동하는 퍼즐이다. (원판 크기는 스택이랑 관련 없으니 생각하지 말자) 이 기둥에 원판을 꽂는 것과 스택의 구조가 굉장히 비슷하다. 하노이탑에 원판을 꽂을 때에는 밑에서 꽂을 수도 없고 중간에 넣을 수도 없다. 무조건 위에 꽂아야 한다. 또한 빼낼 때에는 항상 맨 위에 있는 원판만 빼낼 수 있다. (위에 것.. 더보기 <자료구조 알고리즘> 그래프 표현 3. edge list (간선 리스트) 그래프가 무엇인지 모르시는 분들은 아래 글을 참고하길 바랍니다. https://jjoonleo.tistory.com/11 그래프 개념 그래프란? 정점(vertex)과 간선(edge)로 이루어진 자료구조이다. 수학에서 자주 보던 좌표평면에 그리는 그 그래프가 아니다. 쉽게 이해하기 위해서 정점을 마을 간선을 마을 사이를 잇는 길이라고 jjoonleo.tistory.com 그래프의 표현 방식 이번 글에서는 그래프의 표현 방식에 대해 알아 보도록 하겠다. 그래프는 배열이나 큐 스택과는 다르게 어떻게 구현해야 할지 바로 떠오르지는 않는 것 같다.(나만 그랬나??) 그래프의 표현 방식에는 3가지가 있다. 1. Adjacency List (인접 리스트) 2. Adjacency matrix (인접 행렬) 3. edg.. 더보기 <누구나 쉽게 배우는 C언어> C언어 독학 강좌 3. 변수 변수란 무엇일까요? 실생활에서 변수라는 말을 종종 쓰기도 합니다. "계획에 변수가 생겼어" 처럼 말이죠. 이 때의 변수는 어떠한 상황에서 변할 수 있는 요인이라는 뜻으로 사용됩니다. 프로그래밍에서는 조금 다른 의미로 사용됩니다. 변수란 단 하나의 값을 저장할 수 있는 메모리 공간 어떠한 값을 저장하고 싶을 때 사용하는 것이 변수 입니다. 변수를 사용하는 방식은 세가지 단계로 나눌 수 있습니다. 1. 변수 선언 2. 변수에 값 저장(초기화) 3. 저장한 값 사용 변수는 타입, 이름, 값으로 이루어져 있습니다. 변수를 사용하기 위해서는 제일 먼저 선언을 해줘야 합니다. 컴퓨터에게 "나 이제 이 변수 사용할거야"라고 알려주는 것이죠. 1.변수 선언 변수의 선언은 다음과 같이 합니다. 변수타입 변수이름; 예) .. 더보기 교란순열 교란순열의 개수를 구해보자 교란순열이란 원래 위치에 있는 원소가 하나도 없는 순열이다. 사람들이 각각 자신의 모자를 벗었다가 아무 모자나 다시 쓰는데 모든 사람이 자기 것이 아닌 모자를 쓰는 순열이라고 할 수 있다. 길이가 n 인 순열에서 교란순열의 개수를 어떻게 알 수 있을까? 교란 순열의 개수를 구하는 공식은 $$n! \sum_{k=0}^n \frac{(-1)^k}{k!}$$ 이를 유도해 보자 가장 쉽게 생각해서 모든 순열개수 n!에서 교란순열이 아닌 수열의 개수를 빼주면 된다. 한 개 이상의 수가 원래 자리에 있는 순열의 개수를 구해보면 4C1*3!이다 하지만 이렇게 구한 수를 이용해서 4!- 4C1*3!을 하게 된다면 2개 이상의 수가 원래 자리에 있는 순열은 중복해서 빠지게 된다. 그렇기 때문에.. 더보기 이전 1 2 3 4 5 6 7 다음
