QQ의 다이어리

자세한 이론은 이전 글 참고! 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을 이용해도 ..

문제 https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net 풀이 벡터의 배열을 만들어서 각 나라별로 메달 수를 저장했다. 처음에는 각 메달에 가중치를 곱해서 구하려고 했는데 그렇게 되면 금메달을 하나도 못 받아도 동메달을 많이 받으면 등수가 높아지므로 문제에 맞지 않다. 따라서 금은동 순서대로 벡터에 저장하고, 미리 k번째 나라의 금은동 개수를 배열에 저장해 둔다. 이 배열과 모든 벡터를 비교하면 된다. 금메달 개수부터 확인해가..

map은 검색, 삽입, 삭제가 O(logn)인 레드블랙트리로 구현되어 있다. key 값과 value 값을 가지며, 중복된 값은 제거되고 오름차순으로 정렬된다. c++에서 사용시, #include 을 해줘야 하며, map 헤더파일을 추가하면 중복이 허용되는 mulitmap도 사용할 수 있다. - 선언 map m; //key 값의 자료형은 string, value 값의 자료형은 int 기본적으로 key 값인 string 데이터가 오름차순으로 정렬되어 값이 들어가지만, 내림차순으로 정렬하고 싶다면 map m; (하지만 greater라고 한다고 해서 key 값이 아닌 value 값으로 정렬할 수는 없다.) - 데이터 삽입 m.insert({"abc",1}); - find map에 특정 값이 존재하는지 확인 후,..

문제 https://www.acmicpc.net/problem/1244 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 풀이 정답 비율이 낮아서 지레 겁먹었는데 그냥 차근차근 풀면 되는 문제이다. 정답 비율이 낮은 것은 출력 조건까지 읽지 않은 사람이 많아서 인 것 같다.. 한 줄에 20개만 출력해야 한다는 조건이 있어서 그 조건도 출력할 때 고려해줘야 한다. 대단한 알고리즘이 필요한 문제는 아니고 그냥 1이 입력되면(남학생이면) 뒤에 입력받은 수의 배수들을 돌면서 값을 바꿔주고, 2가 입력되면(여학생이..

문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 최단 거리를 구해야 하므로 BFS를 이용한다. BFS는 시작 노드에서 가까운 노드를 먼저 방문하기 때문에 BFS로 탐색하다가 먼저 찾아지는 답이 최단거리가 되기 때문이다. 코드 #include #include using namespace std; int n,m; bool visited[100][100]; //방문여부 int map[100][100]; //미로 int cnt[100][100]; //경로 세기 int dx..

문제 https://www.acmicpc.net/problem/4963 백준에서 그래프 탐색 알고리즘 문제를 찾아보면 같은 방법으로 풀 수 있는 유사한 문제가 많다.(2667, 1012..) 풀이 DFS를 이용하여 풀 수 있는 문제이다. 유의할 점은 상하좌우뿐만 아니라 대각선으로 연결된 것까지 인접했다고 보므로, 상하좌우, 4방향의 대각선까지 8방향을 전부 탐색해야 한다. 따라서 배열 dx 와 dy를 선언하여 각 좌표에 더해줌으로써 8방향을 전부 확인할 수 있다. 이때 탐색하려는 좌표가 map의 범위를 넘어가지 않는지를 확인해줘야 한다. 배열을 돌다가 방문하지 않았고, map의 값이 1인 좌표를 만나면 dfs를 수행한다. 이 좌표에서부터 DFS를 수행하고 함수가 종료되면 인접한 좌표를 다 탐색했다는 것이..

문제 https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 풀이 A = 119, B = 11914332인 경우와 같이 A 전화번호가 B 전화번호의 앞부분과 같다면 A는 B의 접두어이다. 전화번호 목록이 주어졌을 때, 접두어가 있다면 false, 없다면 true를 리턴하면 된다. 먼저 입력된 전화번호 목록을 정렬한다. 이렇게 하면 인접한 전화번호만 확인하면 접두어가 사용되었는지를 확인할 수 있다. for문을 돌면..

개념 우선순위 큐란 우선순위가 높은 데이터를 먼저 꺼내는 자료구조이다. 우선순위 큐는 보통 힙으로 구현한다. 힙은 Max heap, Min heap이 있는데, Max heap은 부모노드가 자식노드보다 큰 힙이고, Min heap은 부모노드가 자식노드보다 작은 힙이다. 따라서 오름차순으로 정렬할 경우에는 Min heap을, 내림차순으로 정렬할 경우에는 Max heap을 사용한다. c++에서는 헤더파일을 이용하여 우선순위 큐를 간단하게 구현할 수 있다. 구현 (queue 헤더파일 사용 x) - heap에 데이터 추가 void addToHeap(int v, int last) { int cur = last +1; int parent = cur/2; arr[cur] = v; while(1) { if(arr[par..