1. 트리(Tree)란? 그래프의 한 종류로 방향성을 가지며 사이클이 없는 하나의 연결 그래프 DAG(Directed Acyclic Graph, 방향 비순환 그래프)의 한 종류 노드로 이루어진 비선형 자료구조로서 하나의 루트 노드를 갖고, 루트 노드는 0개 이상의 자식 노드를 가진다. 루트 노드를 제외한 나머지 노드들은 각각 루트의 부분트리(재귀적 정의) -노드 용어 루트 노드: 부모가 없는 노드, 하나의 루트만을 가짐 부모 노드: 어떤 노드에 연결된 이전 레벨의 노드 자식 노드: 어떤 노드에 연결된 다음 레벨의 노드 조상 노드: 루트에서부터 특정 노드에 이르기까지 있는 모든 노드 단말 노드: 자식이 없는 노드, =잎 노드 간선: 노드를 연결하는 선 형제 노드: 같은 부모를 가지는 노드 -트리 용어 노드..
🔻Extracurricular Activity/ALCUK
1. MST란? minimum spanning tree: 최소 신장 트리 -신장 트리(spanning tree): 무방향 그래프에서 모든 정점을 포함하는 트리 모든 정점을 포함하지만 사이클은 생성하면 안 된다 정점의 개수 n개, 간선의 개수 n-1개 -최소 신장 트리(minimum spanning tree): 사용된 간선의 가중치의 합이 최소가 되는 신장 트리 2. 동작 원리 -크루스칼 알고리즘 그래프의 모든 간선을 가중치의 오름차순으로 정렬한다 가중치가 낮은 간선부터 그래프에 삽입한다 사이클을 형성하는 간선은 삽입하지 않고 넘어간다 그래프에서 간선이 n-1개 삽입될 때까지 반복하고, n-1개가 된다면 멈춘다 -프림 알고리즘 그래프에서 시작 정점을 선택한다 선택한 정점에 부속된 모든 간선 중 가중치가 가..
1. 유니온-파인드(union-find)란? 상호배타적집합(Disjoint-Set, 서로소 집합)을 표현할 때 사용하는 자료구조 MST(크루스칼)에 사용되는 알고리즘이다 여러 노드가 존재할 때, 두 노드를 같은 집합으로 묶고 같은 그래프에 속하는지 판별 2. 동작 원리 각 번호의 노드가 어떤 부모노드를 갖고 있는지 판별하고 Find: 한 노드가 어느 집합에 포함되어 있는지 찾는 연산 Union: 노드 a가 포함된 집합과 노드 b가 포함된 집합을 합치는 연산 3. 코드 int N, M; int parent[1000001]; int Find(int x) { if (parent[x] == x) { return x; } else{ return parent[x] = Find(parent[x]); //return ..
1. 위상정렬(Topological Sort)이란? 방향 그래프에서 선후관계에 따라 적절한 순서를 찾는 알고리즘 전체 순서가 아닌 일부 순서가 주어진 경우 여러가지 경우로 줄을 세울 수 있다 -문제 유형 어떤 작업ㄷ르에 대한 순서가 주어졌을 때 자신보다 선행되어야 할 일을 다 끝내야 작업에 들어갈 수 있게 주어졌을 때 2. 동작 원리 방향은 존재하지만 사이클은 존재해선 안 된다. (순서를 명확히 정할 수 없기 때문) -bfs 방식 위상정렬 indegree가 0인 노드를 큐에 넣어준다 큐의 front(현재 정점)을 방문한다 front()에 연결되어있는 다음 정점들을 방문하고 indegree[next]를 1씩 감소시킨다 감소시켰을 때 indegree가 0이라면 큐에 넣어준다 -dfs 방식 위상정렬 방문하지 ..
1. 자료구조란? 자료를 효율적으로 표현하고 저장, 처리할 수 있도록 정리하는 것 삽입, 삭제, 탐색 세 가지 연산을 빨리 하기 위해 각 상황에 맞는 다양하고 효율적인 자료구조들이 많이 개발되었다. -스택 후입선출 구조로 마지막 삽입한 원소는 맨 위에 있고, 제일 먼저 삭제된다 웹 브라우저 방문기록(뒤로가기) 역순 문자열 만들기 실행 취소(undo) 후위 표기법 계산 수식의 괄호 검사(연산자 우선 순위 표현을 위한 괄호 검사) -큐 선입선출 구조로 뒤에서만 원소를 삽입하고 앞에서만 원소를 삭제할 수 있다 우선순위가 같은 작업 예약(프린터의 인쇄 대기열) 프로세스 관리 너비우선탐색 캐시 구현 -덱 큐의 양쪽 끝에서 삽입과 삭제 연산을 둘 다 수행할 수 있는 자료 구조 2. 동작 원리 -스택 push(삽입할..
1. 이분탐색(Binary Search)이란? 탐색 범위를 절반씩(두 부분으로 나누어서) 줄여 가며 원하는 값을 찾는 방식 이분 탐색을 실시하기 위해선 정렬된 배열이나 벡터가 필요하다 시간복잡도 또한 탐색 범위가 절반씩 줄어든다. -> O(logN) 2. 동작 원리 -이분 탐색 배열이나 벡터를 정렬한다 left, right값(범위의 최소, 최대)으로 mid값을 설정한다 mid값과 구하고자 하는 값(ans)를 비교한다 mid mid+1 mid > ans --> mid-1 ans를 찾을 때까지 반복 -결과값 구하고자하는 값을 찾았을 때 값을 리턴한다 최적의 해를 찾는 경우 left right이 되므로 종료된다 3. 코드 int arr[100005]; int binarySearch(int l..
1. DP(Dynamic Programming)이란? 하나의 큰 문제를 여러개의 작은 문제로 분할하여 푸는 방법 이미 계산된 작은 문제의 결과값을 별도의 메모리 영억에 저장해두고 활용한다 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시킬 수 있다 방법: top-down(재귀), bottom-up(반복문) 대표예: 피보나치 수열 2. 동작 원리 -사용 조건 큰 문제를 작은 문제로 나눌 수 있다 작은 문제에서 구한 값은 그것을 포함하는 큰 문제에서도 동일한 값으로 사용된다. -사용 방법 완전 탐색으로 접근한다. 반복되는 부분 문제를 찾는다. 기저단계를 설정한다. (점화식으로 더이상 계산하지 못하는 부분) 점화식을 설정한다 중복된 문제를 한번만 계산하기 위해 메모이제이션을 이용한다(이전에 계산한..
1. 재귀란? 재귀(recursion)은 자신을 정의할 때 자기 자신을 재참조하는 방법 2. 동작 원리 재귀함수: 어떤 알고리즘이나 함수가 자기 자신을 호출하여 작업을 수행하는 방식의 함수 함수에서 자기 자신 함수를 또 호출해서 스택에 저장하기 때문에 탈출 조건이 없다면 스택 오버플로우 발생 재귀함수를 쓰는 대표적 예: 피보나치 수열, 팩토리얼, 순열, 분할정복 ※공부 중 작성한 내용이기에 틀린 부분이 있을 수도 있습니다!
1. 완전탐색(브루트포스 알고리즘)이란? 모든 경우의 수를 다 탐색하는 방법으로 '무식하게 푼다'라고도 한다 가능한 모든 경우의 수를 계산하고, 주어진 문제를 선형 구조로 구조화 한다. 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색 후 구성된 해를 정리 2. 동작 원리 단순 for문: for문, if문 등으로 모든 케이스를 만들어서 탐색하는 방식 비트마스크: 2진수를 이용하는 컴퓨터 연산을 이용하는 방식 재귀 함수: 부분 문제로 쪼갤 수 있는 경우에 적합한 방식 순열: 주어진 입력에서 순서가 중요할 때 이용하는 방식 -> 경우의 수 N!, next_permutation, prev_permutation BFS/DFS: 그래프의 모든 정점을 탐색하는 완전 탐색 알고리즘 ※공부 중 작성한 내용이..
1. 정의 -벡터란? 요소가 추가되거나 삭제될 때마다 자동으로 메모리를 재할당하여 크기를 동적으로 변경할 수 있는 시퀀스 컨테이너 -페어란? 어떤 자료형을 쌍으로 묶어서 한 쌍으로 표현 -정렬이란? 데이터를 특정한 조건에 따라 일정한 순서가 되도록 다시 배열하는 것 -에라토스테네스의 체란? 소수판별법: 입력 받은 숫자보다 작은 모든 숫자로 나누어본다 입력 받은 숫자의 제곱근(루트 씌우기)보다 작은 모든 숫자로 나누어본다 에라토스테네스의 체 2. 동작 원리 -일차원 벡터 vector 객체이름(초기크기); push_back( ): 현재 벡터의 마지막 위치에 새로운 원소 삽입, 백터의 크기 1 증가 pop_back( ): 벡터의 마지막 원소 제거, 벡터가 비어있을 경우 오류 발생 size( ): 벡터의 원소 ..
1. 정의 -문자열이란? string이나 char[ ] 배열 초기화 함수: memset(배열이름, 초기화값, sizeof(배열이름)); -GCD란? Greatest Common Divisor: 최대공약수 -LCM이란? Least Common Multiple: 최소공배수 두 자연수의 공통된 배수 중 가장 작은 수 -> 최대공약수를 통해 구할 수 있음 2. 동작 원리 -GCD 방식1: 두 수 m, n를 입력받고 2부터 n까지 두 자연수를 모두 나누어보면 최대공약수를 구할 수 있음 방식2: 유클리드 호제법 m을 n으로 나눈 나머지를 r이라고 하면, m과 n의 최대공약수는 n과 r의 최대공약수와 같은 것을 이용 -LCM 두 수의 곱을 두 수의 최대공약수로 나누어주면 최소공배수를 알 수 있음 3. 코드 //GCD..
1. 플로이드-와샬이란? 다익스트라 알고리즘과 같이 최단 거리를 구할 수 있는 알고리즘 모든 정점에서 모든 정점으로의 최단 경로를 한번에 구하는 알고리즘 모든 쌍을 행렬로 선언하고 DP를 이용해 각 쌍의 최단 거리를 업데이트한다 거쳐가는 정점을 기준으로 최단 거리를 업데이트한다. 2. 동작 원리 정점 i에서 정점 j까의 최단 경로 dp[i][j] = min(dp[i][j], dp[i][n] + dp[n][j]) n -> 경유점 i에서 j로 곧바로 가는 경우 vs i에서 다른 정점 k를 거쳐 j로 가는 경로 3. 코드 void floyd() { for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { a..
1. 벨만 포드 알고리즘이란? 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘 간선의 가중치가 음수일 때도 최단 거리를 구할 수 있다. 다익스트라 알고리즘과 달리 매 반복마다 모든 간선을 확인한다. 시간복잡도가 느리다. -> O(VE) 2. 동작 원리 시작점에서 한 정점 x까지의 최단 경로를 구하다고 하면, x를 제외한 모든 노드(V-1)가 시작점과 x 사이의 최단 경로를 구성한다. 모든 정점으로 가는 최단 경로 갱신 과정을 V-1번 반복하면 된다. 음수사이클이 있는지 알아보려면 1번 더 돌려서 최단 거리가 갱신되는지 확인하기 3. 코드 #define INF 987654321 typedef pair P; long long dist[510]; //각 도시의 거리 계산 long long 필수 vec..
1. 다익스트라 알고리즘이란? Dijkstra 알고리즘은 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘 특정 노드에서 그래프의 모든 노드로 가는 최단 경로를 찾는 알고리즘 1:N관계이며 음수가중치는 없다 2. 동작 원리 dist배열은 시작 노드에서 i번째 노드까지의 거리를 뜻하고, 처음 시작점을 제외한 모든 노드를 INF로 초기화해줘야 함 방문하지 않은 정점 중에서 시작 노드로부터 거리가 가장 가까운 정점을 방문하고 방문한 정점에서 인접한 정점들에 대해서 거리를 갱신해줌 시간복잡도를 줄이기 위해 우선순위 큐를 이용 우선순위 큐는 내림차순으로 정렬되기 때문에 값을 넣을 때 -를 붙여주고 값을 빼낼 때도 -를 붙여서 빼준다 3. 코드 int start; int dist[20010]; vector ..
1. DFS, BFS란? 그래프 탐색: 하나의 정점으로부터 시작해서 차례대로 모든 정점을 한 번씩 방문하는 것 DFS와 BFS는 그래프 탐색의 일종 2. 동작 방식 DFS: 깊이우선탐색 stack이나 재귀함수를 이용함. 루트 노드에서 시작해서 해당 노드의 자식 노드를 먼저 탐색 이동할 때마다 가중치가 있거나 이동 과정에서 제약이 있는 경우 BFS: 너비우선탐색 queue를 이용함. 루트 노드에서 시작해서 해당 노드의 인접 노드를 우선적으로 탐색 단순 최단 경로를 찾는 문제 3. 코드 //1차원 DFS vector adj[1010]; bool visited[1010]; //dfs방문 void dfs(int now) { Dvisited[now] = true; printf("%d ", now); for (in..
