1. 트리(Tree)란? 그래프의 한 종류로 방향성을 가지며 사이클이 없는 하나의 연결 그래프 DAG(Directed Acyclic Graph, 방향 비순환 그래프)의 한 종류 노드로 이루어진 비선형 자료구조로서 하나의 루트 노드를 갖고, 루트 노드는 0개 이상의 자식 노드를 가진다. 루트 노드를 제외한 나머지 노드들은 각각 루트의 부분트리(재귀적 정의) -노드 용어 루트 노드: 부모가 없는 노드, 하나의 루트만을 가짐 부모 노드: 어떤 노드에 연결된 이전 레벨의 노드 자식 노드: 어떤 노드에 연결된 다음 레벨의 노드 조상 노드: 루트에서부터 특정 노드에 이르기까지 있는 모든 노드 단말 노드: 자식이 없는 노드, =잎 노드 간선: 노드를 연결하는 선 형제 노드: 같은 부모를 가지는 노드 -트리 용어 노드..

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( ): 벡터의 원소 ..