IT 꿈나무 참다랑어

https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 처음엔 그냥 모든 수를 다 priority queue에 받아서 마지막에 pop하면서 N번째 찾으려고 했는데 그렇게 하니까 메모리 초과가 났음... 모든 원소를 전부다 pq에 넣으면 사이즈가 터진다는 걸 알고 pq의 사이즈가 N보다 작을때는 바로 push하고, pq의 사이즈가 N일때는 top을 pop해주고 push하는 식으로 구현함 #include #include #include #include using..

https://www.acmicpc.net/problem/2599 2599번: 짝 정하기 첫 줄에는 남학생 (또는, 여학생) 수를 나타내는 정수 N (3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 A초등학교 출신의 남학생 수와 여학생 수가 주어진다. 셋째 줄에는 B초등학교 출신의 남학생 수 www.acmicpc.net 간단한데 안간단하고.. 더 라이트하게 푸는 방식도 있을 거 같은데 못찾겠음ㅠㅠ 풀이 방식은 처음에 O(n^2)으로 풀었다가 다른 분들 코드 참고해서 다른 식으로 O(n)으로 한번 더 해결! 먼저 O(n^2) 풀이는 다음과 같음 #include using namespace std; int N; pair stud[3]; int ab, ac, ba, bc, ca, cb; int main..

https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 투포인터 이용해서 해결할 수 있는 문제 priority queue를 활용하면 메모리는 더 적게 걸리면서 해결할 수 있음. 하지만 시간이 더 오래.. 아 total 안만들고 그냥 바로 출력해도 되는데 어쨌든 두 배열중에 하나는 빨리 끝나니까 while문으로 배열 끝까지 탐색할 수 있도록 해주기! #include #include using namespace std;..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net dfs 로 해결. 대각선도 탐색 가능. #include #include using namespace std; int dx[8] = { 1, 1, 0, -1, -1, -1, 0, 1 }; int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 }; int** map; int** visited; int w, h; void dfs(int y, int x) { for (int i =..

https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 원래 재귀로 탐색하면서 트리 모양대로 입력된 수를 다시 배열하는 식으로 푸는 문제인 것 같은데 탐색 순서에서 규칙이 보여서 굳이 배열을 하나 더 만들지 않아도 수학적으로 풀 수 있을 것 같아서 그렇게 해결함 #include #include #include using namespace std; vector vec; int K, temp; int main() { cin >> ..

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 결국에는 사람과 사람 사이의 최단 거리를 찾아야함-> bfs로 해결 #include #include #include #include #define MAX 1e9 using namespace std; int N, M; vector map[101]; int bacon[101]; bool visited[101]; queue q; void bfs(int s..

https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net #include #include #include using namespace std; int N, temp; stack st; vector num; vector ret; int nidx = 0, ridx = 0; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 다익스트라 알고리즘을 적용하는 문제 기본적인 형태는 bfs와도 비슷하지만 priority queue를 썼다는 점이 중요한 문제라고 생각했다. #include #include #include #include #define INF 1e9 using namespace std; int V, E; int st; vector* edge; int* dist; void di..

동적계획법(dynamic programming, dp)는 큰 문제를 작은 문제로 나누어서 푸는 방법을 일컫는 말이다. 분할정복(Divide and Conquer)와 비슷하지만 분할정복은 큰문제를 작은 문제로 나누어 해결하고 나누어진 작은 해결법들을 다시 합쳐가면서(작은 문제에서 반복이 일어나지 않음) 문제를 해결하고, 동적계획법은 작은 부분문제들이 답이 바뀌지 않고 같은 값을 가지며 큰 문제를 해결해 나가는 것에 차이가 있다. 반복되는 규칙(점화식)을 가지고 문제를 풀어나가는 경우가 많으며 작은 수부터 차례로 접근하며 규칙을 찾아 이를 해결해야한다. 구현법은 bottom-up과 top-down 방식이 있는데, bottom-up은 반복문을 통해 처음부터 문제를 풀어나가고, top-down방식은 재귀함수를 ..

이번 주는 그래프 이론과 깊이 우선탐색(dfs), 넓이 우선 탐색(bfs)에 대해서 살펴보았다. 먼저 그래프는 사물이나 개념 간의 연결관계를 수학적 모델로 단순화하여 표현한 것으로 프로그래밍으로 이를 표현하기 위한 방법으로는 대표적으로 인접 행렬과 인접 리스트 방식이 있다. 문제의 조건에 따라 효율적인 방식을 골라 이용하는 것이 중요하다. 인접 행렬은 인접 리스트보다 비교적 dense한 조건 하에 사용하는 것이 더욱 효율적이고 반대로 인접 리스트는 sparse한 조건 하에 사용하는 것이 더욱 효육적이라고 볼 수 있다. 그리고 각각의 방식으로 표현된 그래프는 그 탐색을 위해 dfs와 bfs 방식을 사용할 수 있다. 먼저 dfs(깊이 우선 탐색) 방식은 가지 하나를 길게 탐색에 이용하는 방식으로 이해했다. ..