'👩‍💻 프로그래밍/✨ 자료구조' 카테고리의 글 목록

2024.04.18· 👩‍💻 프로그래밍/✨ 자료구조

그래프 관련 문제를 풀 때는, 문제 상황을 그래프로 모델링한 후 푸는 것이 보편적이다. 이 때, 모델링한 그래프의 연결관계를 나타내는 두 가지 방식이 있다. 👉 1. 인접 행렬 2. 인접 리스트 🟩 인접 행렬 그래프의 연결 관계를 이차원 배열로 나타내는 방식 인접 행렬을 adj[][]라고 한다면, adj[i][j]에 대해서 다음과 같이 정의 가능 adj[i][j] : 노드 i에서 노드 j로 가는 간선이 있다면 1, 아니면 0 cf. 만약 간선에 가중치가 있는 그래프라면 1 대신에 가중치의 값을 직접 넣어주는 방식으로 구현 가능하다. 🌟 예시 유향 그래프가 아닌 무향 그래프에서는, 노드 i 👉 노드 j 라는 말은, 노드 j 👉 노드 i라는 의미이다. 따라서, 인접 행렬이 대각성분(i=j인 원소들)을 기준으..

셋(Set)

2024.04.16· 👩‍💻 프로그래밍/✨ 자료구조

🟩 key만 있는 map 혹은 정렬된 집합 set은 map과 구조가 매우 유사하다. 단, key만 있고 value가 없는 map이라고 볼 수 있다. 따라서, 사용법도 map과 크게 다르지 않다. 정렬된 집합이라고 정의한 이유는 set이 갖는 값들이 중복을 허락하지 않고 정렬되어 있기 때문이다. 🟩 특정 값에 대해 검색을 빠르게 하고 싶은 경우 🟩 #include s.size() s의 노드 개수를 리턴 s.empty() s의 사이즈가 0인지 아닌지를 확인 s.begin() s의 첫 번째 원소를 가리키는 iterator 리턴 s.end() s의 마지막 원소를 가리키는 iterator 리턴 s.insert(k) s에 값이 k인 노드 추가 s.erase(k) s에 값이 k인 노드 삭제 s.find(k) s에서 ..

맵(Map)

2024.04.16· 👩‍💻 프로그래밍/✨ 자료구조

🟩 인덱스로 int가 아닌 다른 자료형을 사용할 수 있는 배열 (편의상) map의 내부적인 구조는 각 노드가 key와 value의 쌍으로 이루어진 '트리'이다. 특히 검색, 삽입, 삭제 등의 속도를 빠르게 하기 위해 균형 이진 트리 중의 하나인 '레드-블랙 트리'로 구현되어 있다. 검색 속도가 특히 빠른데 이는 key를 기준으로 정렬된 상태이기 때문이다. 🟩 연관있는 두 값을 함께 묶어서 관리하되, 검색을 빠르게 하고 싶은 경우 🟩 #include map은 중복 불가한 key와 value 쌍으로 이루어진 노드의 트리라고 할 수 있다. 같은 key 값을 갖는 노드를 추가하면 어떻게 될까? 해당 key 값을 갖고 있던 원래 노드의 value 값에 덮어 씌워지게 된다. map의 요소에 접근할 때, 반복자(it..

페어(Pair)

2024.04.15· 👩‍💻 프로그래밍/✨ 자료구조

🟩 #include 🟩 이름이 first, second인 두 개의 변수를 저장할 수 있는 struct first가 1이고, second가 2인 pair을 만들기 위해, pair를 선언한 후, 각 멤버 변수(frist, second)를 초기화해주는 것이 아니라, make_pair를 통해 바로 만들 수 있다. 🟩 용도 이차원 배열의 인덱스 이차원 좌표평면에서의 좌표 정점 번호와 해당 정점 번호까지의 최단거리를 묶어서 저장해야하는 경우 // pair 선언 pair p; pair p; // pair 생성 int a = 1, b = 2; pair p = make_pair(a, b); pair p = make_pair(1, 2); // pair의 멤버 변수에 접근 int valA = p.first; int valB..

벡터(Vector)

2024.04.15· 👩‍💻 프로그래밍/✨ 자료구조

🟩 #include 🟩 사이즈가 유동적인 배열 용도 : 배열을 사용하는 모든 경우 동적 배열을 구현한 것으로, 여러 데이터를 연속적인 메모리 공간에 저장한다. v.size() v의 사이즈 (물리적인 저장 용량이 아닌 원소의 개수)를 리턴 v.resize(new_size) v를 new_size로 사이즈를 바꿔줌 v.empty() v의 사이즈가 0인지 아닌지를 확인 v.begin() v의 0번째 원소를 가리키는 iterator 리턴 v.end() v의 마지막 원소를 가리키는 iterator 리턴 v.front() v의 0번째 원소를 리턴 v.back() v의 마지막 원소를 리턴 v.push_back(val) v의 끝에 val를 추가 v.pop_back() v의 마지막 원소를 삭제 v.clear() v의 모든..

너비 우선 탐색(BFS)

2024.04.14· 👩‍💻 프로그래밍/✨ 자료구조

🟩 루트 노드에서 시작하여 인접한 노드에서 시작해서 인접한 노드를 먼저 탐색 지금 위치에서 갈 수 있는 것들을 모두 큐(queue)에 넣는 방식 큐에 넣을 시점에 해당 노드를 방문했다고 체크해야 한다. cf. DFS는 일단 들어가서 체크 큐와 while 반복문 활용 🟩 방법 그래프를 순차적으로 방문할 수 있어야 하고, 방문한 노드들은 다시 탐색할 일이 없도록 방문 처리되어야 한다. 1) 시작 정점 A를 큐에 넣고 방문 처리한다. A 2) 큐에서 A를 꺼내고, 인접 노드 B, C를 큐에 삽입 후 방문 처리한다. B C 3) 큐에서 B를 꺼내고, 인접 노드 D, E를 큐에 삽입 후 방문 처리한다. C D E 4) 큐에서 C를 꺼내고, 인접 노드 F, G를 큐에 삽입 후 방문 처리한다. D E F G 5) 위..

깊이 우선 탐색(DFS)

2024.04.14· 👩‍💻 프로그래밍/✨ 자료구조

🟩 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 stack을 이용하여 갈 수 있는 만큼 최대한 깊이 가는 것이고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아간다는 것 주로 반복문(Stack) / 재귀문(순환 알고리즘)을 통하여 구현된다. 🟩 방법 그래프를 순차적으로 방문할 수 있어야 하고, 방문한 노드들은 다시 탐색할 일이 없도록 방문 처리되어야 한다. 1. 현재 노드를 방문한 것으로 표시 2. 방문한 표시가 되어 있지 않은 각각의 인접한 정점을 탐색 3. 더 이상 방문하지 않은 정점이 없으면 이전 정점을 역추적 4. 모든 정점을 방문할 때까지 프로세스 반복 🌟 반복 구현 (Stack 활용) 1) 시작 정점 A를 스택에 넣고 방문 처리한다. A 2) 스택의 최상단 노드 A는 꺼내 출력하고, 그 ..

트리(Tree)

2024.04.13· 👩‍💻 프로그래밍/✨ 자료구조

🟩 자연의 나무처럼 가지가 분기하여 뻗어 나가는 구조 트리를 구성하는 원을 '노드(마디)' 트리 맨 위에 있는 노드는 '루트(뿌리)' 위에 있는지 아래에 있는지에 따라 부모 노드와 자식 노드로 구분, 같은 부모를 가지면 형제 노드 부모와 자식 노드 형태로 묶인 트리의 일부분을 서브 트리 트리의 맨 아래에 있고, 별도의 자식 노드가 없으면 리프(잎) 노드 노드의 레벨 : 루트로부터 그 노드까지 이어진 선(경로)의 길 노드의 길이 : 어떤 노드에서 다른 노드로 이동할 때, 거치는 노드의 개수 노드의 경로 : 어떤 노드에서 다른 노드로 이동할 때, 거치는 노드의 순서 노드의 크기 : 자기 자신과 자식 노드를 포함한 노드의 개수 노드의 차수 : 노드별 자식 노드의 개수 트리의 높이 : 트리 노드로부터 리프 노드..

그래프(Graph) | 위상 정렬 | 연결 성분

2024.04.13· 👩‍💻 프로그래밍/✨ 자료구조

🟩 연결되어 있는 원소 간의 관계를 표현한 자료구조 몇 개의 정점(Vertext)이 간선(Edge)으로 연결된 것 그래프 G = (V,E) 🟩 그래프 탐색 특정 정점에서 출발해 간선을 통해 이동해가며 대상 정점을 찾는 것 탐색 순서에 따라 깊이 우선 탐색, 너비 우선 탐색 🟩 그래프 용어 인접 : 두 정점이 연결되어 있을 때 cf. 정점들은 부속되어 있다 한다. 차수 : 정점에 부속되어 있는 간선의 수 경로 : 정점 a에서 b까지 간선으로 연결된 정점을 순서대로 나열한 리스트 단순 경로 : 모두 다른 정점으로 구성된 경로 👉 진입 차수, 진출 차 경로 길이 : 경로를 구성하는 간선의 수 사이클 : 단순 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로 🟩 구현 방법 인접 행렬, 인접 리스트 🌟 무..

힙(Heap) cf.이진탐색트리

2024.04.12· 👩‍💻 프로그래밍/✨ 자료구조

🟩 힙 = 퇴적물 바닷속 퇴적물처럼 아래에 큰 바위, 중간 정도의 돌, 그 위에 작은 모래 순으로 쌓여있다. 🟩 그래프의 트리 구조 중 하나(완전 이진트리) 각 노드의 키 값이 그 자식의 키 값보다 작지 않거나(최대힙), 크지 않은(최소힙) 완전 이진트리 완전 이진트리는 중복을 허용하지 않지만 힙은 허용한다. 🟩 정렬을 효율적으로 수행하는 트리 '우선순위 큐'를 구현할 때 사용 최댓값과 최솟값을 빠르게 찾기 위해 고안됨 배열을 사용하면 O(n)만큼 시간이 걸리지만, 힙을 사용하면 O(logn)만큼 소요되므로, 배열을 사용할 때보다 빠르게 최솟값, 최댓값을 구할 수 있다. 🟩 힙에서의 부모-자식 관계 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2 ..

해시 테이블(Hash Table)

2024.04.12· 👩‍💻 프로그래밍/✨ 자료구조

해시함수와 함께 데이터 검색을 효율적으로 하기 위해 사용되는 구조 키(key)와 값(value)이 한 쌍을 이루는 데이터를 저장 특정 키값 K를 갖는 데이터를 찾는 문제에서 활용 원하는 데이터를 선형탐색으로 구할 수는 있지만, 데이터 양에 비례해서 계산시간이 늘어난다는 단점이 있다. 배열 탐색에 시간이 걸리므로, 적합하지 않은 구조 👉 해시테이블의 등장 🟩 배열을 만들고 데이터를 추가할 때, '해시 함수' 이용 키 값을 해시 테이블의 주소로 변환하는 함수 계산이 용이해야 하며, 적은 충돌 발생 👉 각 키를 테이블의 각 슬롯에 균등하게 사상시킬 수 있어야 🌟 해시 함수의 종류 1. 제산잔여법 키 값을 해시 함수에 넣어 나오는 해시값을 배열의 갯수로 나누어 나머지를 구한다. 예) 4928 % 5 = 3 구한..

스택(Stack)

2024.04.12· 👩‍💻 프로그래밍/✨ 자료구조

🟩 LIFO (Last In First Out) 🟩 DFS (깊이우선탐색) 후보 중에서 항상 최신의 것을 선택 🟩 헤더 추가 🟩 주요 동작 push 삽입 pop 추출 peek 가장 최상단에 있는 데이터가 무엇인지 알 수 있음 🟩 삽입/삭제가 단방향으로 이루어짐 데이터를 추가할 때, 가장 위에 추가된다. 삭제도 가장 위에서 이루어진다는 단점이 있다. 데이터 접근도 스택의 가장 위에 있는 데이터만 가능하기 때문에, 원하는 데이터가 필요하면 그 때까지 pop해야 한다. 멤버 함수 기능 s.size() s의 사이즈(물리적인 저장 용량이 아닌 원소의 개수)를 리턴 s.empty() s의 사이즈가 0인지 아닌지를 확인 s.top() s에 가장 나중에 들어간 원소를 리턴 s.push(val) s의 뒤에 val를 추가..

티스토리툴바