본문 바로가기

C++

 (10)
스택 (Stack) 들어가며 대학교 수업에서 처음 스택에 대해서 배울 때 대체 저런 자료구조가 어디에 쓰일지 궁금했다. 이내 교수님께서 웹페이지에서 뒤로가기를 설명하시면서 스택에 대한 예시를 들어주셨을 때 단번에 이해할 수 있었다. 개념만 들었을 때 조금 독특하지만 사실 컴퓨터 곳곳에 쓰이는 자료구조라 지금은 너무도 친숙한 자료구조가 되어버렸다. 개념 및 특징 자료를 차곡차곡 쌓고 뺄때는 제일 최근에 쌓은 거부터 빼내는 일명 FILO 구조이다. 배열과 리스트 두가지 자료구조를 활용하여 구현할 수 있어 둘 다 구현해보았다. 이번 구현에서는 이전에 구현한 단일 연결 리스트 구현을 활용했는데 특별히 make 파일을 만들어 컴파일해보았다. 코드 https://github.com/yell0w-bear/data-structure/tr..
이중 연결 리스트 (Double Linked List) 들어가며 작심삼일, 벌써 자료구조공부를 시작한지 3일이 되간다. 이번에는 꾸준히 공부해서 자료구조를 전체적으로 한번 공부하는 기회가 됬으면 한다. 개념 및 특징 노드가 prev 포인터를 추가로 가진다는 점을 제외하고는 단일 연결 리스트와 거의 유사하다. 한 노드에서 앞뒤 노드의 정보를 바로 얻을 수 있기 때문에 오히려 구현은 단일 연결 리스트보다 단순했던 거 같다. tail을 구현할지말지 고민을 했지만, 책에서 tail에 대한 언급은 없어서 일단 tail 구현은 하지 않았다. 코드 https://github.com/yell0w-bear/data-structure/tree/main/double_linked_list 마무리 연결 리스트들은 그래도 이전에 밤새가며 구현했던 경험들이 있어서인지 조금은 수월하게 ..
원형 연결 리스트 (Circular Linked List) 들어가며 구현은 어제 해두고 글을 작성하지 않았다는 것을 발견했다. 역시 전문 블로거가 되려면 아직 한참 멀었다. 개념 및 특징 단일 연결리스트와 구현이 거의 동일한데, 한 가지 큰 차이점은 마지막 tail의 next가 첫번째 노드가 된다는 점이다. 코드 https://github.com/yell0w-bear/data-structure/tree/main/circular_linked_list 마무리 2일차! 구현 난이도가 아직 어렵지는 않지만 그래도 꾸준히 공부를 해나가고 있다는 점에 의의를 둔다.
[백준 G5] 행운의 문자열 (1342번) 문제 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작했다. 준영이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇 개 나오는지 궁금해졌다. 만약 원래 문자열 S도 행운의 문자열이라면 그것도 개수에 포함한다. 입력 첫째 줄에 문자열 S가 주어진다. S의 길이는 최대 10이고, 알파벳 소문자로만 이루어져 있다. 출력 첫째 줄에 위치를 재배치해서 얻은 서로 다른 행운의 문자열의 개수를 출력한다. 예제 입력 1 aabbbaa 예제 출력 1 1 #include #include #include #include #include using namespace st..
Dijkstra의 개념 및 구현 들어가며 오늘은 엄청 유명한 '다익스트라 알고리즘'에 대해 공부해 볼 예정이다. 그래프와 트리에 관한 알고리즘에 특히 약한 편이라 더더 열심히 해야할 것 같다. 개념 및 특징 한 정점에서 나머지 모든 정점까지의 최단 경로를 찾는 알고리즘 음수인 간선을 포함하는 경우 최단 경로를 찾을 수 없는 경우가 있음 구현 연결되지 않은 정점들 간의 거리는 INF(무한대)로 표현 알고리즘 모든 정점을 미방문 상태로 표시한다. 모든 정점 간의 거리를 INF(무한대)로 표시한다. 이어진 정점 간의 거리를 표시한다. 현재 정점(초기값은 시작점)을 방문 상태로 표시한다. 현재 정점과 이어진 정점들에 대해 (시작점에서 현재 정점까지의 거리) + (현재 정점에서 이어진 정점까지 거리) < (시작점에서 이어진 정점까지 거리)을 만..
02) 스택(Stack)의 개념 및 구현 들어가며 과외를 시작했다. 편입을 준비하는 학생인데 내가 사실 컴퓨터 분야 과외는 처음이고 편입 과외는 더더욱 처음이라, 뭐부터 시작해야할지 잘 모르겠다. 과외를 빌미삼아 자료구조랑 알고리즘을 더 열심히 정리하는 기회로 삼아야겠다. 오늘은 자료구조 중에 가장 기초라할 수 있는 스택(stack)에 대해 포스팅 해보고자 한다. 스택을 공부하면서 나에게 가장 어려웠던 점은, 이 스택이라는 용어를 너무 여기저기 쓴다는 점이었다. 자료구조에도 나오고 프로세스 구조에도 나오고 심지어는 C++ STL에서도 등장한다. 여기서 주목할 점은 스택은 LIFO의 방식으로 데이터를 처리하는 자료구조인데 이러한 자료구조를 따르는 모든 아키텍처에 스택이라는 이름을 붙여놨다는 점이다. 이 점만 기억하면 스택은 정말 쉬운 개념이다. ..
01) 힙(Heap)의 개념 및 구현 들어가며 알고리즘 카테고리의 정렬(sorting)에 대한 포스팅을 하고 있다. 오늘은 힙 정렬(heap sorting)에 대해 포스팅 하려고 했는데 이를 위해서는 힙(heap)에 대해 먼저 공부해야 했다. 따라서 오늘은 힙(heap)에 대해 포스팅 해보고자 한다. 개념 및 특징 완전 이진 트리 우선순위 큐를 위해 만들짐 최댓값이나 최솟값을 빠르게 찾기 위해 만들어짐 반정렬(느슨한 정렬) 상태 부모 노드의 키 값이 자식 노드의 키 값보다 크거나(혹은 작거나) 같은 이진 트리 중복 값을 허용 종류 최대 힙(max heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 최소 힙(min heap) 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 구현 보통 배..
[Sorting 05] Insert Sort의 개념 및 구현 들어가며 날이 엄청 춥다. 드디어 겨울이 오나보다. 오늘은 개념은 쉽지만 비효율적인 알고리즘 중에 하나인 'Insert Sort'에 대해 알아보자. 개념 및 특징 이미 정렬된 리스트를 앞에서 부터 값을 비교하여 자신의 위치를 찾아 삽입함으로써 정렬하는 알고리즘이다. in-place 알고리즘이다. 시간 복잡도: O(N2) 선택정렬이나 거품정렬에 비해서는 빠르다.* 알고리즘 앞에서부터 차례대로 이미 정렬된 리스트와 비교하여 자신의 위치를 찾아 삽입한다. 리스트의 모든 원소에 대해 위와 1과 같은 과정을 반복한다. 소스코드(C++) #include #include #include #include using namespace std; typedef vector::iterator IT; void insertSor..

티스토리툴바