본문 바로가기
728x90

ComputerScience/Algorithm & Data Structure

 (9)
Algorithm&DataStructure - Backtracking 1. Backtracking - 모든 경우의 수를 고려하는 트리탐색 알고리즘이다. - 탐색중 현재 경로가 유망하지 않다면 가지치키를 할 수 있다. - 유망하지 않다 = 더 이상 탐색할 필요가 없다. 2. 백준 15649번 - 1부터 n 까지의 자연수 중 서로 다른 m개를 골라 줄세우는 경우들을 구한다. (nPm) - m에 따라서 경우의 수 tree가 만들어진다. - 이 트리에 대해서 깊이 우선의 탐색을 수행하는데 조건에 따라 탐색을 중지할 수 있다. - 이미 m개를 골랐다면 더 이상 깊이 트리를 탐색할 필요가 없으니 종료 조건에서 가지치를 하는 것이다. void backtracking(int count = 0) { if(count == m) { for(int i =0; i
Algorithm&DataStructure - Map, Set 1. (Ordered) Map - key와 value 쌍으로 이루어진 트리구조이다. 항상 정렬된 상태를 유지한다. - 따라서 탐색, 삽입, 삭제시 O(logn)의 복잡도를 갖는다. - key의 중복을 허용하지 않는다. - 따라서 동일한 키의 쌍의 삽입은 무시된다. - 중복된 원소를 갖고 싶다면 multi map을 사용한다. #include map ma; ma.insert(make_pair("hi", 3)); ma["hi"] = 10; cout second
Algorithm&DataStructure - Dijkstra 1. Dijkstra - 간선에 가중치가 있는 그래프에서 시작 노드가 주어졌을때 시작 노드로부터 각 노드까지의 최단 경로를 찾는 알고리즘이다. - 참고 : https://blog.naver.com/ndb796/221234424646 - 1번 노드의 비용이 가장 작기 때문에 1번 부터 시작해서 갈 수 있는 노드들의 비용을 갱신한다. - 1번을 제외하고 노드중에 비용이 가장 작은것은 4번이다. - 4번을 경유했을 때, 나머지 2, 3, 5, 6번 노드의 비용을 갱신한다. - 1, 4 번을 제외하고 남은 노드 중 비용이 가장 적은 것은 2번이다. - 2번을 경유해서 3, 5, 6번으로 가는 최소 비용을 갱신한다. - 1, 2, 4 번을 제외하고 3, 5, 6 중에 최소 비용은 5번이다. - 5번을 경유해서 나..
Algorithm&DataStructure - Queue 1. Linear Queue - 선입선출(FIFO, First In First Out) 방식의 선형 자료구조 - 문제점 : rear, front는 계속 증가만 한다. 나중에 한정된 메모리 끝에 rear가 도달 했을 때, 사실상 메모리에 비어 있는 공간이 있을 수 있다. 즉, int 100개 만큼의 메모리를 할당해도 100개의 정수를 넣기도 전에 rear가 끝에 도달 할 수 있다. - 해결 1 : 빈 공간이 생길 때 마다 원소들을 앞으로 당긴다. - 해결 2 : Circular Queue - 해결 3 : Linked List로 구현 class Queue { private: int front; int rear; int count; const int size; int* values; public: Queue(..
Algorithm&DataStructure - Dynamic Programming 1. Dynamic Programming - 크고 어려운 문제가 있으면 잘게 나누어서 처리하되 한번 푼 문제는 다시 풀지 않음 - 이미 계산한 결과는 배열에 저장하고 필요시 다시 계산하는 것이 아니라 활용 - 이런 과정을 Memoization이라고 한다. - DP를 적용하려면 대게 두가지 조건이 충족되어야 한다. 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제의 정답은 그것을 포함하는 큰 문제에서도 동일하다. - 즉 여러개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종 목적에 도달하는 방식이다. 2. 백준 9461번 - n번째 삼각형의 변의 길이를 구해야한다. - 먼저 정답을 도출하기 위한 점화식을 구한다. - 이 점화식을 재귀로 풀면 다음과 같다. 동일한 값을 구하기 위해 같은 연산..
Algorithm&DataStructure - BFS 1 BFS - 그래프를 순회(하나의 정점에서 시작해서 차례대로 모든 정점들을 한 번씩 방문) 하는 알고리즘 중 하나 - 한 정점에서 가까운 점들을 우선적으로 탐색, 따라서 시작점에서 도착점까지의 최단거리를 보장해준다. - 탐색 시 어떤 노드에 대해서 방문을 했는지 안 했는지를 알고 있어야 한다. - 큐를 활용해서 구현한다. 2 백준 2178번: 미로탐색 - N×M크기의 배열로 표현되는 미로가 있다. - 0은 벽을 나타내고 1은 이동할 수 있는 칸이다. - 상하좌우로만 이동이 가능하다. - (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하라. #include #include #include #include using namespace std; int dir[4] =..
Algorithm&DataStructure - DFS 1 DFS - 깊이 우선 탐색, Depth-First Search - 그래프를 순회(하나의 정점에서 시작해서 차례대로 모든 정점들을 한 번씩 방문) 하는 알고리즘 중 하나 - 비유를 하자면 미로에서 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 진행할 수 없을 때, 가장 가까운 분기점으로 되돌아와 다른 방향으로 다시 탐색을 진행. 모든 노드를 순회할때까지 이 과정을 계속함 - 탐색 시 어떤 노드에 대해서 방문을 했는지 안 했는지를 알고 있어야 한다. - 스택을 활용한 구현, 재귀 호출을 활용한 구현 2가지가 존재, 본질적으로 스택 구조를 활용한다는 점에서는 같은 방식임. 2 백준 2606번: 바이러스 - 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있..
Algorithm&DataStructure - Divide and Conquer 1 Divide and Conquer - 분할 정복 - 재귀를 활용 - 퀵소트, 머지소트, n제곱 구하기 등에 활용 1단계 : 분할, 원래 문제를 분할하여 비슷한 유형의 하위 문제들로 나눔 2단계 : 정복, 하위 문제를 정복. 이때 분할, 탈출 조건을 설정하여 재귀로 해결한다. 3단계 : 합치기, 정복된 문제들을 종합하여 초기 문제를 해결 - 즉 한 문제를 유형이 비슷한 여러개의 하위 문제들로 나누어 해결하고 나중에 합친다. 2 백준 2630번: 색종이 만들기 - 0 또는 1로만 이루어진 정사각 색종이들의 수를 구하라 #include using namespace std; class Paper{ private: int n; bool** table; int blue; int white; public: Pap..
728x90

티스토리툴바