본문 바로가기

분류 전체보기

 (115)
[C++] 벨만-포드 알고리즘 핵심 요약 한 정점에서 다른 모든 정점으로 가는데 걸리는 최소비용을 구하는데 사용하는 알고리즘 음의 가중치가 있을 때 사용 → 음의 사이클을 찾음 동작 원리 모든 간선들을 탐색하면서, 간선이 잇는 출발정점이 '한번이라도 계산 된 정점' 이라면 해당 간선이 잇는 정점의 거리를 비교해서 업데이트 한다. ⇒ 방향성이 있기 때문! 1번 과정을 반복한다. (N-1번) 음의 사이클을 찾는 방법 N-1번 반복 후, 1번 더 반복한다. → "정상적인 그래프라면, 즉, 음의 사이클이 발생하지 않는 그래프라면, N - 1번을 탐색한 이후에, 또 한번의 탐색을 더 하더라도 절대로! 최소비용이 변하는 정점이 발생하지 않는다"
[C++] 다익스트라(Dijkstra) 핵심 요약최단 경로 탐색 알고리즘.방문한 노드들과 연결된 간선 중 최소 비용인 간선을 선택하는 알고리즘.단, 가중치가 양수일때만 적용할 수 있다. 동작 원리'비용' 이라는 말을 많이 사용하게 될 텐데, 이 값은 1차원 배열 Dist[] 라는 배열에 저장되어 있다고 생각하자. 초기 Dist배열의 모든 값은 무한대(INF)로 초기화 되어 있다.시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주고, 시작 노드를 방문한 노드로 체크한다.방문한 정점들과 연결되어 있는 정점들 중, 비용이 가장 적게 드는 정점을 선택하고, 해당 정점을 방문한 정점으로 체크해준다.2번 과정에 의해서 갱신될 수 있는 정점들의 거리를 갱신시켜준다.3 ~ 4번 과정을 반복한다. 구현1. 비용을 저장할 int형 배열..
[C++] 수학 함수 제곱(pow) 함수 원형 double pow(double base, double n) // base가 되는 숫자의 n 제곱 새로운 수학 함수를 사용할 때마다 차근차근 정리할 예정입니다.
[C++] 유니온 파인드(Union-Find) 핵심 요약 유니온 파인드는 그래프 탐색으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 서로소 집합, 상호 베타적 집합(Disjoint-Set)으로도 불린다. 노드를 합치는 Union연산과 노드의 루트 노드를 찾는 Find연산으로 이루어진다. 트리 구조로 이루어진 자료구조 중 한가지로 생각되기도 한다. 연산 Find - 노드 x가 어느 집합에 포함되어 있는지 찾는 연산 Union - 노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산 예제 코드 #include using namespace std; int parent[9]; //배열에 해당하는 것 int find (int x){ if (parent[x]== x) return x; //배열 인덱스와 값이 같다면 해당 값 리턴 retu..
[C++] BFS(Breadth-First Search) 핵심 요약 너비 우선 탐색 시작 노드에 인접한 노드들부터 차근차근 탐색하는 알고리즘 간선의 비용이 동일한 최단거리 문제에서 활용된다. 구현 방식 1. 큐를 사용한다 큐에 노드를 push하고, 방문 처리한다. 노드를 큐에서 pop하고, 인접 노드를 모두 push한 뒤 방문 처리한다. 2. while문의 조건을 통해 모든 노드를 탐색할 때까지 돌린다. 3. while문 안에 for문을 넣어 인접 노드를 탐색한다. 1. 입력이 배열로 주어질 때 배열에 입력값들을 넣은 뒤, 이동해야 하는 방향(주로 상하좌우)을 탐색한다. 이때, 이동 방향은 dx[4] = {-1, 1, 0, 0} 과 dy[4] = {0, 0, 1, -1}을 이용하여 처리하는 편이다. 이 경우 방문 정보는 bool 형의 2차원 배열로 처리한다. ..
[C++] DFS(Depth-First Search) 핵심 요약 깊이 우선 탐색 루트 노드에서 시작하여 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 기법 특징 주로 재귀로 구현된다. 트리 순회의 경우 모두 DFS이다. 방문 여부(visited) 체크나 깊이 지정을 해야 무한 루프에 빠지지 않는다. 구현 방법 스택 재귀
백트래킹(Back-Tracking) 핵심 요약 해를 찾는 도중 해가 아니어서 막힐경우, 되돌아가서 다시 해를 찾아가는 기법 시간 복잡도를 감소시킬 수 있는 기법 최적화 문제, 결정 문제 등을 풀 때 활용한다. 유망성 판단(promising)이 중요하다! 사용처 DFS 등 대표 문제 백준 9663, N-Queen 문제. https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net
[오브젝트] CHAPTER 2. 객체지향 프로그래밍 핵심 용어 도메인 객체(상태 + 행동) 접근 제어와 접근 수정자 협력 메시지와 메서드 지연 바인딩(동적 바인딩) 초기 바인딩(정적 바인딩) 추상화 상속과 다형성 추상 클래스와 인터페이스 상속과 협력 핵심 요약 - 객체지향 프로그래밍을 구성하는 다양한 요소와 구현 기법 객체지향 프로그래밍 온라인 영화 예매 시스템이라는 구체적인 예시로 설명을 시작한다. 객체지향 프로그래밍 1. 어떤 클래스가 필요한지 고민하기 전, 어떤 객체들이 필요한지 고민하라. 2. 객체를 독립적인 존재가 아닌, 기능을 구현하기 위해 협력하는 공동체의 일원으로 파악하라. 도메인(domain) - 문제를 해결하기 위해 사용자가 프로그램을 사용하는 분야 프로그래머는 도메인의 구조(객체들의 관계)에 맞게 클래스들을 구성하는 것이 좋다! 객체 ..

티스토리툴바