https://cascade.tistory.com/70 [열혈자료구조] 3강. 연결 리스트(Linked List) 1 - (2) * 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. https://cascade.tistory.com/69 [열혈자료구조] 3강. 연결 리스트(Linked List) 1 - (1) * 본 글은 [윤성우의 cascade.tistory.com 앞서 열혈자료구조 교재에서 배열로 정의한 리스트를 구현하고, Point 라는 구조체(2차원 좌표평면 상의 점)를 정의하여 리스트 안에 이 구조체를 저장할 수 있도록 하는 코드를 공부하였다. 본 포스팅에서는, 두 개의 Point (시작점, 끝점)을 변수로 가지는 유향선분(Directed Lin..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 추상 자료형(Abstract Data Type, ADT) 추상 자료형 = 각 기능의 구현 등 세부적인 내용은 나타내지 않고, 기능 그 자체만 나열한 것 예를 들어, 지갑을 정의하는 추상 자료형에 대해 생각해 보자. 지갑에는 100원짜리 동전과 5000원짜리 지폐가 들어갈 수 있다. 각 화폐의 개수를 변수로 하는 구조체를 이용하여 지갑을 정의하자. typedef struct _wallet { int num_coin_100; int num_bill_5000; }Wallet; 또한, wallet이라는 자료형에 관련된 연산을 결정하는 것도 자료형을 정의하는 데 필요하다. int TakeOutMoney(Wall..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 재귀는 자료구조와 알고리즘에서 매우 중요한 요소이다. 재귀함수의 기본적 이해 void Recursive(){ printf("Recursive Call\n"); Recursive(); } 재귀함수는 위와 같이 함수 안에서 함수를 다시 호출하는 형태이다. 그러나 Recursive의 정의 부분에서 Recursive를 호출하고 있는데, 정의가 끝나지 않은 함수를 다시 호출하는 것이 가능한가? 재귀함수가 작동할 때 아래와 같이 메모리상에서 함수의 복사본을 여러 개 만들고 다시 호출한다. 즉, 함수의 명령문을 실행할 때 CPU로 불러와서 사용하는데, 명령문을 실행하는 중간에 재귀 조건이 등장한다면 CPU로 하나 ..

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 자료구조 vs 알고리즘 자료구조: 데이터의 표현 및 저장 방법 알고리즘: 표현 및 저장된 데이터를 대상으로 하는 문제의 해결방법 즉 데이터 자체를 다루는 것이 자료구조, 데이터를 가지고 문제를 해결하는 것이 알고리즘이다. ex) 자료구조의 예시: 배열의 선언 int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 알고리즘의 예시: 반복분의 구성 for(idx=0; idx

무작위로 N개의 수가 들어있는 리스트가 있다고 하자. 이 안에 특정 수 x가 들어있는지 찾는 최적의 알고리즘은 무엇일까? 이런 류의 문제를 탐색(searching)문제라고 한다. 탐색 문제에는 크게 세 가지 알고리즘이 있다. 선형 탐색(linear searching) 복잡도 : O(N) 선형 탐색은 N개의 수를 하나씩 차례대로 x인지 비교하는 방법이다. 이는 가장 간단한 알고리즘이지만 N이 커질 때 복잡도가 크게 늘어난다. 파이썬의 in 연산자가 선형 탐색을 이용한다. 이진 탐색(binary searching) 복잡도 : O(logN) 정렬된 리스트에서 사용 가능한 알고리즘으로, 아래의 순서로 진행된다. 리스트의 중간 인덱스를 잡고, 해당 인덱스의 값을 x와 비교하여 같으면 종료한다. 다르다면, 크기를 ..

스택 구조란, 쌓여 있는(stack) 더미처럼 된 자료구조를 말한다. 그림처럼 쌓은 수건을 위에서부터 사용하면서, 빨래한 새 수건을 다시 위에 쌓으면 아래 있는 수건은 계속 안 써서 먼지가 쌓인다. 이 구조가 스택 구조이다. 스택 구조는 나중에 들어온 데이터가 먼저 나가는 LIFO(Last In, First Out) 구조이다. 또한, 스택에 데이터를 넣는 것을 push, 데이터를 (위에서) 빼는 것을 pop이라고 한다. 백준 9012번: 괄호 백준 9012번(괄호)는 스택 문제의 대표적인 유형이다. 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid..