자료구조 알고리즘 썸네일형 리스트형 <자료구조 알고리즘> 연결 리스트 연결리스트란? 배열에서 각 요소간의 연결이라는 개념이 추가된 자료구조이다. 연결리스트에는 여려개의 요소들이 들어있고 이 요소들은 특정한 방법을 통해 다음 요소와 서로 연결되어 있다. 이 연결을 타고 우리는 각 요소에 접근 할 수 있다. 이야기만 들으면 너무 추상적이니 아래 그림을 같이 보자. 위의 그림에서 네모는 연결리스트의 각 요소를 나타내며 다음 요소를 가르키고 있는 화살표가 요소 사이의 연결을 나타낸다. 1. 연결 방식 연결리스트의 각 요소는 두가지로 구성되어 있다. 하나는 저장하려는 값이고, 다른 하나는 다음 요소의 주소값이다. 오른쪽 그림의 초록색 부분에 다음 요소의 주소를 저장해 위의 그림에서 화살표가 요소를 연결하는 것과 같은 역할을 한다. 2. 접근 방식 해리포터를 읽어 보았다면 플루 가루.. 더보기 <자료구조 알고리즘> CCW 알고리즘 CCW(Counter Clock Wise) 알고리즘이란? 시계 반대 방향이라는 뜻으로 세 점이 있을 때 이들의 위치 관계를 파악하는 알고리즘이다. 기하 알고리즘에서 덧셈처럼 아주 기본적인 알고리즘이며 선분 교차 convex hull 찾기 알고리즘 등 대부분의 기하 알고리즘에서 사용한다. 결과가 음수라면 시계 방향, 0이라면 일직선, 양수라면 시계 반대 방향이라는 뜻이다. 일직선인 경우 시계 반대 방향 시계 방향 CCW 알고리즘은 벡터의 외적이 두 벡터의 상대적인 방향에 따라 결과 벡터의 방향이 바뀐다는 것을 이용한다. 그럼 벡터의 외적을 먼저 알아보자. 벡터의 외적 $\overrightarrow{v} = \begin{bmatrix} v_1& v_2 & v_3 \\ \end{bmatrix}$ $\overr.. 더보기 <자료구조 알고리즘> 마스터 정리 Master theorem 점화식으로 표현되는 재귀알고리즘의 시간 복잡도를 계산하는 것은 간단한 일이 아니다. 이 글에서는 재귀알고리즘의 시간 복잡도를 조금은 쉽게 계산할 수 있게 해 주는 Master theorem에 대해 알아보자 이름은 Master theorem 이지만 모든 점화식에 사용이 가능하지는 않고 $T(n) = aT(\frac{n}{b}) + f(n)$의 형태의 점화식에만 사용가능하다. 즉 재귀 트리에서 모든 leaf노드의 차수가 같을 때만 가능한 것이다. (a: 분할한 부분 문제의 수, b: 입력의 크기가 줄어드는 비율 당연히 $\geq 2$, $T(\frac{n}{b})$ : 부분문제를 푸는데 걸리는 시간, $f(n)$ : merging에 필요한 시간) Master theorem $$T(n) = aT(\frac{n.. 더보기 <자료구조 알고리즘> 정렬 (버블정렬) 정렬이란? 선형 자료구조(배열 등)의 원소들을 특정한 순서(오름차순 내림차순등)로 나열하는 것을 이야기 한다. 정렬 자체가 목적일 때도 있겠지만 대부분 검색등의 다른 알고리즘의 전처리 과정으로 사용되는 경우가 많다. 정렬알고리즘 종류 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. 하노이 탑 스택을 알아보자면서 갑자기 웬 하노이 탑이 나오냐고? 일단 아래 사진처럼 하노이 탑의 기둥 하나만 떠올려 보자. 하노이탑은 기둥에 원판을 이동하는 퍼즐이다. (원판 크기는 스택이랑 관련 없으니 생각하지 말자) 이 기둥에 원판을 꽂는 것과 스택의 구조가 굉장히 비슷하다. 하노이탑에 원판을 꽂을 때에는 밑에서 꽂을 수도 없고 중간에 넣을 수도 없다. 무조건 위에 꽂아야 한다. 또한 빼낼 때에는 항상 맨 위에 있는 원판만 빼낼 수 있다. (위에 것.. 더보기 이전 1 2 다음
