코딩각

C언어 | 단순 삽입 정렬 (straight insertion sort) | 기본 정렬

단순 삽입 정렬은 (straight insertion sort) 말 그대로 선택한 요소를 압쪽으로 삽입하는 작업을 반복하여 정렬한다. 단순 선택 정렬과 비슷해 보이지만 삽입정렬은 왼쪽으로 삽입하고 나머지를 오른쪽으로 미는 방식이고 단순 선택 정렬은 값이 가장 작은 요소를 앞으로 끌고오는 방식이다. 둘다 시간 복잡도는 O(n^2) 이다. 단순정렬 3종 세트(버블, 선택, 삽입)의 시간복잡도는 모두 O(n^2) 이다. 이 세개는 세트로 배워두는게 좋다. n2 는 굉장히 큰 숫자인데 n이 작업의 단위를 말하는 것이면 100개의 요소가 있는 배열은 정렬한번에 1만번 작업이 실시되고, 1000개의 요소를 정렬하려면 1000,000 회(100만) 작업이 필요하다는 것이다. 실로 놀라운 숫자라고 할 수 있다. 컴퓨터..
알고리즘(Algorithm)/C언어 알고리즘 2020. 11. 29. 16:59

C언어 | 이중 연결 리스트 (Doubly Linked List) | 자료구조

C언어 이중 연결 리스트 (Doubly Linked List) 단일 연결 리스트(singly linked list) 에서는 한쪽 방향으로 노드를 연결한다. 이중 연결 리스트는 두방향으로 노드를 연결한 다는 점이 다르다. 양방향으로 이동 가능하다는 것은 자료형태에 다양한 가공을 할 수 있다는 것을 의미한다. 이 포스팅에서는 C언어로 기본적인 이중 연결 리스트를 설계해본다. 이중 포인터를 사용하는 경우도 많이 있는데 여기서는 일반 포인터를 사용한다. 확실히 이중 연결 리스트는 하나의 노드에 prev 와 next 두 방향의 포인터가 들어있기 때문에 이중 포인터를 사용하는게 편리한 경우가 있다. 그런데 코드의 가독성은 떨어지게 되므로 사용에 주의할 필요는 있다. 이중 포인터를 사용하지 않아도 양방향으로 이동이 ..
알고리즘(Algorithm)/C언어 알고리즘 2020. 11. 25. 05:11

C언어 | 스택(Stack) 만들기 | 동적 할당 | POP, PUSH 함수 |자료구조

스택(Stack) 자료구조 스택은 우리 생활에서 흔히 보이는 자료구조다. 접시를 쌓아놓은 모습을 스택이라고 한다. 맨 아래 접시를 사용하기 위해서는 꽤 많은 사람이 식사를 해야 한다. 웹브라우저의 URL 도 스택을 사용한다. 뒤로가기를 누르면 마지막에 열람한 인터넷 주소로 돌아간다. Ctrl-Z 로 되돌리기도 스택이다. 마지막에 한 행동을 기억해놨다가 그 행동을 취소한다. 스택의 구조를 LIFO 라고 한다. LAST IN FIRST OUT 마지막에 온 데이터가 먼저 나온다. FIFO FIRST IN FIRST OUT 먼저 온 사람이 먼저 서비스를 받는다. FIFO 를 사용하는 큐와 대비된다. 살다 보면 항상 먼저 일어난 일이 나중에 끝난다는 법이 없는 것 처럼 Stack 은 가장 최근에 일어난 일을 소환..
알고리즘(Algorithm)/C언어 알고리즘 2020. 11. 24. 17:55

C언어 | 선택 정렬 (selection sort) | 파이썬 선택정렬

선택정렬은 직관적으로 이해하기 쉬운 정렬 방식이다. 예를 들어 여기 숫자 카드가 5장 있다. [2, 1, 5, 3, 4] 오름차순으로 어떻게 정렬하는가? 누구나 알 수 있다. [2, 1, 5, 3, 4] 카드에서 작은 숫자 순으로 뽑아서 오른쪽에 놓는다. 두번째, 첫번째, 네번째, 다섯번째, 세번째 순으로 뽑아서 나열한다. [1, 2, 3, 4, 5] 가 될 것은 의심의 여지가 없다. 뽑은 카드의 순서를 표시하면 CARD[2] CARD[1] CARD[4] CARD[5] CARD[3] 이 나온다. 이제 컴퓨터에서 어떤 코드를 구현하는가만 남아있다. 사람에겐 달리 생각이 필요없는 일도 컴퓨터에게 있어서는 구체적인 명령어와 지시가 필요하다. 온라인의 올라와있는 기본 자료들은 서로 약간의 차이가 있는데 다들 비..
알고리즘(Algorithm)/C언어 알고리즘 2020. 11. 22. 11:37

C언어 | 이진 탐색 트리( Binary Search Tree) 만들기 | 추가, 삭제, 검색

이진 탐색 트리 C언어 *이진검색트리 (Binary Search Tree)의 조건 - 이진 트리는 루트를 중심으로 노드가 왼쪽에 하나 오른쪽에 하나씩 연결된다. - 노드 N(어느 한 노드)을 기준으로 왼쪽 트리의 키값은 노드 N보다 작아야 하고, 오른쪽 트리의 키 값은 노드 N보다 커야 한다. - 같은 키값을 갖는 노드는 없다. 이 포스팅에서는 C언어로 이진 탐색 트리 자료형를 만들어 본다. 이진 탐색 트리는 값을 입력시 자동으로 정렬된다. 특히 이진 탐색 트리에는 중복된 값이 입력되지 않는다. 이진 검색이라는 용어가 있는데 엄밀히 말하면 이진 검색과 이진 탐색 트리는 같은 것이 아니다. 이진 검색은 오름차순으로 정렬된 숫자의 배열에서 검색하는 알고리즘이고, 이진 탐색 트리는 위와 같은 조건을 가진 자료..
알고리즘(Algorithm)/C언어 알고리즘 2020. 11. 21. 18:00
◀ 1 2 3 ▶

티스토리툴바