728x90 Algorithm128 16988 Baaaaaaaaaduk2 (Easy) https://www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net (풀이) 이 문제는 빈 칸에 자신의 돌을 2개 두고 상대방의 돌을 최대 몇개 잡을 수 있는지 묻는 문제이다. 자신의 돌을 2개 선택 하는 경우의 수를 먼저 찾아준다. (빈 칸의 갯수) Combination 2 조합을 이용하여 모든 경우의 수를 다 찾아준다. 그리고 해당 각 경우의 수 마다 흰색돌을 DFS 또는 BFS로 순회하여 빈칸이 존재하는지 여부를 파.. 2020. 7. 25. 16985 Maaaaaaaaaze https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net (풀이) 이 문제는 바둑이와 난이도는 같지만, 경우의수가 하나 더 추가되어 구현이 복잡하다. 문제의 요구조건은 5x5x5 3차원 배열의 각 층을 무작위로 선택하여 선택한 층들을 다시 무작위로 회전시켯을때 미로를 탈출할 수 있는 가장 최소거리를 구하는 문제이다. 이 문제를 층을 나누는방식과, 회전시키는 부분을 분리해보면 무작위로 층을 선택하는 경우의 수는 5!이 나온다. 각 층.. 2020. 7. 25. 15686 치킨배달 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net (풀이) 문제의 조건에 치킨집 M의 수는 13개 보다작거나 같다. 폐업 시키지않은 치킨집 수를 최대 M개 고려했을때 치킨 거리가 가장 최소가 될때의 최소값을 찾는문제. 치킨집을 폐업 시키는 제한이 없다. 따라서 1개를 폐업시키든 2개를 폐업시키든 폐업시키지 않든 폐업 시키지 않은경우에도 최소거리를 찾을 수 있다. 도시 치킨 거리를 가장 최소로 하기 위해서 각 치킨집에서 집들과.. 2020. 7. 25. 17136 색종이 붙이기 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크�� www.acmicpc.net 문제 풀이의 접근은 다음과 같이 진행하였다. 각 색종이의 size(1~5)를 5장씩 사용해보며 종이의 1의 갯수가 모두 사라지면 다 붙였다고 판단하고 그때 붙인 색종이의 갯수가 최소값을 구하여 출력하였다. 먼저 문제의 조건에서 1. 종이가 0인 부분이 붙이면 안된다. 2. 덮어쓰기가 불가능하다. 3. 붙이려는 색종이가 10x10의 종이 사이즈를 초과하면 안된다. 조건 1을 검사하기 위.. 2020. 7. 19. 2234 성곽 https://www.acmicpc.net/problem/2234 2234번: 성곽 문제 대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로� www.acmicpc.net (풀이) 1. 성의 방의 갯수는 연결요소가 몇개인지 탐색을 해서 구한다 2. 방의 최대길이는 각 연결요소의 길이중 최대합을 구한다. 3. 하나의 벽을 제거하여 얻을 수 있는 방의 최대 크기는 서로 이웃한 다른 연결요소들의 길이를 합하여 그 중 최대값이 무엇인지 구한다 EX) 서로 이웃한 방(1->5), (1->2), (2->3), (2->5) (3->4) 1과 이웃한 방이 5라면 한번 벽을 허물고 길이를 .. 2020. 7. 17. 17822 원판 돌리기 https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net (풀이) 1. rotate 함수 구현 CCW, CW 방향을 매개변수로 받아서 각각 x배수 번째의 원판을 K번 회전 시킨다. CCW인 경우 (d ==1) -> 배열을 왼쪽으로 k번 회전 시켜주면 된다. CW인 경우는 오른쪽으로 k 번 회전 2.조금 변형된 BFS 인접한 4방향탐색을 통해 원판과 인접한 숫자들이 같으면 소거한다. 하지만, 예를들어 1431 이 한개의 원판에 있을때 원판.. 2020. 7. 15. 14503 로봇 청소기 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net (풀이) 문제의 요구 사항 1. 현재 위치를 청소한다. 2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다. c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, .. 2020. 7. 15. 2468 안전영역 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 � www.acmicpc.net (풀이) 완전탐색 + BFS 문제 1. 문제 요구사항 파악 비가 0 (안옴) ~ 100까지 내리는데 , 그때 침수되지 않는 영역이 최대 몇개인지 구하는 문제. 2. 접근 0~100까지 비를 내려보며 BFS를 탐색하며 연결요소를 구해보았다. 3.더 나은 풀이법. 기둥의 최대높이까지만 비를 내려도 그 이상은 모두 침수되므로 굳이 100까지 내릴 필요가 없다. 효율성을 더 빠르게 할 수 있음. #inclu.. 2020. 7. 13. 9205 맥주 마시면서 걸어가기 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 문제 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발 www.acmicpc.net (풀이) 1. 잘못 접근. 문제에서 순차적으로 접근해야 하는줄 알았다. 2. 순서에 상관없이, 편의점 혹은 도착지점 까지 BFS 탐색을하며 목적지까지 맥주가 다 떨어지지 않는지 풀어야 한다. 3. 맥주가 다 떨어지는 것은 탐색까지 도착지에 다다르지 못하면 도착 하지 못한것으로 판정 4. 다음 위치를 가기 위한 조건 즉, queue에 삽입 되어야 하는 조건 check[i] = (i는 편의점 혹.. 2020. 7. 13. 2644 촌수 계산 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진� www.acmicpc.net (풀이) 문제 접근 1. 인접리스트를 이용한 BFS 2. 기본적인 인접리스트를 이용한 BFS를 구현할 수 있는지 묻는 문제 vector v 로 2차원 연결리스트를 만들고, 해당 노드와 연결된 부분을 입력과 함께 연결시켜줌. 3. 시작점부터 도착지점을 찾을때까지 너비우선탐색, DFS로도 풀리는 문제이다. 4. 못찾으면 -1출력. #include #include #include usi.. 2020. 7. 13. 이전 1 2 3 4 5 ··· 13 다음 728x90
