IT 꿈나무 참다랑어

https://www.acmicpc.net/problem/6884 6884번: 소수 부분 수열 각 테스트 케이스마다 가장 짧은 소수 부분 수열의 길이가 x라면 "Shortest primed subsequence is length x:"를 출력하고, 그 수열 공백으로 구분해 출력한다. 가장 짧은 소수 부분 수열이 여러 가지면, 먼저 www.acmicpc.net 문제 풀면서 연속 부분 수열이라는걸 놓치고 있어서 조합으로 풀어야하는건가 하고 계속 고민했는데, 연속 부분 수열이여서 삽질을.. 문제를 풀면서 수를 계속 소수인지 아닌지 확인해봐야할 것 같아서 모든 원소를 다 더한 값까지 에라토스테네스의 체를 미리 만들고 부분합을 길이를 기준으로 탐색을 하려고 했다. (지금 생각해보니 범위가 그렇게 넓지 않고, 소수..

https://www.acmicpc.net/problem/11140 11140번: LOL 당신 친구 지민이는 지금 할 일이 없다. 그리고 매우 심심하다. 그래서 쓸데없는 짓으로 시간을 때우려고 한다. 그래서 단어 하나가 주어질 때 단어에 'lol'이 들어가도록 글자를 추가하거나 변경 www.acmicpc.net 위의 문제를 풀기 위해서 일정 패턴을 인식하고 그에 따른 처리 횟수를 출력하는 방법을 생각했다. 여기서 케이스는 문자열에 1) "lol" 자체가 포함되어 있는 경우 -> 추가적으로 처리할 필요 없음(0) 2) "lo", "ol", "ll", "l_l"과 같이 하나만 추가해서 "lol"을 만들 수 있는 경우 -> 추가 또는 수정만 진행(1) 3) "l"또는 "o"가 포함되어 있는 경우 -> 2개 추..

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..