c++11 백준 마법사 상어와 복제 https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 마법사 상어와 복제 문제 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기, 블리자드 마법을 할 수 있다. 오늘은 기존에 배운 물복사버그 마법의 상위 마법인 복제를 배웠고, 4 × 4 크기의 격자에서 연습하려고 한다. (r, c)는 격자의 r행 c열을 의미한다. 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (4, 4)이다.. 2021. 12. 14. 49. SW_Test 연습 백준 어른상어 www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 청소년상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다. N×N 크기의 격자 중 M.. 2021. 2. 28. 위상정렬 위상정렬은 정렬 알고리즘의 종류이다. 위상정렬이란 '방향그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열' 하는 것이다. 쉽게 비유를 하자면 '대학교 커리큘럼'을 예로들수있다. 예를들어 모 대학교의 컴공과는 인공지능과목을 자료구조를 선수강한 뒤에 신청할수있도록 하였다. 이처럼 그래프상에서 선후관계가있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 순서를 계산할수있다. 위상정렬의 알고리즘 순서는 다음과 같다. 1. 진입차수가 0인 노드를 큐에 넣는다. 2. 큐가 빌때 까지 다음의 과정을 반복한다. 1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 여기서 진입 차수란, 특정노드로 들어오는 간선의 개수와 같다. #.. 2021. 2. 26. 신장트리, 크루스칼 알고리즘 신장트리는 그래프에서 자주보이는 유형이다. 신장트리란, 하나의 그래프가있을때 모든 노드를 포함하면서 사이클을 발생 시키지 않는 부분그래프를 뜻한다. 이처럼 신장트리에서 최소 비용으로 만들어진 신장트리를 '최소비용 신장트리' 리고하는데 이 신장트리를 구하는 대표적인 방법은 크루스칼 알고리즘이 있다. 크루스칼 알고리즘의 동작순서는 다음과 같다. 1. 간선데이터의 비용을 크기에 따라 오름 차순 정렬한다. 2. 간선을 하나씩확인하며 사이클을 발생 시키는지 확인한다. 1. 사이클이 발생하지 않는다면 최소비용 신장트리에 포함시킨다. 2. 사이클이 발생하는 경우 포함하지 않는다. 3. 모든 간선에 대하여 2 번의 과정을 반복한다. 다음은 크루스칼 알고리즘의 코드이다. #include #include #include .. 2021. 2. 26. 다익스트라 다익스트라 알고리즘은 그래프에서 여러개의 노드가 있을때, 특정한 노드에서 출발하여 다른 노드로가는 최단 경로를 구하는 알고리즘이다. 다익스트라 동작 방식은 다음과 같다. 1. 출발노드를 설정한다. 2. 최단거리 테이블을 초기화한다. 3. 방문하지 않는 노드중에서 최단거리가 가장 짧은 노드를 선택한다. 4. 해당노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 갱신 5. 위 과정에서 3 4 반복. 다익스트라를 구현하는 방법은 두가지가있는데, 하나는 1차원 리스트를 순차탐색하면서 구현하는 방법이고 두번째는 힙(우선순위큐)를 이용하여 구현하는 방법이다. 첫번째 방법의경우 O(V^2) 의 시간복잡도를 가지지만 두번째는 O(ElogV) 의 시간복잡도를 가진다. 아래는 우선순위큐를 이용하여 다익스트라를 구현한.. 2021. 2. 25. 이진탐색, upper_bound , lower_bound 이진탐색이란 배열의 내부가 정렬되어있어야 사용할수있는 탐색이다. 이진탐색은 시작점, 끝점, 중간점을 반복 이용하여 중간점과 찾고자하는값을 비교하며 데이터를 찾는다. 또한 탐색을 진행할때마다 평균적으로 확인하는 원소가 절반으로 줄어든다. 즉, 빅오 표기법에 따라 O ( logn) 의 복잡도를 가진다. 간단한 이진탐색을 구현하는 방법은 재귀,반복을 이용하는 두가지 방법이 있는데 반복을 이용하는 코드는 다음과 같다. #include #include #include using namespace std; vector list; int binarySearch(vector &list , int left, int right ,int target){ while (left> N >> target; for(int i = 0.. 2021. 2. 25. 이전 1 2 다음
