이번 포스팅에서는 스택의 정의와 성질, 구현 방법, 활용에 대해서 정리합니다. 스택은 큐, 데큐와 서로 비슷한 부분이 많기 때문에 함께 공부하는 것을 적극 추천합니다.또한 스택은 비교적 여러 알고리즘에서 활용합니다. 따라서 어렵더라도 제대로 이해하고 넘어가야 합니다. 1. 스택의 의미와 특징스택이란?마지막으로 들어온 원소가 제일 먼저 나가는 자료구조더 이해하기 쉽게 풀어보면 한쪽 입구만 뚫린 터널이라고 생각할 수 있다. 이 구조는 데이터들이 한쪽으로만 들어갔다가 나오며 무언가 쌓는 모양을 생각할 수 있다. 이러한 형태 때문에 "쌓다"라는 의미에서 스택(stack)으로 불린다. 스택의 특징LIFO(Last In First Out)의 구조를 가진다.원소의 추가/제거/확인이 모두 O(1)이다.최상단의 원소에만..

이번 포스팅에서는 선형 자료구조인 큐에 대해서 알아보겠습니다. 큐는 스택, 데큐와 비슷한 점이 아주 많기 때문에 이들과 같이 비교하면서 보는게 좋습니다. 1. 큐 FIFO의 규칙을 가지는 자료구조입니다. 선입선출이라고도 합니다. 마치 놀이공원 대기줄을 연상시키죠. 2. 구현 배열을 이용해 구현할 수 있지만 head와 tail이 계속해서 밀리는 문제때문에 연결리스트를 이용한 원형 큐로 구현하는 것이 효율적입니다. 하지만 C++의 STL에는 이미 선형 큐가 구현되어 있습니다. STL의 queue를 쓰는 것을 적극 추천합니다. 다음은 큐 구현을 연습하기에 좋은 기본적인 문제들입니다. [백준 10845] 큐 [백준 18258] 큐2 [백준 2164] 카드2 3. 활용 큐는 주로 한 방향으로 처리되는 데이터들을 ..

자료구조와 알고리즘은 컴퓨터 과학에서 기초로 다룰 만큼 근간이 되는 학문입니다. 이번 포스팅에서는 자료구조와 알고리즘에 대해 알아보고 둘의 관계를 다루어 보겠습니다. 이번 글에서는 전반적으로 흐름에서 자료구조와 알고리즘의 관계에 대해 다룰 예정입니다. 구현 방법, 예시 등은 다른 글에서 다루었으니 필요하시면 찾아보세요! 1. 자료구조 자료구조란? 효율적으로 데이터를 접근/수정하기 위해 데이터를 조직화하는 방법입니다. 그렇다면 자료구조는 왜 중요할까요? 어떤 자료구조를 사용하느냐에 따라 데이터의 처리 속도나 메모리 사용량이 크게 달라집니다. 따라서 자료구조는 프로그램의 실행 속도를 결정짓는 매우 중요한 개념입니다. 자료 구조의 특징 상황에 맞는 자료구조를 선택하려면 다음 세 가지 특징을 만족해야 합니다. ..

이진 트리의 자식 표현 방법 이진 트리는 트리와 달리 자식의 Left, Right에 대한 정보가 반드시 필요하다. 따라서 일반적인 그래프로 구현하기 힘들다. 배열, 구조체, 연결리스트 등으로 표현가능하지만 트리의 구조를 이용하여 배열로 간단하게 나타낼 수 있다. 이진 트리의 4가지 순회 방법 1. 레벨 순회(Lever Travel) Level Travel은 트리이 깊이를 순차적으로 탐색한다. 방문 순서는 cur → Left Child → Right Child이다. 레벨 순회는 BFS와 유사한 구조를 가진다. 구현은 일반적인 BFS처럼 해주면 된다. 이를 코드로 구현하면 다음과 같다. void levelTravel(){ queue q; q.push(1); while(!q.empty()){ int cur =..

[목차] Deque이란? Deque 기능 주요 기능 소개 구현해보기 주요 기능들의 성능 분석 예제 코드 Deque의 특징 예제 문제 1. Deque이란? 선형 자료구조에는 Stack, Queue, Deque, Linked List가 있다. Duque는 선형 자료구조의 한 종류이다. Double Ended Queue의 줄임말로 양쪽에서 삽입과 삭제가 가능한 Queue를 말한다. 주로 배열을 뒤집어서 원소를 추가/삭제하는 경우에 Deque를 쓰면 효율적으로 구현할 수 있다. C++과 java 모두 Deque을 지원한다. 따라서 그냥 가져다 쓰면 된다. 여기서는 C++에서 Deque의 주요 기능들을 간단히 소개하고 구현해본다. 예제는 [백준 5430번]을 이용한다. 2. Deque의 기능 1) 주요 기능 문제..

이번 글에서는 해시 테이블에 대해 알아보겠습니다. 삼성 SW역량테스트 B형에서는 C++ 컨테이너, 파이썬의 모듈 등 이미 구현된 자료구조는 쓸 수 없어서 직접 구현해야 합니다. 그 경우를 제외하고는 해시 테이블을 직접 구현하는 일은 거의 없으므로 구현보다는 기능과 활용을 중심으로 다룰 예정입니다. 구현은 접은글로 자세하게 작성했으니 궁금하면 참고해 주세요.  1. 해시 테이블이란?해시 테이블은 아주 많은 양의 데이터를 저장하고 접근할 때 빠른 속도로 찾을 수 있는 자료구조입니다. 코테같은 알고리즘에서는 주로 1억이 넘어가는 데이터 ????를다루는데 쓰일까?많은 양의 데이터를 저장하고 탐색하는 경우 아무리 빨라도 O(n)의 시간복잡도를 가집니다. 하지만 해시 테이블은 key, value를 이용하여..

1. 괄호쌍의 유효성 괄호쌍의 유효성이란 열린괄호' ( '와 닫힌 괄호' ) '가 서로 순서와 짝이 맞게 이루어져있는지 판단해주는 방법이다. 일반적으로 괄호쌍을 다룰 때에 소괄호' ( '가 주로 판단대상이지만 중괄호' { '나 대괄호' [ '로 확장하여 판단하기도 한다. 괄호쌍이 유효한 경우 ( ) ( ( ) ) ( [ ] ) 괄호쌍이 유효하지 않은 경우 ) ( { ( } ) { } ) 2. stack을 이용한 괄호쌍 유효성 검사하기 알고리즘 그러면 어떻게 이를 판단할 수 있을까? 위에서 괄호쌍이 유요하지 않은 경우는 괄호의 짝이나 순서 또는 개수가 맞지 않는다는 것을 확인할 수 있다. 데이터가 입력되었을 때 현재까지 입력된 상태를 유지하고 제일 마지막에 입력된 값과 비교해야 함을 느낄 수 있다. 따라서..

트리란? 트리란 싸이클이 없는 무방향 그래프를 말한다. 싸이클이 존재하지 않아서 모든 노드가 루트가 될 수 있다. 마치 실로 연결된 구슬이 있는데 한 구슬을 잡아서 들어올릴 때마다 그 구슬이 루트가 되고 트리 구조가 형성되는 것과 비슷하다. 트리 순회하기 그래프의 구조를 가지므로 BFS와 DFS를 이용할 수 있다. 이 과정에서 부모의 정보 or 깊이의 정보가 필요한 경우 중간중간에 기록해주면 된다. 1. BFS void bfs(int root){ queue q; q.push(root); while(!q.empty()){ int cur = q.front(); cout