백준 사이트 코딩 문제 (23) 썸네일형 리스트형 백준 17142번: 연구소 3 (C++) 문제 링크 : www.acmicpc.net/problem/17142 1. 바이러스가 있는 지점들을 모두 vector에 넣어주고 dfs로 m개의 모든 조합을 선택한다. 2. m개의 바이러스를 선택했으면 spread_bfs로 바이러스를 퍼뜨려준다. 3. 바이러스를 퍼뜨리며 시간을 위치에 기록한다. 4. 이차원 배열에 0이 존재하면 스킵, 다 퍼졌으면 최대시간을 반환한다. 5. 2,3,4를 반복하며 최소시간을 구한다. 바이러스가 퍼진 시간을 구할 때,,바이러스가 빈 공간에만 모두 퍼진시간을 구하는 것이다. 즉 아직 비활성 상태의 바이러스에 더욱 퍼질 수 있어도 이미 빈공간에 다 퍼졌으면 그것이 최소시간이다. #include #include #include using namespace std; int n; in.. 백준 17140번: 이차원 배열과 연산 (C++) 문제 링크 : www.acmicpc.net/problem/17143 구현, 시뮬레이션 문제이다. 1. 행이 열보다 크면 R 연산으로 모든 행마다 벡터로 저장을 해서 sorting함수로 넘겨준다. 열이 행보다 크면 C 연산으로 모든 열마다 벡터로 저장을 해서 sorting 함수로 넘겨준다. 2. sorting 함수에서 sorting을 진행해준다. 2-1. 벡터를 탐색하며 num_count배열에서 해당 숫자의 index의 값을 증가시켜줌(숫자 개수 구하는 거임) 2-2 num_count를 탐색하며 벡터에 (숫자와 개수를) 쌍으로 넣어준다. 2-3 넣으준 벡터를 sort 라이브러리로 문제 조건대로 정렬시켜줌 3. sorting으로 정렬이 되면 그 뒤의 값들은 0으로 채워준다, row와 column 사이즈 갱신.. 백준 7569번: 토마토 (C++) 문제 링크 : www.acmicpc.net/problem/7569 배열을 전부 탐색해나가며 토마토를 익게 하면 당연히 시간초과가 난다. 이 문제는 bfs로 간단히 해결할 수 있다. bfs 알고리즘 : wlshddlek.tistory.com/8?category=883327 1. bfs로 토마토를 익게하며 제일 늦게까지 탐색되는 토마토가 몇일만에 탐색되었는지 구한다. 2. 토마토다 다익었으면 제일 늦게 익은 토마토 day를 반환, 안익은게 있으면 -1반환 *bfs로 탐색을 할 때 queue안의 각 점에서 모두 탐색을 한다는 것을 이용한다 -> 시작점을 여러개 넣어도 각 시작점에서 모두 탐색해 나감. #include #include using namespace std; class ins { public: in.. 백준 1766번: 문제집 (C++) 문제 링크 : www.acmicpc.net/problem/1766 위상정렬 문제이다. 위상정렬 알고리즘 : wlshddlek.tistory.com/39?category=887828 위상정렬을 이용해야 한다. 위상정렬을 이용할 때 일반 큐가 아니라 우선순위 큐를 사용하면 실시간으로 탐색할 수 있는 것 중에 작은거 부터 탐색할 수 있다. #include #include #include using namespace std; int n, m; vector a[32002]; int indegree[32002]; void topology() //우선순위큐를 이용한 위상 정렬 { priority_queue pq; //실시간으로 선택할 수 있는 것 중 가장 작은거 선택 위함 for (int i = 1; i > m; f.. 백준 1005번: ACM Craft (C++) 문제 링크 : www.acmicpc.net/problem/1005 위상정렬과 dp를 이용한 문제이다. 위상정렬 알고리즘 : wlshddlek.tistory.com/39?category=887828 1. 위상정렬 알고리즘으로 순서대로 건물을 짓는다. 1-1. 건물을 탐색할 때 마다 더 오래 걸리는 시간으로 갱신해준다. #include #include #include using namespace std; int time[1002]; vector a[1002]; int indegree[1002];// int d[1002];// int n,w; void topology() { queue q; for (int i = 1; i > test; for (int t = 0; t < test; t++) { int k; c.. 백준 2776번: 암기왕 (C++) 문제 링크 : www.acmicpc.net/problem/2776 문제 자체는 간단한 문제이지만 조금 문제점이 있다. nlogn 복잡도로만 풀면 되는 문제이기에 set을 이용하는 방식과 이분탐색을 이용하는 방식 둘다 통과해야하지만 set으로 풀면 통과가 되지 않는다.(set 자체가 느리기 때문) 문제를 읽어보면 정수의 개수만 1000000개이다. 이것을 그냥 배열에 넣어서 순차 탐색으로 수를 찾는다면 1000000*1000000수준의 복잡도가 나온다. 그러므로 방법은 set을 이용하는 방법과, 이분 탐색을 이용하는 방법이 있다. -set을 이용하는경우 -> 균형 이진 트리 구조임으로 해당 값을 찾는데 logn수준의 복잡도이다. -이분탐색을 이용하는 경우 -> 역시 분할 정복임으로 logn수준의 복잡도이다.. 백준 17143번: 낚시왕 (C++) 문제 링크 : www.acmicpc.net/problem/17143 시뮬레이션, 구현 문제이다. 1. 오른쪽으로 한 칸 이동한다. 2. 물고기를 잡는다. -물고기를 잡을때는 해당 열에서 밑으로 내려가면서 탐색을 하다가 상어를 만나면 지도에서 제거하고 sum에 더한다. 3. 1초동안 물고기들을 움직이게 한다. - 지도를 탐색하면서 상어가 있으면 상어들을 움직이게 해준다. 움직인 상어들을 tmp임시지도에 저장한다. - 임시 지도를 현실 지도로 복사한다. (현실 지도를 순차탐색 하고 있기 때문에 이미 움직인 상어를 선택하지 않기 위해 임시지도 사용) 4. 1,2,3번을 n번 반복한다. (시간복잡도) 생각없이 그냥 속력1마다 이동하는 식으로 구현을 하면 시간초과가 나게 된다. 그 이유는 상어의 s속력의 범위가 .. 백준 1541번: 잃어버린 괄호 (C++) 문제 링크 : https://www.acmicpc.net/problem/1541 너무 간단한 문자열 문제이다. 1. 수를 최소로 만드려면 '-'로 최대한 많은 수를 묶어야 한다는 것을 알 수 있다. 2. '-'가 나오기 전까지는 '-'로 묶을 수가 없으니 당연히 더하는 방법밖에는 없다. 결국 '-'가 나오기 전까지는 모두 더해준 다. 3. '-'나온 후에는 모두 빼면 된다는 것을 쉽게 알 수 있다. '-'가 한번이라도 나온 후에는 모두 음수로 만들 수 있다. ex) 1+2-3+4+5+6+7 -> 1+2-(3+4+5+6+7) ex) 1+2-3+4+5-6+7 -> 1+2-(3+4+5)-(6+7) #include #include using namespace std; int main() { ios_base::s.. 백준 9012번: 괄호 (C++) 문제 링크 : https://www.acmicpc.net/problem/9012 간단한 stack문제다. 열린 괄호면 stack에 넣고 닫힌 괄호면 미리넣었던 열린괄호를 빼버린다.(쌍을 하나씩 제거하는 방식) 쌍이 서로 다 맞아서 모두 삭제가 되면 vps이다. - 닫힌 괄호가 나왔는데 스택이 비어있으면 vps가 아니다. (닫힌 괄호의 쌍이 없음.) - 닫힌 괄호가 나왔는데 스택 top이 열린 괄호가 아니라면 vps가 아니다. (마찬가지) - 쌍들을 모두 삭제 해주었는데 스택에 남아있는 괄호가 있다면 역시 vps가 아니다. #include #include #include using namespace std; bool is_vps(string str) { stack s; for (int i = 0; i < .. 백준 16236번: 아기 상어 (C++) 문제 링크 : https://www.acmicpc.net/problem/16236 bfs문제입니다. bfs로 먹을 수 있는 먹이를 계속 찾습니다. bfs가 끝날때 마다 먹이를 찾는데 걸리는 시간을 계속 더해줍니다. 만약 먹을 수 있는 먹이가 더이상 없다면 종료시켜줍니다. - 최단 거리의 먹이들 중 가장 위쪽에서 왼쪽인 먹이를 찾기위해 일단 최단 거리의 먹이를 전부 저장해야함 -> 처음 먹이를 찾을때의 거리(최단 거리)를 저장한 후 거리가 더 커지기 전까지의 먹이를 전부 저장한다. (bfs는 가까운 것부터 탐색하므로 거리가 같은 부분끼리 뭉쳐서 queue에 저장된다.) - 상어 정보를 저장하는 class (저장해야 하는 속성이 3개 이상이라 class를 정의함) - 같은 거리의 먹이들을 임시저장하기위한 v.. 이전 1 2 3 다음
