QQ의 다이어리

문제 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://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번째 나라의 금은동 개수를 배열에 저장해 둔다. 이 배열과 모든 벡터를 비교하면 된다. 금메달 개수부터 확인해가..

문제 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문을 돌면..

문제 https://www.acmicpc.net/problem/1269 1269번: 대칭 차집합 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어 www.acmicpc.net 풀이 map을 이용하여 현재 들어온 원소 중에서 지금 입력된 원소와 겹치는 것이 있다면 cnt를 증가시킨다. 그렇지 않으면 map에 입력된 원소를 추가한다. 예제가 다 입력된 후에는 cnt에 겹치는 원소의 개수가 들어있게 된다. 그 후, 전체 원소의 개수에서 겹치는 원소의 개수*2 만큼을 빼면 대칭 차집합의 원소의 개수를 구할 수 있다. 즉, (집합 A의 원소의 개수 + 집합 B의 원소..

문제 https://www.acmicpc.net/problem/9613 9613번: GCD 합 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진 www.acmicpc.net 풀이 GCD란 최대공약수로, 유클리드 호제법을 이용하여 구할 수 있다. 두 수를 계속 나누어서 생기는 나머지가 0이 될때까지 계산하는 과정을 계속 반복한다. 코드로 나타내면 아래와 같다. 이 때 a가 최대공약수가 된다. while(b!=0) { n=a%b; a=b; b=n; } 주의할 점은 합이 int 범위를 넘어설 수 있으므로 long으로 지정해줘야 한다. 코드 #i..