전체 글

알고리즘 설명 DFS(Depth First Search) 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 알고리즘 수행 과정 시작하는 칸을 스택에 넣고 방문했다는 표시를 남긴다. 스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행한다. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입한다. 스택이 빌 때까지 2번을 반복한다. 모든 칸이 스택에 한 번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N)이다. 이전 BFS의 수행 과정과 비교해보았을 때, DFS는 스택을 쓴다는 차이만 존재한다. 큐를 쓰면 BFS이고, 스택을 쓰면 DFS가 된다. DFS와 BFS는 노드의 방문 순서에도 차이가 있다. B..

알고리즘 설명 BFS(Breadth First Search)는 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다. 원래 BFS는 그래프라는 자료구조에서 모든 노드를 방문하기 위한 알고리즘이다. 여기서 그래프는 정점과 간선으로 이루어진 자료구조를 말한다. BFS 과정 시작하는 칸을 큐에 넣고 방문했다는 표시를 남긴다. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행한다. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입한다. 큐가 빌 때까지 2번을 반복한다. 모든 칸이 큐에 1번씩 들어가므로 시간 복잡도는 칸이 N개일 때 O(N)이다. 만약 행이 R개이고 열이 C개이면 시간 복잡도는 O(RC)이..

수식의 괄호 쌍이란? 위 식은 계산이 가능한 올바른 식이지만, 아래 식은 괄호가 이상하게 배치되어 있다. 수식의 괄호 쌍이란 주어진 괄호 문자열이 올바른지 판단하는 문제이다. 문제 해결을 위한 관찰 보편적인 방법으로는, 안쪽부터 짝 맞추기를 해서 괄호를 지워나가는 방법이다. 짝이 모두 맞으면 올바른 괄호 쌍이고, 그렇지 않으면 올바르지 않은 괄호 쌍이다. )의 개수가 (의 개수를 넘지 않아야 한다. 괄호가 여러 종류일 때에는 여는 괄호와 닫는 괄호의 개수만으로는 판단할 수 없다. 대신 짝이 되는 소괄호() 와 중괄호{} 를 지우는 방법은 여전히 잘 동작한다. 이 방법은 배열로 구현할 경우, 최대 N번 중간에 있는 원소의 삭제가 발생하기 때문에 O(N2)이고 연결리스트로 구현할 경우, O(N)이다. 스택을..

정의와 성질 덱은 양쪽 끝에서 삽입과 삭제가 전부 가능하다. 자료구조의 덱은 deque이고 Double Ended Queue라는 뜻을 가지고 있다. 덱의 성질 원소 추가/제거의 시간 복잡도는 O(1)이다. 제일 앞/뒤 원소 확인의 시간 복잡도는 O(1)이다. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능하다. 그러나 STL deque에서는 인덱스로 원소에 접근할 수 있다. 기능과 구현 배열의 형태로 덱을 구현해 보았다! STL deque STL deque은 매우 독특하게 double ended queue보다는 vector와 느낌이 비슷한데, front에서도 O(1)에 데이터의 추가와 제거가 가능하다는 느낌이 강하다. insert, erase 함수가 있고 인덱스로 원소에 접근할 수도 있..

정의와 성질 큐는 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. 스택에서는 먼저 들어간 원소가 나중에 나왔는데, 큐에서는 먼저 들어간 원소가 먼저 나오게 된다. 스택을 FILO(First In Last Out)라고 한 것과 비슷하게 큐를 FIFO(First In First Out)라고 하기도 한다. 큐의 성질 원소 추가/제거의 시간 복잡도는 O(1)이다. 제일 앞/뒤 원소 확인의 시간 복잡도는 O(1)이다. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능하다. 기능과 구현 배열 형태로 선형 큐를 구현해 보았다. STL queue 큐가 비어있을 때 front, back, pop을 호출하면 런타임 에러가 발생할 수 있으므로 주의해야 한다. 출처: 바킹독님 블로그

정의와 성질 스택은 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조이다. 구조적으로 먼저 들어간 원소가 제일 나중에 나오게 된다. 이를 FILO(First In Last Out) 자료구조라고 부르기도 한다. 큐와 덱도 스택처럼 특정 위치에서만 원소를 넣거나 뺄 수 있다. 그래서 스택, 큐, 덱을 묶어서 Restricted Structure라고 부르기도 한다. 스택의 성질 원소의 추가/제거의 시간 복잡도는 O(1)이다. 제일 상단의 원소 확인의 시간 복잡도는 O(1)이다. 제일 상단이 아닌 나머지 원소들의 확인 및 변경이 원칙적으로 불가능하다. 스택은 원소의 추가/제거, 그리고 제일 상단의 원소 확인 기능만 제공한다. 그래서 제일 상단이 아닌 나머지 원소들의 확인/변경은 스택에서 제공하는 기능이 아니다...

정의와 성질 연결 리스트는 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다. 원소는 배열의 원소들처럼 연속하게 저장되는 것이 보장되지 않고, 흩어져 있다. 연결 리스트의 성질 K번째 원소를 확인/변경하기 위해 O(K)가 필요하다. 임의의 위치에 원소를 추가 / 임의 위치의 원소 제거는 O(1)이다. 원소들이 메모리 상에 연속해 있지 않아 Cache hit rate가 낮지만, 할당이 쉽다. 연결 리스트의 종류 단일 연결 리스트(Singly Linked List) - 각 원소가 자신의 다음 원소의 주소를 가지고 있는 연결리스트이다. 이중 연결 리스트(Doubly Linked List) - 각 원소가 자신의 이전 원소와 다음 원소의 주소를 가지고 있는 연결 리스트이다...

정의와 성질 배열은 메모리 상에 원소를 연속하게 배치한 자료구조이다. 배열의 성질 O(1)에 K번째 원소를 확인/변경 가능하다. 추가적으로 소모되는 메모리의 양(overhead)가 거의 없다. 메모리 상에 데이터들이 연속으로 배치되어 있어 Cache hit rate가 높다. 메모리 상에 연속된 구간을 잡아야 해서 할당에 다소 제약이 있다. 사용 팁 memset 함수는 실수할 여지가 많다. for문은 투박하기는 하지만 실수할 여지가 없기 때문에 무난하고 좋다. algorithm 헤더의 fill 함수는 실수할 여지도 별로 없고 코드도 짧아 좋다. STL vector vector는 배열과 거의 동일한 기능을 수행하는 자료구조이다. 배열과 마찬가지로 원소가 메모리에 연속하게 저장되어 있기 때문에 O(1)에 인덱..