망하면 망하는 대로 세계여행! 망하면 망하는 대로 세계여행!

www.acmicpc.net/problem/14427 14427번: 수열과 쿼리 15 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 www.acmicpc.net 1. 문제 길이가 N인 수열이 주어진다. 1을 입력받으면, 주어진 수열에서 가장 작은 값의 인덱스를 출력한다. 2를 입력받으면, i번째 수열의 값을 v로 바꾼다. 2. 해결 1) 가장 작은 값만 필요하기 때문에 우선순위 큐를 이용하였다. 2) 수열의 각 정보는 Node 구조체로 구성하였다. - num : 수열의 값 - heapIndex : 2를 입력받으면,..

www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 1. 문제 주어지는 값들 중에서 현재 중간값을 출력한다. 2. 해결 1) 최대힙(Max Heap)과 최소힙(Min Heap)을 구현해야 한다. 왜냐하면 최대힙은 root 보다 모두 작은 값들로 이루어져 있고, 최소힙은 root 보다 모두 큰 값들로 이루어져 있다. 따라서 최대힙 또는 최소힙의 root가 중간값이다. MaxHeap MinHeap Root Root | | Root 보다 작은 수들 R..

힙정렬 (Heap Sort) 1. 기본동작 1) 모든 노드를 순회하면서, 현재 노드를 기준으로 위쪽으로 올라가며 Heapify 한다. 2) 루트 값을 가장 뒤쪽으로 보내고 Heapify 하며 크기를 줄여간다. 2. 시간복잡도 : O(N * log N) 3. 구현 - BOJ 의 11650번 좌표정렬하기를 힙정렬을 직접 구현하여 풀었습니다. (www.acmicpc.net/problem/11650) - 아래 heapSort 코드는 SWEA(swexpertacademy.com/main/visualcode/main.do#/home/mainlayout) 에서 Priority Queue의 레퍼런스 코드를 참고하여 구현하였습니다. #include struct Node { int x, y; } heap[100001]; ..

www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net - 연결리스트(메모리 제한), DFS + 이분탐색(시간제한) 으로 구현하였습니다. (입출력 외 라이브러리를 사용하지 않은 구현입니다.) #include int N, M; int start, end; bool visit[10001]; struct Bridge { int linked, weight; Bridge* next; } b[200002]; Bridge* bri..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net - BFS 를 이용하였으며, Queue를 직접 구현하였습니다. #include bool computer[101][101]; int queue[101]; bool visited[101]; int main() { int computerN; scanf("%d", &computerN); int linkN, a, b; scanf("%d", &linkN); for (int i = 0; i < linkN; ++i)..

www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 다이나믹 프로그래밍(DP) 을 이용하였다 #include #include using namespace std; int a[100000], d[100000]; int main() { int n, ans; cin >> n; for (int i = 0; i > a[i]; } d[0] = a[0]; for (int i = 0; i < n; i++) { d[i] = max(a[i], d[i - 1] ..

www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 다이나믹 프로그래밍(DP)을 이용하였다 #include #include using namespace std; int a[1000], d[1000]; int main() { int n, ans = 0; cin >> n; for (int i = 0; i > a[i]; for (int i = 0; i < n; i++) { d[i] ..

www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 다이나믹 프로그래밍을 이용하였다. #include #include using namespace std; int p[10001], d[10001]; int main() { int N; cin >> N; for (int i = 1; i > p[i]; } d[0] = 0; for (int i = 1; i