분류 전체보기233 [투 포인터] c++구현 및 백준 2003 예제 설명 목차 투 포인터 알고리즘 정의 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 정렬되어있는 두 리스트의 합집합에도 사용됨. 병합정렬(merge sort)의 counquer 영역의 기초가 되기도 합니다. 대표 예제 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 투 포인터 알고리즘 설명 크게 4가지 절차를 알면됩니다. 목표값보다 작으면 종착점을 증가시킨다. 목표값보다 .. 2024. 2. 28. [백준][이진 탐색] 1654 랜선 자르기 c++구현 및 설명 목차 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 문제 구현 방향 범위가 아주 크기 때문에 이진 탐색을 통해 해결하지 않으면 시간 초과가 나는 문제이다. 또한 정수의 범위가 매우 크기 때문에 long long int를 쓰고자 했다. 아래 기본 코드에서 약간 변형하고 아이디어를 더하면 풀리는 문제이다. 이진탐색 기본 구현 코드 #include #include #include using namespace std.. 2024. 2. 27. [정렬 알고리즘] 버블, 선택, 삽입 정렬 c++ 구현 단순한 정렬 알고리즘 3가지를 알아보고자 한다. 아래 알고리즘 3개는 정말 단순하기 때문에 금방 이해하고 구현할 수 있다. 버블 정럴 버블 정렬은 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다. 시간 복잡도 O(n^2) 코드 구현 #include using namespace std; // 버블 정렬 함수 void bubbleSort(int arr[], int n) { for (int i = 0; i arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; .. 2024. 2. 27. [백준][bfs] 1967 트리의 지름 c++ 구현 목차 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 문제 구현 방향 나는 리프 노드부터 bfs탐색을 시작하여 가중치를 더해준 후 그 중 가장 큰 가중치를 출력하는 방식으로 구현하였다. 가중치를 계속해서 누적해주는 것은 dp에서 착안하였다. 문제 풀이 시 주의할 점 그냥 인접행렬로 만들게 되면 메모리를 굉장히 많이 먹기 때문에 메모리 초과 오류에 빠진다. 따라서 구조체를 만들고 인접리스트를 사용하여 간선과 노드를 저장하.. 2024. 2. 24. 이전 1 ··· 48 49 50 51 52 53 54 ··· 59 다음 728x90
