본문 바로가기

Algorithm20

[C++] max_element(), min_element() algorithm 헤더에 있는, 배열이나 벡터 구간 안에서 최대, 최솟값을 찾는 함수이다. max_element(arr, arr+size) 혹은 max_element(vec.begin(), arr.end()) 처럼 시작 주소 혹은 이터레이터, 끝 주소 혹은 이터레이터를 넣어주면 된다. return 형식도 주소 혹은 이터레이터이기 때문에, 값을 알고 싶다면 *max_element(arr, arr+size) 처럼 써준다. #include #include #include using namespace std; int arr[10] = {1, 2, 10, 4, 9, 3, 7, 5, 6, 8}; vector vec; int main() { vec.push_back('c'); vec.push_back('a'); ve.. 2020. 4. 29.
[알고리즘] 카데인 알고리즘(Kadane's algorithm) 카데인 알고리즘(Kadane's algorithm)은 배열의 최대 부분 합을 O(n)의 시간복잡도로 구하는 알고리즘이다. i번째 인덱스를 오른쪽 끝으로 하는 부분배열들의 최대 부분 합을 M[i]라고 하면, M[i+1]은 M[i]+arr[i+1]이거나 arr[i+1]중 더 큰 값이다. M[0]은 arr[0]인 1이다. M[1]은 arr[1] = -6과 M[0] + arr[1] = -5 중 더 큰 -5이다. M[2]는 arr[2] = 4와 M[1] + arr[2] = -1 중 더 큰 4이다. 왜 M[i+1]이 max(M[i] + array[i+1], array[i+1]) 인지 이해하면 쉽다. i를 오른쪽 끝으로 하는 부분배열 중 최대 부분 합이 음수이면 굳이 더하지 않고 그냥 i+1번째 인덱스부터 새로 더하.. 2020. 4. 25.
[BOJ] 2098. 외판원 순회 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 현재까지 방문한 경로를 표현할 때 비트마스크를 이용하는 문제이다. 개인적으로 DP 배열을 현재 경로와 인덱스 두 개의 인자를 써야 한다는 아이디어를 떠올리기가 힘들었다. #include #include using namespace std; #define INF 1000000000 int N, W[16][16]; int dp[65536][16]; i.. 2020. 4. 17.
[알고리즘] 비트마스크(Bit Mask) 비트마스크(Bit Mask)는 알고리즘이라기보다는 기법인데, 한 비트가 0 또는 1의 두 가지 값을 갖는다는 사실을 이용해 2진수 배열을 십진수로 변환하여 사용하는 테크닉이다. 예를 들어 {true, false, true, false}인 배열을 2진수로 1010으로 표현하고, 다시 십진수로 변환하면 10이 된다. 비트마스크 기법을 이용하면 bool 배열간의 연산을 간단하게 할 수 있다. {true, false, true, false} 배열과 {true, false, false, true} 배열을 각각 & 연산으로 비교할 때, 일반적으로는 반복문을 이용해 배열의 각 인덱스마다 비교해줘야 할 것이다. 그런데 비트마스크 기법을 이용해 {true, false, true, false} 배열을 10으로, {true.. 2020. 4. 16.
[자료구조] 세그먼트 트리(Segment Tree) 세그먼트 트리(Segment Tree)는 부분 합을 트리 구조에 저장해서, 값이 바뀔 수 있는 상황에서도 부분합을 빠르게 구할 수 있는 방법이다. 세그먼트 트리를 그려보면 이런 느낌이다. 위의 대괄호 안에 들어있는 숫자는 각 노드의 인덱스이고, 아래 큰 숫자는 부분합의 범위이다. 즉 루트 노드인 [0]에는 배열의 0~9번째 값들의 합이 저장되어 있고, [11] 노드에는 배열의 5~6번째 값들의 합이 저장되어 있는 식이다. 구현 | 1. init 배열의 초기 값을 세그먼트 트리에 처음 넣는 함수이다. 이때는 루트 노드 [0]부터 아래로 내려간다. 한 노드에 값을 채울 때는 자식 노드에 값을 먼저 채우고 그 뒤에 그 합을 쓰면 되는 것이다. 그런 식으로 말단 노드 (예를 들어, 6번째부터 6번째까지의 합 노.. 2020. 4. 14.
[알고리즘] 강한 연결 요소(Strongly Connected Component) 강한 연결 요소(Strongly Connected Component, SCC)는 어떤 양방향 그래프 내에서 다음 조건을 만족하는 부분집합이다. 임의의 강한 연결 요소 내부의 모든 정점끼리는 서로 이어진 경로가 존재한다. 임의의 강한 연결 요소 내부의 정점과 외부의 정점끼리는 서로 이어진 경로가 존재하지 않는다. 즉 이는 어떤 한 정점에 대해 첫번째 조건을 만족하는 최대의 부분집합이라고 할 수 있다. 위 그래프에서 {A, B, C, E}, {D, G, H}, {F}, {I}가 강한 연결 요소이다. 어떤 그래프에서의 SCC를 찾는 알고리즘으로는 코사라주 알고리즘이 있다. 코사라주 알고리즘 | 코사라주 알고리즘은 DFS를 이용한 위상 정렬을 토대로 SCC를 찾는 알고리즘이다. 그래프와 역방향 그래프를 준비한다.. 2020. 4. 13.
[자료구조] 큐(Queue) 큐(Queue) | 한 쪽 끝에서는 자료를 넣고, 반대쪽 끝에서는 자료를 뺄 수 있는 선형 자료구조. FIFO(First-In-First-Out) | 먼저 들어간 자료가 먼저 나온다. 인큐(Enqueue) | 큐에 자료를 넣는 것. 디큐(Dequeue) | 큐에서 자료를 빼는 것. 사이즈(Size) | 큐의 크기. 큐에 들어 있는 자료 수. 프론트(Front) | 큐의 가장 앞에 있는 자료. 백(Back) | 큐의 가장 뒤에 있는 자료. 2019. 11. 11.
[자료구조] 스택(Stack) 스택(Stack) | 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 선형 자료구조. LIFO(Last-In-First-Out) | 먼저 들어간 자료가 나중에 나온다. 푸시(Push) | 스택에 자료를 넣는 것. 팝(Pop) | 스택에서 자료를 빼는 것. 사이즈(Size) | 스택의 크기. 스택에 들어 있는 자료 수. 탑(Top) | 스택의 가장 위에 있는 자료. (접근 가능한 자료.) 2019. 11. 3.

티스토리툴바