'👩‍💻 프로그래밍' 카테고리의 글 목록 (4 Page)

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의 모든..

[C++] 이름공간(namespace) | 범위지정 연산자

2024.04.14· 👩‍💻 프로그래밍/🎠 C++

🟩 이름공간의 원리 이름공간 : 프로젝트의 진행에 있어서 발생할 수 있는 이름의 충돌을 막을 목적으로 존재하는 것 존재하는 이름공간이 다르면 동일한 이름의 함수 및 변수를 선언하는 것이 가능하다. :: 범위 지정 연산자 namespace BestComImpl{ void SimpleFunc(void){ cout

[C++] inline 함수 cf. 매크로 함수

2024.04.14· 👩‍💻 프로그래밍/🎠 C++

🌟 함수의 인라인화 함수의 몸체가 함수의 호출문을 대신한다. 🌟 매크로 함수 #define SQUARE(x) ((x)*(x)) int main(void){ cout

[C++] 함수 오버로딩 | 매개변수의 디폴트 값

2024.04.14· 👩‍💻 프로그래밍/🎠 C++

int MyFunc(int num){ num++; return num; } int MyFunc(int a, int b){ return a+b; } int main(void){ MyFunc(20); // MyFunc(int num) 함수 호출 MyFunc(30, 40); // MyFunc(int a, int b) 함수 호출 return 0; } C++은 함수 호출 시 '함수의 이름'과 '전달되는 인자의 정보'를 동시에 참조하여 호출할 함수를 결정한다. 따라서 매개변수의 선언이 다르다면 동일한 이름의 함수도 정의 가능하다. 그리고 이러한 형태의 함수 정의를 가리켜 '함수 오버로딩'이라 한다. 🌟 함수 오버로딩 조건 (아래 3개 조건 모두 만족) 1. 반환형이 같을 것 2. 함수의 이름이 같을 것 3. 매개변..

[C++] printf와 scanf를 대신하는 입출력 방식

2024.04.14· 👩‍💻 프로그래밍/🎠 C++

🟩 헤더파일 선언 #include 🟩 출력의 기본 구성 std::cout > val2; 입력할 땐 스페이스바/엔터/탭과 같은 공백을 통해서 입력하면 된다. 🌟 문자열 입출력도 크게 다르지 않다. char name[100]; std::cin >> name; 🟩 변수의 선언 위치 함수의 중간 부분에서도 변수의 선언이 가능하다(변수의 선언 위치에 제한을 두지 않는다). 출력에서와 마찬가지로 입력에서도 별도의 서식 지정이 불필요

2-3-4 트리

2024.04.14· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 다음 성질을 만족하는 균형 탐색 트리 2-노드 👉 1개의 키와 2개의 자식을 갖는 노드 3-노드 👉 2개의 키와 3개의 자식을 갖는 노드 4-노드 👉 3개의 키와 4개의 자식을 갖는 노드 각 노드의 한 키와 왼쪽 서브트리에 있는 모든 키 값은 그 키 값보다 작다. 각 노드의 한 키와 오른쪽 서브트리에 있는 모든 키 값은 그 키 값보다 크다. 🌟 노드의 구조 🟩 탐색 🟩 삽입 탐색 과정에서 4-노드를 만나면 항상 노드 분할을 우선 수행 🌟 노드 분할 노드 분할의 유형 부모가 2-노드인 4-노드인 경우 👉 중간 키를 부모로 보내어 3-노드에 연결된 2개의 2-노드로 변환 부모가 3-노드인 4-노드인 경우 👉 4-노드에 연결된 2개의 2-노드로 변환 루트가 4-노드인 경우 👉 3개의 2-노드로 변환 & 루..

이진 탐색 트리(Binary Search Tree)

2024.04.14· 👩‍💻 프로그래밍/🎐 알고리즘

🌟 이진 트리 한 노드의 왼쪽 서브트리에 있는 모든 키 값은 그 노드의 키 값보다 작다. 한 노드의 오른쪽 서브트리에 있는 모든 키 값은 그 노드의 키 값보다 크다. 🟩 루트 노드에서부터 시작해서 값의 크기 관계에 따라 트리의 경로를 따라 내려가면서 탐색 진행 🟩 삽입 연산 삽입할 원소를 탐색한 후, 탐색이 실패하면 해당 위치에 자식 노드로서 새 노드를 추가 🟩 삭제 연산 삭제되는 노드의 자식 노드의 개수에 따라 구분해서 처리 1. 자식 노드가 없는 경우 👉 남는 노드가 없어 위치 조절 불필요 2. 자식 노드가 1개인 경우 👉 자식 노드를 삭제되는 노드의 위치로 올리면서 서브트리 전체도 따로 올림 3. 자식 노드가 2개인 경우 👉 삭제할 노드 왼쪽 서브 트리의 가장 큰 자손을 해당 노드의 자리에 올린다 ..

이진 탐색(Binary Search)

2024.04.14· 👩‍💻 프로그래밍/🎐 알고리즘

🟩 정렬된 리스트 형태로 주어진 원소들을 절반씩 줄여 가면서 원하는 값을 가진 원소를 찾는 방법 분할정복 방법이 적용됨 주어진 배열이 정렬되어 있지 않으면 정렬 수행 🟩 탐색 방법 배열의 가운데 원소 A[mid]와 탐색키 key를 비교 🌟 중간 값을 구하는 방식 1. mid : low + (high-low) / 2 2. mid : (low + high) / 2 👉 low + high 값이 (2^31-1)의 범위보다 크다면 음수값으로 오버플로우 발생 가능 1. A[mid] = key 👉 탐색 성공 (인덱스 mid 반환 후 종료) 2. A[mid] key 👉 이진 탐색(원래 크기의 1/2인 왼쪽 부분배열) 순환 ..

순차 탐색(Sequential Search)

2024.04.14· 👩‍💻 프로그래밍/🎐 알고리즘

🌟 다양한 탐색 방법 리스트 형태 👉 순차 탐색, 이진 탐색 트리 형태 👉 이진 탐색 트리, 2-3-4 트리, 레드-블랙 트리, B-트리 해시 테이블 👉 해시 함수, 충돌 해결 방법 🟩 리스트 형태로 주어진 원소들을 처음부터 하나씩 차례로("순차") 비교하면서 원하는 값을 갖는 원소를 찾는 방법 // A[] : 입력배열 // n : 입력 크기 (탐색할 데이터의 갯수) // x : 탐색 키 SequentialSearch(A[ ], n, x){ i = 0; while (i < n && A[i] != x) i = i + 1; return (i); } // x가 배열 내에 존재하면 인덱스, 아니면 n을 반환 🌟 삽입 및 삭제 🟩 시간 복잡도 탐색, 삭제 : O(n) 삽입 : O(1) 🟩 정렬되지 않고 크기가 작..

너비 우선 탐색(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는 꺼내 출력하고, 그 ..

티스토리툴바