본문 바로가기

연결리스트6

백준 - [BOJ 12094] A와 B 백준 온라인 져지(BOJ)에서 제공 되는 12094번 문제는 그리디(Greedy, 탐욕법) 유형이다. 해당 문제는 code.plus 중급 1/3, 그리디 알고리즘에 게시된 문제이다. 문제 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다. 문자열의 뒤에 A를 추가한다. 문자열을 뒤집고 뒤에 B를 추가한다. 주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 .. 2024. 2. 29.

6. STL 사용하기 - std::list STL 이란? C++ 에서 제공하는 STandard Library를 STL이라고 한다. 자바에서는 자바에서 제공하는 API라고 볼 수 있다. 지금까지 list에 대해 직접 설계해보았고 list에 대한 설명이 충분했다. 이번에는 STL을 직접 사용하면서 어떤 기능이 있고 언제, 어떻게 사용할 지 생각해보도록 하자. ※ 시간이 오래 걸리는 Method는 제외한다. (효율적 사용) std::list Construct Method Description (constuctor) 리스트 생성시 입력 값 operator= = 기호에 대한 연산 방법 Iterators Method Description begin() 리스트 Head에 속한 데이터 위치 end() 리스트 마지막 위치 != Tail, null 값 rbegin.. 2024. 2. 11.

5. 원형 연결 리스트 (Circular Linked List) 원형 연결 리스트란? 단순 연결 리스트에서 끝이 처음과 연결되어 있는 형태를 원형 연결 리스트라고 합니다. STL에도 구현되어있지 않고 아직 학생 수준이지만, 실제로 사용되는 경우도 본 적이 많이 없습니다. 그래서 단순하게만 만들어보도록 할 것인데, 이중 연결 리스트 형태로 만들려고 합니다. (실제로 순환적인 요소는 큐 또는 재귀를 많이 사용하는듯) 원형 연결 리스트(Circular Linked List) 구현하기 많은 기능을 추가하지는 않겠습니다. 노드 #pragma once template class Node { public: Node(T data); T getData() const; Node* getNext() const; Node* getPrev() const; void setNext(Node* .. 2024. 2. 10.

4. STL 따라잡기 - 이중 연결 리스트 (Doubly Linked List) 구현 이중 연결 리스트란 ? 여기서 연결 리스트에 대한 개념을 알게 되었고 여기서 단순 연결 리스트를 구현해보았다. 또, 앞선 포스팅에서 연결에 대한 방법을 말했는데 '이중 연결 리스트' 는 양방향(이중)으로 구성된 자료구조이다. 즉, 싱글 연결 리스트는 코스 여행이라면 이중 연결 리스트는 자유 여행이다. 이에 대해선 내가 생각한 예시이기 때문에 한 번 생각해보고 비슷한 예시를 찾아서 본인만의 개념으로 이해하길.. 이번 STL 따라잡기 포스트는 standard library인 list를 만들어보겠다. 먼저, list에 어떤 기능이 있는지 한 번 알아보자. 우리는 STL list에 어떤 기능이 구현되어있는지 파악한 뒤에 이를 정리할 것이다. 깃허브 이슈에 구현할 내용을 작성하고 이를 바탕으로 레파지토리에 저장할.. 2024. 2. 7.

3. STL 따라잡기 - 단순 연결 리스트 (Singly Linked List) 구현 단순 연결 리스트란 ? 이전 2. Linked List (연결 리스트) 포스트에서 설명된 내용을 기반으로 설명하겠습니다. 연결리스트는 데이터 간에 '연결'되어 있다고 했는데, 연결은 아래와 같이 두 가지 방법이 있다. A 에서 B로 갈 때(단방향), A ㅡ> B 또는 B ㅡ> A A 에서 B로 가고 B에서도 A로 갈 수 있을 때(양방향), A B 또는 A ㅡ B 단순 연결리스트는 이 중, 단방향에 대한 정보를 사용하는 것이 단순 연결리스트이다. 대신, 주의할 점이 있다. A가 시작점, B가 종점인 경우에는 B에서 A로 갈 수 없다. 즉, 순환이 발생하지 않는다는 점이다. A ㅡ> B ㅡ> A ㅡ > B ( X ) A ㅡ> B ㅡ> 끝 ( O ) 단순 연결리스트는 이게 끝이다. 그럼, 주로 어떻게 사용되고.. 2024. 2. 4.

2. 연결 리스트 (Linked List) 연결 리스트란 ? 먼저, List를 생각하면 쭉 ~ 나열되어 있는 것이 떠오르시나요? 연결 리스트는 말 그대로 쭉 ~ 나열되어 있는 것입니다. 하지만 데이터를 서로 연결하고 있는 것이죠. 어? 쭉 ~ 나열되어있고 연결되어있는 것은 '배열' 아닌가요? 맞습니다. 자료구조의 기본이자 데이터가 순차적으로 나열되어 있는 것은 배열입니다. 그럼 연속된 데이터를 표현하는 방법으로는 배열(Array)가 있는데 왜 Linked List를 사용하나요? 배열과 Linked List에는 엄연한 차이가 있습니다. 앞선 포스팅에서 각 자료구조는 필요에 따른 사용처가 있고, 사용자가 유동적으로 사용해야 함을 표현했습니다. 그래서 배열이라는 자료구조에 대해 알고 Linked List라는 자료구조와의 차이점을 알아야합니다. 차이점을.. 2024. 2. 4.

이전 1 다음

티스토리툴바