라이크위키

반응형

IT/알고리즘 : 「9」건

  1. 큐 (Queue) - 큐의 주요 기능, 순환 큐
  2. 스택 응용하기 - 사칙연산 계산기 만들기
  3. 링크드 리스트로 구현하는 스택
  4. 스택(Stack)의 개념 및 배열로 구현하는 스택
  5. 환형 링크드 리스트 (원형 링크드 리스트, Circular Linked List)
  6. 더블 링크드 리스트(Doubly Linked List)
  7. 링크드 리스트의 주요 연산 - 노드 추가, 노드 탐색, 노드 삭제, 노드 삽입
  8. 링크드 리스트의 주요 연산 - 노드의 생성과 소멸
  9. 링크드리스트(Linked List)

큐 (Queue) - 큐의 주요 기능, 순환 큐

큐 (Queue) - 큐의 주요 기능, 순환 큐 은행에서 먼저 온 순서대로 대기하는 줄을 만들어서 먼저 온 사람이 먼저 일을 보고 갈 수 있게 하듯이, 먼저 들어가고 먼저 나오는(FIFO(First In First Out), 또는 선입선출(先入先出)) 자료구조를 큐(Queue)라고 합니다. 큐는 작업을 처리하는 요소에 부하를 주지 않으면서도 처리 능력을 넘어서는 작업들도 놓치지 않고 수용할 수 있도록 돕는 역할을 합니다. 큐가 이처럼 '완충장치' 역할을 하는 사례는 아주 많습니다. 놀이공원의 롤러코스터에서 30인승 롤러코스터에 200명의 손님이 몰린다면, 롤러코스터는 자신의 능력 한계치인 30명을 태워서 레일로 나가고 나머지 170명은 큐에서 기다립니다. 손님이 몰린다고 하여 30명이 정원인 롤러코스터에..
IT/알고리즘

스택 응용하기 - 사칙연산 계산기 만들기

스택 응용하기 - 사칙연산 계산기 만들기 스택을 응용하여 '사칙 연산 계산기'를 만들어보려고 합니다. 정확히 말하자면 '수식 분석기 기반의 사칙 연산 계산기'라고도 할 수 있습니다. 계산기의 요구 조건은 간단합니다. 다음과 같이 사칙 연산 만으로 이루어진 식을 분석해서 풀 수 있으면 됩니다. 1 + 3.334 / (4.28 * (110 - 7729) ) 이 문제를 직접 푼다고 하면 이렇습니다. 가장 먼저 괄호 내에 있는 식을 풀 것입니다. 괄호가 중첩되어 있다면 가장 안쪽에 있는 괄호부터 풀 것입니다. 그리고 곱셈(*)과 나눗헴(/)을, 그 후에 덧셈과 뺄셈 계산을 할 것입니다. 하지만 이는 사람이기에 할 수 있는 계산입니다. 컴퓨터는 이와 같은 방법으로 계산할 수가 없습니다. 따라서 컴퓨터가 이 문제를..
IT/알고리즘

링크드 리스트로 구현하는 스택

링크드 리스트로 구현하는 스택 링크드 리스트로 스택을 구현하면 스택의 용량에 제한을 두지 않아도 된다는 장점이 있습니다. 링크드 리스트의 구조를 잘 떠올리며 링크드 스택에 대해 알아보도록 하겠습니다. 스택과 스택의 노드 표현하기 잘 알려진 것처럼, 배열과는 달리 링크드 리스트는 인덱스로 노드에 접근할 수 없습니다 .따라서 링크드 리스트로 스택을 구현하려면 노드는 자신의 위에 위치하는 노드에 대한 포인터를 가지고 있어야 합니다. 이러한 요구 사항을 반영한 노드 구조체는 다음과 같습니다. typedef struct tagNode { char* Data; struct tagNode* NextNode; } Node; 배열 스택에서와는 달리 Data 필드가 char* 형으로 선언되어있습니다. 이는 다음 번에 구현..
IT/알고리즘

스택(Stack)의 개념 및 배열로 구현하는 스택

스택(Stack)의 개념 및 배열로 구현하는 스택 스택 주차장 차를 몰고 여기저기 돌아다니다가 식사를 위해 주차장에 주차를 한 뒤 식당에 들어갔습니다. 식당에 들어갈 때에는 손님이 거의 없었지만 식사를 마치고 나올 쯤에는 손님들로 식당이 꽤 붐볐습니다. 이 때문에 주차한 차를 빼는 데에 문제가 생겼습니다. 식당의 주차장이 독특하게 생긴데다 열악했기 때문인데요. 폭이 좁고 긴 공터를 주차장으로 사용하고 있었기 때문입니다. 손님이 없을 때에 주차를 했기 때문에 가장 안쪽에 주차한 것이 화근이었습니다. 제 차 앞에 세 대의 차가 더 주차되어 있었기 때문이었습니다. 식사 중인 손님들을 방해하고 싶지는 않았지만 식당의 지배인을 통해 차 주인들을 모두 불러 앞의 차들을 모두 빼낸 다음에야 차를 빼고 나설 수 있었습..
IT/알고리즘

환형 링크드 리스트 (원형 링크드 리스트, Circular Linked List)

환형 링크드 리스트 (Circular Linked List) 환형 링크드리스트(Circular Linked List)는 머리(헤드)가 꼬리(테일)를 물고 있는 형태의 링크드 리스트입니다. 이를 제외하고는 링크드 리스트나 더블 링크드 리스트와 다른 것이 없습니다. 더블링크드 리스트, 혹은 링크드 리스트를 이용하여 아래와 같이 환형 링크드 리스트를 만들 수 있습니다. 테일의 다음 노드 포인터가 헤드를 가리키게 하면 됩니다. 헤드와 테일을 연결하여 얻을 수 있는 장점은 무엇일까요? "시작을 알면 끝을 알고 끝을 알면 시작을 알 수 있다"는 점입니다. 예를 들어 더블 링크드 리스트를 환형으로 구현하면 헤드의 앞 노드가LL_AppendNode() 함수의 성능을 획기적으로 개선시킬 수도 있고, 뒤에서부터 노드를 찾..
IT/알고리즘

더블 링크드 리스트(Doubly Linked List)

더블 링크드 리스트(Doubly Linked List) 더블 링크드 리스트(Doubly Linked List)란? 더블 링크드 리스트(Doubly Linked List)는 링크드 리스트의 탐색 기능을 개선한 자료구조입니다. 링크드 리스트는 노드를 찾으려면 헤드에서 테일 방향으로만 탐색을 할 수 있는 반면에, 더블 링크드는 양방향으로 탐색이 가능하다는 것입니다. 양방향 탐색이 가능한 것은 구조가 변경된 덕분입니다. 링크드 리스트의 노드가 다음 노드를 가리키는 포인터만을 가졌던 데 비해, 더블 링크드 리스트의 노드는 자신의 앞에 있는 노드를 가리키는 포인터도 가지고 있습니다. 그래서 더블 링크드 리스트의 노드는 뒤로 이동할 수 있을 뿐만 아니라 앞으로도 이동할 수 있습니다. 이것을 구조체로 표현하면 다음과 ..
IT/알고리즘

링크드 리스트의 주요 연산 - 노드 추가, 노드 탐색, 노드 삭제, 노드 삽입

링크드 리스트의 주요 연산 - 노드 추가, 노드 탐색, 노드 삭제, 노드 삽입 노드 추가 노드 추가 연산은 링크드 리스트의 테일 노드 뒤에 새로운 노드를 만들어 연결하는 것을 의미합니다. 즉, 꼬리를 덧붙이는 것입니다. SLL_CreateNode() 함수를 이용하여 자유 저장소에 노드를 생성한 다음, 새로 생성한 노드의 주소를 테일의 NestNode 포인터에 대입하면 될 것 같습니다. 노드 추가 연산을 수행하는 SLL_AppendNode() 함수는 다음과 같이 구현할 수 있습니다. /* 노드 추가 */ void SLL_AppendNode(Node** Head, Node* NewNode) { /* 헤드 노드가 NULL 이라면 새로운 노드가 Head */ if ( (*Head) == NULL ) { *Hea..
IT/알고리즘

링크드 리스트의 주요 연산 - 노드의 생성과 소멸

링크드 리스트의 주요 연산 - 노드의 생성과 소멸 이전 포스팅에서 기본적으로 링크드 리스트를 구축하고 링크드 리스트에 있는 자료를 사용하기 위해 필요한 연산은 다음 다섯 가지라고 설명했습니다. 노드 생성/소멸 노드 추가 노드 탐색 노드 삭제 노드 삽입 노드 생성/소멸 C언어로 작성된 프로그램은 세 가지 종류의 메모리 영역을 가집니다. 하나는 전역 변수나 정적 변수 등이 저장되는 정적 메모리(Static Memory)이고, 또 다른 하나는 지역 변수가 저장되는 자동 메모리(Automatic Memory), 그리고 마지막 하나는 자유 저장소(Free Store)입니다. 정적 메모리는 프로그램이 실행되면서 프로그램에서 사용될 전역 변수/정적 변수를 메모리에 할당한 후 프로그램이 종료될 때 해제하는 영역이기 때..
IT/알고리즘

링크드리스트(Linked List)

링크드리스트(Linked List) 배열의 한계 소프트웨어는 종종 프로그래머에게 배열 이상의 그 무엇을 요구할 때가 있습니다. 만약 임의의 디렉토리 내에 존재하는 파일의 목록을 소프트웨어가 필요로 한다면 어떻게 해야할까요? 그 디렉토리에는 파일이 전혀 없을 수도 있고, 10개도 안되는 파일만 존재할 수도 있습니다. 하지만 운이 나쁘면 수천, 수만 개의 파일이 있을 수도 있습니다. 분명한 사실 한 가지는 디렉토리 내에 존재하는 파일의 수는 프로그래머의 염원과는 상관없이 정해진다는 것입니다. '파일이 항상 10개 미만으로만 있으면 좋겠다.' 라는 염원 하나로 다음과 같이 배열을 선언하겠습니까? char* files[10]; 그렇다고 다음과 같이 무작정 큰 배열을 선언할 수도 없는 일입니다. 게다가 문제를 완..
IT/알고리즘
◀ 1 ▶
반응형
loading

티스토리툴바