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

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

🟩 n개의 행렬을 연쇄적으로 곱할 때 최소의 기본 곱셈 횟수를 갖는 행렬의 곱셈 순서를 구하는 문제i x j 행렬과 j x k 행렬을 곱하기 위해서는 i x j x k 번 만큼의 곱셈이 필요하다.연쇄적으로 행렬을 곱할 때 어떤 행렬을 먼저 수행하느냐에 따라서 필요한 총 곱셈의 횟수가 달라진다.🟩 연쇄행렬행렬의 곱셈은 아래와 같이 결합법칙이 성립한다.A x (B x C) = (A x B) x C그러나, 행렬을 곱하는 순서에 따라 곱하는 횟수가 달라진다. 👉 즉, 연쇄행렬 최소곱셈 알고리즘은 행렬곱셈에서 곱하는 순서에 따라 곱셉의 횟수가 달라지는데 이러한 법칙을 이용하여 최소로 곱하는 횟수를 구하는 것이다. 연쇄행렬 최소곱셈 알고리즘 재귀관계식 ✨ 예제로 이해하면 쉽게 이해 가능!EX) A(20x1),..

[C++] 가상의 원리와 다중상속

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

EX) 몬스터 구조체에서 Attack 함수가 있다고 가정하면, 몬스터 A도 Attack 함수를 사용 가능하고, 몬스터 B도 같은 Attack 함수를 사용가능하다.👉 다수의 객체가 멤버함수를 공유하는 형태다만, 함수 호출시 객체의 정보가 전달이 되고, 이를 기반으로 함수가 실행되기 때문에 객체 안에 멤버함수가 존재하는 형태이다.객체가 생성되면, 멤버변수는 객체 내부에 존재하지만, 멤버함수는 메모리의 한 공간에 별도로 위치한다.이 함수가 정의된 클래스의 모든 객체가 이를 공유하는 형태를 가진다. 🟩 가상함수 테이블실제 호출되어야 할 함수의 위치정보를 담고 있는 테이블한 개 이상의 가상함수(virtual 함수)를 포함하는 클래스에 대해서는 컴파일러가 '가상함수 테이블'이라는 것을 만든다.매 함수호출시마다 ..

[C++] 상속과 다형성 | 가상함수(virtual function) | 참조자

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

🌟객체의 주소값을 저장하는 객체 포인터 변수C++에서 AAA형 포인터 변수는 AAA 객체 또는 AAA를 직접 혹은 간접적으로 상속하는 모든 객체를 가리킬 수 있다.👉 객체의 주소값을 저장할 수 있다. EX) Person ⊃ Student ⊃ PartTimeStudentPerson * ptr = new Student();Person * ptr = new PartTimeStudent();Student * ptr = new PartTimeStudent(); IS-A 관계로 봐보자!"학생은 사람의 일종이다""근로학생은 학생의 일종이다""근로학생은 사람의 일종이다" 👉 하위 클래스 객체를 상위 클래스 객체로 바라볼 수 있는 증거"학생은 사람이다""근로학생은 학생이다""근로학생은 사람이다" EX2) 모든 클래..

[C++] 상속

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

🟩 기존에 정의해 놓은 클래스의 재활용을 목적으로 만들어진 문법적 요소 좋은 코드는 요구사항의 변경 및 기능의 추가에 따른 변경이 최소화되어야 한다. 그리고 이를 위한 해결책으로 상속이 사용된다. class Person { private: int age; char name[50]; public: Person(int myAge, char * myName) : age(myAge){ } void WhatYourName() const { } void HowOldAreYou() const { } } class Student : public Person { // Person 클래스를 public 상속함 private: char major[50]; public: Student(char *myName, int myAg..

[C++] 복사 생성자 | 깊은 복사와 얕은 복사

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

// C 스타일 초기화 int num = 20; int &ref = num; // C++ 스타일 초기화 int num(20); int &ref(num); 위 문장들은 모두 동일하다. class SoSimple{ private: int num1; int num2; public: SoSimple(int n1, int n2) : num1(n1), num2(n2){} void ShowSimpleData(){ cout

포드-풀커슨 알고리즘(최대 유량 문제)

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

🌟 최대 유량 문제(=네트워크 플로우) 특정한 지점에서 다른 지점으로, 얼마나 많은 유량을 동시에 보낼 수 있는지 계산하는 문제 ✏️ 용어 정리 용량 : c(u,v) 정점 u에서 v로 전송할 수 있는 최대 용량 유량 : f(u,v) 정점 u에서 v로 실제 흐르고 있는 유량 잔여 용량 : r(u,v) = c(u,v) - f(u,v) 간선의 용량과 실제로 흐르는 유량의 차이 소스 s 모든 유량이 시작되는 정점 싱크 t 모든 유량이 도착하는 정점 증가 경로 소스에서 싱크로 유량을 보낼 수 있는 경로 ✏️ 기본 속성 용량 제한 속성 f(u,v)

플로이드 알고리즘(최단 경로)

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

🟩 모든 정점쌍에 대해서 둘 사이의 최단거리를 구할 수 있다. cf. 다익스트라 : 한 시작점에서 다른 정점까지의 최단 거리 단, 플로이드 알고리즘은 음수 가중치가 없는 무조건 양수의 그래프에서 동작 a 👉 b로 이동할 때, 경유점은 c 플로이드 알고리즘은 두 정점 사이의 어떤 경유점이 존재한다면 경유점을 거쳐가는 것을 확인하면서 더 짧은 것을 선택 🟩 구현 1. 위의 그래프를 우선 배열로 구현해야 한다. 초기값은 아주 큰 값으로 설정해야 한다. 그리고 자기 자신까지의 비용은 0으로 설정한다. 2. 시작점을 i, 끝점을 j, 경유점을 k라 할 때, 구하는 식은 다음과 같다. adj[i][j] = MIN(adj[i][j], adj[i][k] + adj[k][j]) 항상 작은 값만을 갖게 되므로 직접적으로 ..

벨만-포드 알고리즘(최단 경로)

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

🟩 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘 간선의 가중치가 음수일 때도 최단 거리를 구할 수 있다. 🌟 다익스트라 vs 벨만-포드 1번 노드에서 3번 노드로 가는 최단 거리를 구한다고 할 때, 경로1. 1번 👉 3번 (비용 : 10) 👉 다익스트라 알고리즘 경로2. 1번 👉 2번 👉 3번 (비용 : 5) 👉 벨만-포드 알고리즘 ✏️ 다익스트라 알고리즘 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하여 한 단계씩 최단 거리를 구해나간다. 음수 간선이 없다면 최적의 해를 구할 수 있다. 시간 복잡도가 빠르다 (O ElogV) ✏️ 벨만-포드 알고리즘 (정점-1)번의 매 단계마다 모든 간선을 전부 확인하면서 모든 노드간의 최단 거리를 구해나간다. cf. 다익스트라와의 차..

다익스트라 알고리즘(최단 경로)

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

🟩음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단 거리를 구하는 알고리즘 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만 한 꼭짓점을 "소스" 꼭짓점으로 고정하고, 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것으로도 사용 🟩 그리디이자 동적계획법 그리디 : 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택 다이나믹 프로그래밍 : 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신 👉 가능한 적은 비용으로 가장 빠르게 해답을 도달하는 경로를 찾아내는 대부분의 문제에 응용된다. 🟩 예제 A노드에서 출발하여 F노드로 가는 최단경로를 구하는 문제 S = 방문한 노드들의 집합 d[N] = A -> N까지 계산된 최단 거..

프림 알고리즘 (최소 신장 트리)

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

🟩 시작 정점에서 정점을 추가해가며 단계적으로 트리를 확장하는 기법 즉, 탐색 정점에 대해 연결된 인접 정점들 중 비용이 가장 적은 간선으로 연결된 정점을 선택 🟩 동작 1. 시작 단계는 시작 노드만이 최소 신장 트리 집합에 속한다. 2. 트리 집합에 속한 정점들과 인접한 정점들 중 가장 낮은 가중치의 간선과 연결된 정점에 대해 간선과 정점을 최소 신장 트리 집합에 넣는다 (사이클을 막기 위해 연결된 정점이 이미 트리에 속한다면 그 다음 순서를 넣는다) 3. 2번 과정을 MST 집합의 원소 개수가 그래프의 정점의 개수가 될 때까지 반복한다. 시작 정점 A A와 인접한 노드 B, C 중 C가 가장 가중치가 낮은 간선으로 연결되어 있으니, C를 집합에 넣고 비용에 AC 가중치를 더한다. AC와 인접한 노드들..

크루스칼 알고리즘 (최소 신장 트리)

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

🟩 최소 신장 트리 신장 트리 중 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘 👉 크루스칼 알고리즘 : 가장 적은 비용으로 모든 노드 연결 가능 🌟 신장 트리 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 🌟 최소 신장 트리 신장 트리 중에서도 최소한의 비용으로 만들 수 있는 신장 트리 왼쪽 그래프에서 최소 신장 트리를 찾으면 25를 제외한 2개의 간선 (23+13)으로 이루어진 신장트리 즉, 신장 트리의 조건을 만족하면서 최소 비용으로 만들 수 있는 신장 트리 🟩 크루스칼 알고리즘 동작과정 1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 2. 간선을 하나씩 확인하면서 현재의 간선이 사이클을 발생시키는지 확인 👉 사이클 발생 여부에 따라, 최소 신장..

[C++] 클래스와 배열, this 포인터

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

🟩 객체 배열 객체로 이루어진 배열 따라서, 배열 생성시 객체가 함께 생성된다. Person arr[3]; Person * per = new Person[3]; 🟩 객체 포인터 배열 객체를 저장할 수 있는 포인터 변수로 이뤄진 배열 따라서 별도의 객체 생성 과정을 거쳐야 한다. Person * arr[3]; arr[0] = new Person(name, age); arr[1] = new Person(name, age); arr[2] = new Person(name, age); 객체 관련 배열을 선언할 때는 객체 배열을 선언할지, 객체 포인터 배열을 선언할지를 먼저 결정해야 한다. 🟩 this 포인터 그 값이 결정되어 있지 않은 포인터이다. 왜냐하면 this 포인터는 this가 사용된 객체 자신의 주소값을..

티스토리툴바