Programming
-
너비우선탐색(BFS)Programming/알고리즘 2020. 11. 7. 16:03
너비우선탐색(Breadth first search, BFS)은 탐색을 할때 너비를 우선으로 탐색하는 기법이다. BFS는 '맹목적인 탐색 기법'에 속하며 '최단 경로'를 보장해줍니다. 또한, BFS는 자료구조인 Queue(FIFO)에 기반하여 구현할 수 있습니다. 코드는 아래와 같은 그래프를 기준으로 작성하였다. #include #include #include using namespace std; int n; int flag[8]; vector bfs[8]; queue q; void bfs_search(int start) { q.push(start); flag[start] = true; while (!q.empty()) { int x = q.front(); printf("%d ", x); q.pop(); ..
-
[c++] 백준 10989번 - 수 정렬하기 3Programming/알고리즘 문제 2020. 11. 7. 01:49
# 백준 10989번 URL 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 숫자를 N개 만큼 입력 받는다. (각 숫자는 10000보다 작거나 같은 자연수) 이 문제는 속도가 O(nlog)이 나오는 퀵 정렬, 병합정렬, 힙정렬을 사용하게 되면 메모리 초과가 나오게 된다. 입력값이 10000보다 작다는 조건이 있으므로 여기서는 계수정렬을 사용한다. (계수정렬은 O(n)의 시간복잡도를 가진다) 또한 c++의 입력, 출력 방식인 cout, cin을 사용하게 되면 시간초과가 일어나므로 여기서는 printf()와 scanf()를 사용하였..
-
[c++] 백준 1431번 - 시리얼 번호Programming/알고리즘 문제 2020. 11. 7. 00:59
# 백준 1431번 URL 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루 www.acmicpc.net 문자열의 수 N을 먼저 입력하고, N만큼 문자열을 입력한다. 1. 길이가 짧은 것 2. 길이가 같다면, 각 자리의 합이 작은것(숫자만 더할 것) 3. 각 자리의 합 또한 같다면 사전 순으로.. 위의 세가지 조건을 만족시켜 c++ STL의 sort를 사용하여 정렬한다. sort의 세번째 인자에는 compare 함수가 들어가며, compare 외에도 각 자리의 숫자의 합을 반환하는 integer_sum이라는 함수를 따로 구현하였다..
-
[c++] 백준 1181번 - 단어 정렬Programming/알고리즘 문제 2020. 11. 7. 00:24
# 백준 1181번 URL 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 1. 길이가 짧은 것 2. 길이가 같을 경우 사전 순으로 입력할 문자열의 수 N을 먼저 입력하고, N가지의 문자열을 입력한다. 그리고 각 N개의 문자열을 위의 두 가지 조건을 만족시켜 출력하는 문제였다. 문제 풀이는 간단하다. C++ STL에서 지원하는 sort를 사용하는 대신 세번째 인수로 bool 형식의 compare라는 함수를 사용하면 된다. compare라는 함수는 길이가 string.length() 함수를 사용하여 길이가 ..