QQ의 다이어리

# DFS (Depth First Search) '깊이 우선 탐색'이라는 이름에서 알 수 있듯이, 최대한 깊숙이 들어가서 확인하고, 돌아가서 또 반복하며 트리나 그래프를 탐색한다. 가장 마지막에 만났던 갈림길의 정점으로 돌아가서 다시 DFS를 진행해야 하므로 후입 선출 구조의 스택을 사용한다. input 사이즈가 너무 크지 않다면 스택뿐만 아니라 재귀 호출로도 구현 가능하다. - 재귀를 이용한 코드 void recur_dfs(int node) { visited[node] = true; for(int next=0; next

문제 https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 풀이 2차원 벡터를 생성해서 입력값들을 저장했다. 2차원 벡터로 문자열과 1차원 정수 벡터를 짝으로 묶었으므로, 아래와 같이 저장된다. v.first v.second[0] v.second[1] v.second[2] 이름 국어 점수 영어 점수 수학 점수 그 후, comp 함수를 생성하여 정렬했는데, comp 함수에는 문제가 요구하는 내용을 바탕으로 정렬하도록 했다. 국어 ..

문제 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 풀이 DLL을 이용하여 풀 수 있는 문제이다. 포인트는, 첫 번째로 현재 커서의 위치를 나타내는 cur 포인터가 연산이 끝나고 제자리를 잘 가리키도록 해야 한다는 것이다. 추가 연산을 한 후에는 새로 생성된 노드를 가리키고, 삭제 연산을 한 후에는 가리키던 노드의 이전 노드를 가리키도록 한다. 왼쪽이나 오른쪽으로 이동하는 연산을 할 때는 연결리스트의 범위를 넘어가지 않도록 한다. 두 번째는 연..

문제 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 풀이 입력으로 주어지는 배열의 원소 개수가 최대 8개이므로, 브루트포스로 하나하나 확인해가며 최댓값을 찾으면 된다. 이때 모든 경우의 수를 찾기 위해 next_permutation 을 사용했다. 입력받은 배열을 오름차순으로 정렬한 후, 계속해서 다음 순열을 찾으면서 원소들의 절댓값을 더한다. 끝날 때까지 반복하고 나면 max 변수에 최댓값이 저장된다. 코드 #include #include #include ..

문제 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 R이 입력되었을 때, 매번 배열을 뒤집으면 시간 초과가 발생할 것이다. R이 입력될 때마다 flag를 설정해서 처리해줬다. 뒤집힌 상황 -> D가 입력됨 -> 뒤에서 노드를 제거 뒤집히지 않은 상황 -> D가 입력됨 -> 앞에서 노드를 제거 즉, 앞 뒤에서 노드를 제거할 수 있어야 하므로 더블리 링크드 리스트를 사용했다. 더블리 링크드 리스트로 구현하면 값을 출력할 때도 맨 뒤 노드부터 prev로 접근하면서 역순으로 출력하거나, head부터 ..

문제 https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 풀이 여러 문자열을 입력받아서 오름차순으로 정렬하고, 각 문자열의 백분율을 옆에 출력하면 된다. 오름차순으로 정렬하고, 입력받는 문자열의 개수를 세야 하므로 map을 이용해줬다. 이 문제에서는 입력받는 문자열의 개수나 입력을 마치는 조건이 없으므로 입력이 없을 때까지 입력을 받아야 하는데, 이때 while(cin>>s) 나 while(getline(cin, s))와 같은 형태를 사..

문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 이전에 게시했던 MST 관련 포스팅을 익혔다면 그냥 해결할 수 있는 문제이다. MST를 구현해서 가중치의 합을 출력하면 된다. ◎ MST를 구현하기 위한 알고리즘에 대한 설명은 -> https://qqs-diary.tistory.com/106 MST (Minimum Spanning Tree) MST란 그래프의 모든 vertex를 최소 edg..

자세한 이론은 이전 글 참고! https://qqs-diary.tistory.com/106 MST (Minimum Spanning Tree) MST란 그래프의 모든 vertex를 최소 edge의 weight로 연결한 그래프이다. 최소 비용으로 모든 도시의 도로를 연결하거나, 통신망을 연결하는 데 응용할 수 있다. Kruskal's Algorithm MST를 찾아내는 알고리 qqs-diary.tistory.com 이론 정리글에서 사용했던 그래프를 이용해서 코드로 구현해보자. 이 그래프를 MST로 만들면 총 가중치는 1+2+3+3+3+4+5 = 21이 된다. 코드 #include #include #include #define SZ 8 using namespace std; int getparent(int cy..

MST란 그래프의 모든 vertex를 최소 edge의 weight로 연결한 그래프이다. 최소 비용으로 모든 도시의 도로를 연결하거나, 통신망을 연결하는 데 응용할 수 있다. Kruskal's Algorithm MST를 찾아내는 알고리즘으로, 가장 작은 weight를 갖는 edge를 추가하면서, 모든 vertex가 연결될 때까지 반복한다. 이때 cycle이 발생하지 않도록 주의한다. 정리하자면, Kruskal algorithm은 1. weight의 오름차순으로 edge를 더해가는데 2. edge의 개수가 vertex-1개가 될 때까지만 반복한다. 3. Cycle이 생기지 않도록 유의하면서 과정을 진행한다. 그렇다면 cycle은 어떻게 찾을까? cycle detection 배열을 이용한다. 연결되었다면 알파..

문제 https://www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 풀이 입력된 배열에서 특정 값을 찾아내는 문제이므로 이분 탐색을 이용해서 풀면 된다. 주의할 점은, 탐색해야 할 배열에서 중복 값이 없다는 조건은 없으므로 중복을 제거해줘야 하고, 테스트 케이스마다 수첩 1의 숫자들을 저장할 벡터 v를 초기화해줘야 한다. 이 과정이 없으면 이전 테스트케이스 뒤에 숫자가 추가된다. 이분 탐색을 코드로 구현해줘도 되고, 중복 제거를 위해 map이나 set을 이용해도 ..