목록PS (176)
득이공간
해당 게시물은 하루코딩님의 'Do it! 알고리즘 코딩테스트 with C++' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 목차 - 3장. 탐색 3-1. 깊이 우선 탐색 3-2. 너비 우선 탐색 3-3. 이진 탐색 📌 3-1. 깊이 우선 탐색 * 깊이 우선 탐색 - 시작 노드에서 출발해서 탐색할 한 쪽 분기를 정해 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동해서 다시 탐색을 수행하는 알고리즘 - 기능: 그래프 완전 탐색 - 특징: LIFO, 재귀 함수로 구현 or 스택 자료구조 이용 - 시간 복잡도: O(V+E) * 깊이 우선 탐색 동작 원리 1. 그래프를 인접 리스트로 표현 2. 방문 배열 초기화, 시작 노드 선택 3. 방문 배열 체크 후 인접 노드 중 미방문 노드 탐색 - 재..
해당 게시물은 하루코딩님의 'Do it! 알고리즘 코딩테스트 with C++' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 목차 - 2장. 정렬 2-1. 버블 정렬 2-2. 선택 정렬 2-3. 삽입 정렬 2-4. 퀵 정렬 2-5. 병합 정렬 2-6. 기수 정렬 📌 2-1. 버블 정렬 * 버블 정렬 - 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬 - 시간 복잡도: O(N^2) * 버블 정렬 동작 원리 1. 비교 연산이 필요한 루프 범위 설정 2. 인접한 데이터 값 비교 3. swap 조건에 부합하면 swap 연산 수행 4. 루프 범위가 끝날 때까지 2~3 반복 5. 정렬 영역 설정. 다음 루프를 실행할 때는 이 영역을 제외 6. 비교 대상이 없을 때까지 1~5 반복 *..
12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net #include #include #include using namespace std; vector LIS; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; int Number; cin >> Number; LIS.emplace_back(Number); for (int i = 1; i > Number; if (Number < ..
2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net #include #include #include using namespace std; vector Weights; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; Weights.reserve(N); for (int i = 0; i > Weight; Weights.emplace_back(Weigh..
2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net #include #include #include using namespace std; vector Houses; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, C; cin >> N >> C; Houses.reserve(N); for (int i = 0; i > X; Hous..
1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net #include #include using namespace std; const int& MaxSize = 100000; int Map[MaxSize + 1]; queue SearchQueue; bool IsInSize(int Node) { return (Node >= 0 && Node > N >> K; SearchQueue.emplace(N); while (!SearchQueue.empty()) { int Current = Searc..
7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net #include #include #include using namespace std; vector Box; queue Queue1; queue Queue2; int BFS(int N, int M) { int Day = 0; while (true) { while (!Queue1.empty()) { int Row = Queue1.front().first; int Col = Queue1.front().second; Queue1.pop(); // Lef..
11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net #include #include #include using namespace std; vector Neighbors; vector Visited; void DFS(int Node) { Visited[Node] = true; for (const int& Neighbor : Neighbors[Node]) { if (Visited[Neighbor]) { continue; } DFS(Neighbor); } ..
1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net #include #include #include using namespace std; int Map[50][50]; list Neighbors[50][50]; void DFS(int Row, int Col) { Map[Row][Col] = 0; for (const pair& Neighbor : Neighbors[Row][Col]) { if (Map[Neighbor.first][Neighbor.second] == 0) { continue; } DFS(Neighbor.first..
1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net #include #include #include using namespace std; priority_queue Cards; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; for (int i = 0; i > Card; Cards.emplace(Card); } int Cnt = 0; for..