본문 바로가기

자료구조15

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.

[이분 탐색] 이분 탐색(Binary Search) 이란 ? 이분 탐색 두 이, 나눌 분을 써서 이분인가? 정답, 이분 탐색은 두개로 나누어서 탐색하는 것이다. 예를 들어, 1부터 10까지 있다고 생각해보자. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 우리가 8을 찾을 때, 눈으로 바로 보이니까 위치를 파악할 수 있다. 하지만 몇 번째에 있는가? 배열은 0번째부터 시작하니 7번째에 있다는 것을 알 수 있다. 컴퓨터 배열 인덱스 개념이 없는 사람들은 8번째라고 답할 것이다. 즉, O(1) 시간이다. 그럼, {1, 4, 7, 10, 12, 23, 30, 35, 100, 120} 이 있을 때, 35의 위치는? 우리는 앞에서 값을 세어가면서 몇 번째에 있는지 알 것이다. 즉, O(N) 시간이다. 100만개의 숫자가 있다면? 우리는 100만개를 일일이 세다가.. 2024. 2. 1.

백준 - [BOJ 12015] 가장 긴 증가하는 부분 수열 2 백준 온라인 져지(BOJ)에서 제공 되는 12015번 문제는 선행 문제가 있다. 가장 긴 증가하는 부분 수열 나는 위 문제를 먼저 풀어보고 오는 것을 추천한다. 해당 문제는 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)로 유명한 문제이다. 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤.. 2024. 2. 1.

1. 자료구조란? Data Structure 컴퓨터는 Data의 집합체입니다. 컴퓨터에서 Data를 다루기 위한 방법이 있겠죠? 실제로 사람이 생각하기에 직관적이거나 수학적, 논리적으로 해결할 수 있는 사고를 컴퓨터의 입장에서 표현한 것이 자료구조입니다. 컴퓨터는 사람과 다르게 생각을 할 수 없기 때문에 이해할 수 있도록 '명령'을 해주어야 합니다. How ? 어떻게 컴퓨터에게 명령을 해야 할까요? 기본적으로 컴퓨터는 변수에 값을 할당하고 입, 출력을 통해 우리가 확인할 수 있습니다. 이 때, 1, 2, 3, 4, 5, 7 이 있을 때 '6'을 추가하는데 순서를 유지하고 싶습니다. 즉, 결과를 1 2 3 4 5 6 7로 나타내고 싶습니다. 방법은 무수히 많은데요. vector arr = {1, 2, 3, 4, 5, 7};.. 2024. 1. 26.

이전 1 2 다음

티스토리툴바