조준화의 오류정정

예제 1 3 1 3 2 6 answer : 16 예제 2 4 2 4 2 3 1 answer : 19 n개의 카드에 대해 어떤 두 카드의 숫자를 그 두 카드의 합으로 바꾸는 것을 m번 진행한 뒤 n개의 카드의 숫자 합이 최소가 되게 하는 문제이다. 먼저 그리디 하게 매 턴마다 가장 작은 숫자 두 개를 고르면 된다고 생각했다. 매 턴마다 그리디 하게 숫자를 고르는 것까지는 문제가 없어 보였고, 구현 부분은 우선순위 큐를 이용해 간단히 우선순위를 내림차순으로 하고, pop 두 번 후 두 숫자를 더한 값을 push 두 번 하는 식으로 구현했다. 여기까지는 쉬웠지만 주의할 점이 하나 있었다. n개의 카드가 최대 1,000개이고 15 * n번의 턴이 진행되며 각 카드의 숫자는 최대 1,000,000여서 int 자료..

힙 최대 힙은 완전 이진트리이고, 부모가 항상 자식보다 큰 자료구조이다. 완전 이진트리란, 마지막 레벨을 제외하고 모든 레벨의 노드가 다 채워져 있고 마지막 레벨은 왼쪽부터 채워지는 트리이다. 최소 힙은 반대로 부모가 항상 자식보다 작다. 힙은 완전 이진트리의 특성상 부모와 자식의 index가 명확해서 배열을 사용한다. A[i]의 부모는 A [i/2]이고 왼쪽 자식은 A [2*i] 오른쪽 자식은 A [2*i + 1]이다. 힙은 힙 특성 유지하기(heapify), 힙 만들기(buildHeap), 삽입(insert), 삭제(delete)만 알면 된다. 힙 구현 힙 특성 유지하기(heapify) 배열 A에 대해 i번째 원소를 최대힙의 루트가 되게 한다. 아래는 퍼수도 코드이다. heapify(A, i){ l ..

교재 Introduction To Algorithms 3rd Edition를 바탕으로 수업시간에 다룬 내용 위주로 정리하였다. ​ 알고리즘 기본 용어 정리 매개변수((parameter))는 문제에서 언급된 할당되지 않은 변수들이다. 문제 : 오름차순으로 n개의 정수 리스트 S를 정렬하시오. → 매개변수 : n, S ​ 실체((instance))는 매개변수에 실제로 할당된 값이다. → 문제 : 오름차순으로 n개의 정수 리스트 S를 정렬하시오. → 실체 : n = 6, S = [10, 7, 11, 5, 13] ​ 알고리즘이란 어떤 수학적으로 엄밀히 정의된 문제를 풀기 위한 유한한 절차와 방법이다. 알고리즘의 실험적 분석 주어진 알고리즘을 소스코드로 구현한 다음, 실제 환경에서 동작시켜 실제 실행 시간을 측정..

예제 입력 1 5 -2 4 -99 -1 98 예제 출력 1 -99 98 배열의 어떤 두 원소의 합 중 0과 가장 가까운 쌍을 찾는 문제이다. 투 포인터 알고리즘으로 풀 수 있다. 투 포인터 알고리즘이라 칭하면 어려워 보이지만 사실 그냥 포인터 두 개를 놓고 특정 기준에 따라 포인터를 옮겨가면서 배열을 탐색하는 알고리즘이다. 여기서 특정 기준을 찾는 게 문제의 난이도를 결정한다. 투 포인터 알고리즘으로 푼다고 생각했을 때 자세한 알고리즘은 어떻게 짤까? 우선 배열을 정렬하고, 포인터 두 개를 설정한다. 아직 이 포인터들을 차례로 둘지, 처음과 끝에 둘지 혹은 다른 방법으로 둘지는 생각하지 않은 상태이다. 이 포인터를 0과 가장 가까운 쌍을 찾을 수 있도록 옮기면서 배열을 탐색하면 된다. 그럼 여러 방법들을..

예제 입력 1 2 5 3 8 1 7 3 1 3 6 1 3 4 2 13 7 103 11 290 215 예제 출력 1 7 1 B의 원소들보다 더 큰 A의 원소 쌍을 찾으면 되는 문제이다. 우선 정렬을 한 뒤 A의 원소보다 작은 B의 원소의 index를 기억해 뒀다가 A의 다음 원소를 비교할 때 그 index를 써먹는 식으로 해결하였다. p_b 원소로 그 index를 기억해 놓고, A의 원소를 차례로 탐색하면서 A[i]가 B[p_b]보다 크면 p_b++을 하는 방식이다. 물론 p_b는 B 원소 개수보다 작아야 한다. 만약 p_b가 B 원소 개수 - 1과 같다면, 즉 p_b가 B의 마지막까지 갔다면 A의 그다음 원소는 당연히 모든 B의 원소보다 크다. 이 해법의 중간 과정을 보자. /** 정렬 7795 먹을 것..

Vector 벡터의 선언 vector 변수명(m, n)과 같이 초기화하며 m만큼 벡터를 생성 후 숫자 n로 초기화한다. vector 변수명[] = {, }과 같이 2차원 벡터를 선언한다. 이때 열의 크기는 고정이고 행의 크기는 변할 수 있다. vector 변수명과 같이 2차원 벡터를 선언할 수 있고 이 경우는 열과 행 모두 크기가 변할 수 있다. 벡터의 원소에 접근 v.begin() : 벡터 시작점의 주소 값을 반환한다. v.end() : 벡터 벡터의 마지막 원소의 주소값을 반환한다. v.at(i) : 벡터의 i번째 요소에 접근한다. 이때 범위를 검사한다. v [i] : 벡터의 i번째 요소에 접근하며 이때 범위는 검사하지 않는다. v.front() : 벡터의 첫 번째 값을 리턴한다. v.back() : ..

예제 입력 1 5 5 1 1 4 1 2 2 3 2 4 3 4 예제 출력 1 1 4 3 2 0 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 무방향 그래프를 구현하고 오름차순으로 DFS를 구현한 뒤 정점들에 대한 방문 순서를 차례로 출력하면 되는 문제이다. DFS의 기본 이론은 시작 정점에 대해 방문할 수 있는 정점 중 정해진 기준(문제에서는 오름차순)에 따라 방문하고, 다시 방문한 정점에 대해 방문할 수 있는 정점 중 기준에 따라 반복하..

Range based for Range based for문은 알아서 데이터 리스트를 순회하는 for 반복문이다. 일반적인 for문과 달리 사용할 때 순회할 리스트의 index는 넘겨주지 않고 for문 안에서도 사용하지 않는다. 사용법은 예제로 보자. #include using namespace std; int main() { int arr[] = {0, 1, 2, 3, 4, 5}; for (int i : arr) { i += 1; cout