전체 글

BFS(Breadth First Search)다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘-> 너비 우선으로 방문?? 그래프에서 모든 노드를 방문하는 알고리즘그래프: 정점과 간선으로 이뤄진 자료구조예시시작하는 칸을 큐에 넣고 방문했다는 표시를 남김큐에서 원소 꺼내 그 칸에 상하좌우로 인접한 칸에 대해 3번 진행해당 칸 이전에 방문했다면 아무것도 하지 않고, 처음 방문했다면 방문했다는 표시 남기고 해당 칸을 큐에 삽입큐 빌 때까지 2번 반복=> 모든 칸이 큐에 1번씩 들어감-> 시간복잡도는 칸이 N개일 때 O(N)ex. 행이 R개, 열이 C개 -> O(RC)(0, 0)과 상하좌우로 이어진 모든 파란칸 확인좌표를 담을 큐 필요(0, 0)에 방문했다는 표시 + 해당 칸 -> 큐에 넣음큐..

시간 복잡도배열로 구현 -> 최대 N번 중간에 있는 원소의 삭제 발생 => O(N^2)연결리스트 -> O(N)=> 스택으로 훨씬 간단하게 구현 문자열을 앞에서부터 읽어나갈 때, 닫는 괄호가 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라고 생각해도 된다 문제 해결 방법여는 괄호 나옴 -> 스택에 추가닫는 괄호 나옴스택이 비어 있음 -> 올바르지 X 괄호 쌍스택의 top이 짝과 맞지 X 괄호 -> 올바르지 X 괄호 쌍스택의 top이 짝이 맞는 괄호 -> pop모든 과정을 끝낸 후 스택에 괄호 남아있음 -> 올바르지 X 괄호 쌍 / 남아있지 X -> 올바른 괄호 쌍

덱Restricted Structure 양쪽 끝에서 삽입, 삭제 전부 가능한 자료구조성질원소 추가 / 제거 O(1)제일 앞 / 뒤의 원소 확인 O(1)제일 앞 / 뒤가 아닌 나머지 원소들의 확인 / 변경이 원칙적으로 불가능STL deque에서 인덱스로 원소에 접근 가능구현배열(더 쉬움)연결리스트const int MX = 1000005;int dat[2*MX+1];int head = MX, tail = MX;원소를 담을 큰 배열 1개, 앞쪽, 뒤쪽을 가리킬 변수 2개 (= 큐)head: 가장 앞에 있는 원소의 인덱스tail: 가장 뒤에 있는 원소의 인덱스 + 1-> 초기값 0이 아닌 MX큐: 앞(제거), 뒤(삽입) -> 배열 내에서 실제 큐에 들어간 원소들이 차지하는 공간이 점점 R로 이동하면서 확장덱: ..

큐한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조ex. 공항에서 입국소속 하는 줄FIFO(First in First Out)먼저 들어간 원소가 먼저 나옴성질원소의 추가 / 제거 O(1)스택 - top: 원소가 추가되고 제거되는 곳/ 원소가 위 아래로 배치된 것큐 - rear: 추가되는 곳(뒤쪽), front: 제거되는 곳(앞쪽)제일 앞 / 뒤의 원소 확인 O(1)제일 앞 / 뒤가 아닌 나머지 원소들의 확인 / 변경 원칙적으로 불가능구현배열(더 쉬움)연결 리스트const int MX = 1000005;int dat[MX];int head = 0, tail = 0;head와 tail은 0번지에서 시작해 계속 증가dat 배열에서 dat[head] ~ dat[tail-1]번지 = 큐의 원소들..

스택한쪽 끝에만 원소를 넣거나 뺄 수 있는 자료구조Restricted Structure: 스택, 큐, 덱ex. 프링글스 통, 엘리베이터FILO(First In Last Out) 자료구조먼저 들어간 원소가 나중에 나오는 구조성질원소의 추가 / 제거 O(1)제일 상단의 원소 확인 O(1)제일 상단이 아닌 나머지 원소들의 확인 / 변경이 원칙적으로 불가능구현 시 배열 기반으로 구현구현배열(더 쉬움)연결리스트const int MX = 1000005;int dat[MX];int pos = 0;원소를 담은 큰 배열 1 개, 인덱스 저장할 변수 1개{13, 21, 30}이 담겨있는 스택 나타내기 -> dat[0], dat[1], dat[2]에 각각 13, 21, 30, pos = 3=> 스택의 값들은 dat의 0번지..

연결리스트원소들을 저장할 때 그 다음 원소가 있는 위치를 포함하는 방식으로 저장하는 자료구조ex. 메모장성질k번째 원소를 확인 / 변경 -> O(k) 필요첫 번째부터 순차적으로 방문해야 함 (첫 번째 원소의 주소만 알고 있음)N개의 원소 -> 평균적으로 2/N 시간 => O(N)임의의 위치에 원소 추가 / 임의 위치의 원소 제거 -> O(1)다음 원소의 주소만 변경해주면 됨 (추가하고 싶은 위치의 주소를 알고 있는 경우)원소들이 메모리 상에 연속 X -> Cache hit rate ↓ But, 할당 다소 쉬움배열 vs. 연결리스트-> 선형 자료구조vs. 비선형 자료구조: 트리, 그래프, 해쉬 종류단일 연결 리스트(Singly Linked List)각 원소가 다음 원소의 주소를 들고 있는 연결 리스트이중 ..