본문 바로가기
728x90
반응형

Datastructure/[Algorithm problem]

#2-5. 스택의 개념과 알고리즘 / 함수 2023. 9. 12. 스택과 큐는 프로그래밍에서 가장 고전적인 자료구조이며, 그중 스택은 거의 모든 애플리케이션을 만들 때 사용하는 기본 자료 구조이다. 스택의 개념 스택의 기본 개념을 프로그래밍 시각에서 설명하면 다음과 같다. 입력과 출력을 한 방향으로 제한한 자료 구조 스택은 배열과 연결리스트와 비교하면 비교적 간단한 구조로, 삽입과 삭제에서 용이하다. 연결리스트에서 새로운 노드를 삽입하려면 기존의 연결리스트에서 새로운 노드가 삽입될 위치를 검색하고 링크를 연결시켜야 하기 때문이다. 스택은 이러한 배열과 연결리스트에 비해 구조가 간단하다. 스택을 단순하게 표현하면 바닥부터 데이터를 쌓는 형식이다. 이렇게 데이터를 쌓는 과정을 푸시(push)라고 한다. 반면 가장 위에 있는 데이터부터 사용하는데 이를 팝(pop)이라고 한다..
#2-4. 이중 연결 리스트의 생성 2023. 9. 7. 이전 포스팅까지 다룬 연결리스트는 링크를 하나만 갖는 단일 연결리스트이다. 그런데 연결리스트에는 2개의 링크를 갖는 이중 연결리스트와 연결리스트가 원형으로 구성된 원형 연결리스트가 있다. 이번 차시에는 이중 연결리스트를 기준으로 다른 구조의 연결리스트를 살펴보자. 이중 연결리스트 이중 연결리스트 각각의 노드가 다음 값 위치를 저장하는 next 구조체 포인터와 이전 값 위치를 저장하는 pre 값을 가진다. 이중 연결리스트는 haed 노드와 tail 노드를 가지며 두 노드는 연결되어 있지 않다. 원형 (이중) 연결리스트 각각의 노드가 next와 pre 구조체 포인터를 가진다는 점에서 일반 이중 연결리스트와 같으나 head 노드와 tail 노드가 서로 연결되어 원형의 형태를 이룬다. 이중 연결리스트의 삽입과 ..
#2-3. 연결 리스트의 삽입과 삭제(2) : 삭제 2023. 9. 7. 지난 포스팅에서는 단일 연결리스트의 삽입에 대해 알아보았다. 이번 포스팅에서는 연결리스트의 삭제에 대해 알아보도록 하자. https://udangtangtang-cording-oldcast1e.tistory.com/182 #2-3. 연결 리스트의 삽입과 삭제(1) : 삽입 지난 포스팅에서는 add 함수를 이용해서 원하는 순서에 원하는 데이터를 저장하는 코드를 짜보았다. 코드는 정상적으로 작동했지만 현재 단일 연결리스트를 다루는 것에 비해 add 함수는 이중 연 udangtangtang-cording-oldcast1e.tistory.com 단일 연결리스트의 삭제 알고리즘 삭제 알고리즘은 삽입 알고리즘의 변형이라고 생각하면 된다. 단일 연결리스트의 삭제 알고리즘의 로직은 다음과 같다. 삭제하고 싶은 데이터를..
#2-3. 연결 리스트의 삽입과 삭제(1) : 삽입 2023. 9. 6. 지난 포스팅에서는 add 함수를 이용해서 원하는 순서에 원하는 데이터를 저장하는 코드를 짜보았다. 코드는 정상적으로 작동했지만 현재 단일 연결리스트를 다루는 것에 비해 add 함수는 이중 연결리스트를 기준으로 작성된 코드라서 불필요한 요소가 존재했고 알고리즘이 다소 복잡했다. 이번 포스팅에서는 가장 간결하고 단순한 단일 연결리스트의 삽입 알고리즘을 짜보도록하자. 단일 연결리스트의 생성 로직은 다음과 같다. 단일 연결리스트의 구조체 선언 헤드 노드의 동적할당 기본 노드의 동적할당 및 데이터 저장 새로운 노드를 추가할 plus 함수/ insert 함수 작성 plus 함수 연결리스트의 요소와 관계 없이 가장 마지막에 삽입 insert 함수 특정 조건에 의해 새로운 노드를 특정 위치에 삽입 이때 plus 함수와..
#2-3. 연결 리스트의 삽입과 삭제: 이중 연결 리스트를 곁들인,, 2023. 9. 5. 이전 포스팅에서는 연결리스트의 생성을 알아보았다. https://udangtangtang-cording-oldcast1e.tistory.com/180 #2-2. 단일 연결 리스트의 생성 단일 연결리스트의 특징 배열과 단일 연결리스트는 하나 이상의 데이터를 저장하는 면에서 기본 개념에서 배열과 거의 같다. 그렇다면 배열을 사용하지 않고 연결리스트를 사용하는 이유는 무 udangtangtang-cording-oldcast1e.tistory.com 해당 포스팅에서는 연결리스트의 생성과정을 다시 복습하고 연결리스트의 삽입과 삭제함수에 대해 알아보자. 연결리스트의 생성 연결리스트 생성의 순서는 다음과 같다. 연결리스트의 구조체 선언: 인자로는 데이터 값을 저장할 변수, 다음 노드의 구조체 포인터를 가진다.(단일 ..
#2-2. 단일 연결 리스트의 생성 2023. 9. 4. 단일 연결리스트의 특징 배열과 단일 연결리스트는 하나 이상의 데이터를 저장하는 면에서 기본 개념에서 배열과 거의 같다. 그렇다면 배열을 사용하지 않고 연결리스트를 사용하는 이유는 무엇일까. 단일 연결리스트의 장점은 다음과 같다. 단일 연결리스트의 장점은 배열의 단점과 같다. 배열은 연속적인 데이터를 저장하며 같은 자료형을 갖는 데이터의 집합이다. 이때 배열은 생성할 때 데이터를 저장하는데 필요한 모든 메모리를 한번 확보해 사용한다. 따라서 프로그램이 실행되는 중간에 배열을 크기를 바꿀 수 없다. 즉, 배열 안에 저장되어 있는 값들을 정렬할 때에도 메모리에 저장된 있는 각각의 값을 바꿔야 하는 것이다. 단일 연결리스트는 이러한 배열의 단점을 해결한다. 배열은 연속된 메모리를 사용하며 총 메모리가 고정되어 ..
728x90
반응형

티스토리툴바