1. 알고리즘 설명 Flood Fill - 외부 윤곽선을 따라서 구분되는 영역의 색을 한꺼번에 바꾸는 것 구현 방법 - BFS BFS - 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 2. 예시 우선 BFS 알고리즘에서는 좌표를 담을 큐가 필요하다. BFS 알고리즘이 시작되면 우선 (0, 0)에 방문했다는 표시를 남기고 해당 칸을 큐에 넣는다. 이 초기 세팅이 끝난 후에는 큐가 빌 때까지 계속 큐의 front를 빼고 해당 좌표의 상하좌우를 살펴보면서 큐에 넣어주는 작업을 반복하면 된다. 큐가 빈 순간 과정은 종료되고 (0, 0)과 상하좌우로 이어진 모든 같은 영역의 칸을 잘 방문했음을 알 수 있다. 1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 2. 큐에서 원소를 꺼내어 그..

1. 수식의 괄호 쌍이란? 수식의 괄호 쌍 - 말 그대로 수식의 괄호 쌍을 의미하며 주어진 괄호 문자열이 올바른지 판단하는 문제이다. 2. 문제 해결을 위한 관찰 괄호 문자열이 올바른지 아닌지 판단하는 방법 중 가장 보편적인 방법은 바로 안쪽부터 짝맞추기를 해서 지워나가는 방법이다. 다 짝이 맞으면 올바른 괄호 쌍인거고 그렇지 않으면 올바르지 않은 괄호 쌍입니다. +) ) 의 갯수가 ( 의 갯수를 넘지 않으면 된다. 그런데 괄호가 여러 종류일 때에는 여는 괄호의 갯수와 닫는 괄호의 갯수 만으로는 해결이 되지 않는다. 예를 들어 ({}), ({)}라는 두 괄호 문자열을 생각해보면 첫 번째는 올바르고 두 번째는 올바르지 않다. 그런데 둘 다 ) 의 갯수가 ( 을 넘은 적도 없고, } 의 갯수가 { 을 넘은 ..

1. 정의와 성질 덱 - 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조 덱은 Restricted Structure의 끝판왕과 같은 느낌의 자료구조인데, 양쪽 끝에서 삽입과 삭제가 전부 가능하다. 자료구조의 덱은 deque고 Double Ended Queue라는 뜻을 가진다. 덱은 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조로 스택과 큐를 덱의 특수한 경우이다. 덱의 성질 1. 원소의 추가 - O(1) 2. 원소의 제거 - O(1) 3. 제일 앞/뒤의 원소 확인 - O(1) 4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능. 그리고 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능한데 독특하게도 STL deque에서는 인덱스로 원소에 접근할 수 있다. STL st..

1. 정의와 성질 큐 - 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조 스택에서는 먼저 들어간 원소가 나중에 나왔는데 큐에서는 먼저 들어간 원소가 먼저 나오게 된다. 스택은 FILO(First In Last Out), 큐는 FIFO(First in First Out)이다. 큐의 성질 1. 원소의 추가 - O(1) 2. 원소의 제거 - O(1) 3. 제일 앞/뒤의 원소 확인 - O(1) 4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능. 스택에서는 보통 원소가 추가되고 제거되는 곳을 top이라고 부르고, 원소가 위 아래로 배치된 것으로 생각을 많이 하는데 큐에서는 추가되는 곳을 rear, 즉 뒤쪽이라고 하고 제거되는 쪽을 front, 즉 앞쪽이라고 한다. 스택과 ..

1. 정의와 성질 스택 - 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조 먼저 들어간 원소가 제일 나중에 나오는 FILO(First In Last Out) 자료구조이다. +) 참고로 큐나 덱도 스택처럼 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있어 스택, 큐, 덱을 묶어서 Restricted Structure라고 부르기도 한다. 스택의 성질 1. 원소의 추가 - O(1) 2. 원소의 제거 - O(1) 3. 제일 상단의 원소 확인 - O(1) 4. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능. 원칙적으로 불가능하다는 뜻을 잘 이해할 필요가 있는데, 원래 스택이라는 자료구조는 원소의 추가/제거/제일 상단의 원소 확인이라는 기능만 제공하는 자료구조이다. 제일 상단이 아닌 나..

1. 정의와 성질 연결 리스트 - 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조 연결 리스트의 성질 1. k번째 원소를 찾기 위해 O(k)의 시간이 필요 2. 임의의 위치에 원소 추가/제거 O(1) 3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움 연결 리스트의 종류 1. 단일 연결 리스트(Singly Linked List) 2. 이중 연결 리스트(Doubly Linked List) 3. 원형 연결 리스트(Circular Linked List) 배열 vs 연결 리스트 배열 연결 리스트 k번째 원소의 접근 O(1) O(k) 임의 위치에 원소 추가/제거 O(N) O(1) 메모리 상의 배치 연속 불연속 추가적으로 필요한 공간..