동환아 공부해야지

문제: https://www.acmicpc.net/problem/2487 조건TimeLimit = 1s섞기 수열 = 1~N까지의 숫자로 이루어진 수열 (1섞기 = 기존 카드 배열에서, '섞기 수열'의 각 원소가 나타내는 위치에 있는 카드를 순서대로 뽑아서 나열하는 것'기존 카드 배열'에서 '섞기'를 진행할 때, 제일 처음 상태로 되돌아오는 '최소' 섞기 횟수는?단, 정답은 최대 20억이다 풀이완전탐색선택지가 따로 없어서 DFS/BFS 상관없이 그냥 탐색하면 됨N이 작아서 단순 탐색이 될 것만 같지만... 탐색 한번에 '섞기 횟수'가 +1 되는 것이므로, 정답이 최대 20억이라 단순 탐색으로는 절대 불가능몇 번 직접 예시를 그려보자-> 각 자리의 숫자마다, 제일 처음 상태로 돌아오기까지 필요한 '섞기 횟..

문제: https://www.acmicpc.net/problem/1726 조건TimeLimit = 2s로봇은 상,하,좌,우로 움직인다명령어는 두 종류가 있다Go k : 현재 방향으로 k만큼 이동한다. k는 1,2,3 중 하나이다Turn dir : dir로 90도만큼 회전시킨다. dir은 left와 right가 있다지도는 0(이동가능)과 1(이동불가능)으로 이루어져있다방향은 1,2,3,4가 각각 동서남북이다 (오른, 왼, 아래, 위)현재 위치와 방향이 주어질 때, 도착 위치와 도착 방향까지 필요한 명령어의 최소 횟수를 출력한다 풀이완전탐색최소/최단이므로 bfs 사용제자리에서 방향회전이 가능하므로 visited를 3차원 배열로 만들어서 사용하자-> visited[r][c][dir]nr, nc, nd 설정을..

문제: https://www.acmicpc.net/problem/17240 조건TimeLimit = 1s역할군 5개, 후보자 n명 (5각 후보자별로 각 역할군 실력이 주어진다 (0~1000)후보자 n명중 5명을 뽑을 때, 역할군 실력의 합 최대를 출력하라 풀이완전탐색최단/최소가 아니니까 dfs(백트래킹)으로 가보자단순 선택/비선택으로 가면 O(2^2만)이므로 다르게 접근5개의 능력치중, 어떤 능력치를 최우선으로 뽑을지 선택하는 방향으로 가보자 (그리디하게)후보자 번호와 능력치를 매핑시켜두고, 각 능력치별로 정렬시켜서 방문처리이렇게하면 O(5! * 정렬비용)이므로 가능 코드import java.io.*;import java.util.*;public class Main { static BufferedRea..

문제: https://www.acmicpc.net/problem/1389 조건TimeLimit = 2s케빈 베이컨의 수가 가장 작은 사람은?유저 수(2 풀이완전탐색모든 각 경로들에 대한 cost를 알아야하므로, 플로이드-워셜 알고리즘을 사용하자 코드import java.io.*;import java.util.*;public class Main { static BufferedReader br; static StringTokenizer st; static StringBuilder sb; static int n; static int m; static int[][] dist; public static void main(String[] args) throws IOException { // input br =..

문제: https://www.acmicpc.net/problem/4485 조건n*n 크기 동굴 (2(0,0)에서 (n-1,n-1)까지 이동할 때의 최소 비용은? 풀이완전탐색dfs를 사용하면 스텍오버플로우 발생전형적인 다익스트라 문제간선을 상,하,좌,우로만 설정하자 코드import java.io.*;import java.util.*;public class Main { static BufferedReader br; static StringTokenizer st; static StringBuilder sb; static int n; static int[][] map; static int[][] dist; static int p = 1; static int[] dr = { -1, 1, 0, 0 }; static..

문제: https://www.acmicpc.net/problem/1987 조건TimeLimit = 2sr*c로 이루어진 board(1(1,1)에서 말이 출발할 때, 방문한 알파벳이 중복되지 않게 이동할 수 있는 최대 칸 수는? (출발점부터 카운트) 풀이완전탐색최악의 경우 r,c가 20이라면, 각 칸당 4번씩 비교해야하므로 O(4^20)이 된다. 따라서 가지치기가 필수이때 알파벳이 중복되지 않게 이동해야하므로, 최대 26번만 움직일 수 있어서 충분히 가능하다최단 이동이 아니므로, 모든 지점을 탐색하기 위해 dfs를 사용하자더 이상 이동이 불가능할 때 max를 갱신해주자방문했던 칸의 알파벳으로는 이동하지 못하므로, 전체 map에 대한 visited는 따로 필요없다(알파벳 방문체크만) 코드import java..

문제: https://www.acmicpc.net/problem/2206 조건TimeLimit = 2sn*m 행렬 맵(1(1,1)에서 (n,m)까지 최단경로로 이동할 때, 벽을 최대 한 개 까지 부술 수 있다. 최단경로의 거리는? 도착 불가능하다면 -1 출력 풀이완전탐색단순 최단경로 탐색이라면 BFS를 사용해서 O(V^2)로 해결 가능하지만 벽을 최대 한 개 부술 수 있으므로, 어떤 벽을 부술지 선택해야하면.. 최대 O(100만C1 * V^2)가 된다. (실제 벽은 100만개까지는 안나오긴 하겠지만..)따라서 최적화가 필수 -> 각 상태별 방문 여부를 저장해두는 'boolean[][][] minMap'을 사용하자minMap은 '두 가지 상태'에서 (r,c)의 방문 여부를 저장해둔다각 상태는 '벽을 부순..

문제: https://www.acmicpc.net/problem/16562 조건TimeLimit = 2s학생 N명(1친구의 친구는 내 친구로 간주한다각 학생들의 친구비가 얼마인지 주어질 때, 모든 학생을 친구로 만들 수 있다면 그 최소비용을, 불가능하다면 "Oh no"를 출력하라 풀이완전탐색최악의 경우, 각 학생에 대해 모든 관계를 조사해봐야하므로 O(N*M) = O(1억) -> 따라서 완탐 가능A와 B학생이 친구라면, 둘중 비용이 더 낮은 친구에게 친구비를 주어야 최소 비용을 달성할 수 있다즉, Greedy하게 가장 친구비가 낮은 학생부터 탐색을 진행해야한다 코드import java.io.*;import java.util.*;public class Main { static BufferedReader b..

문제: https://www.acmicpc.net/problem/15683 조건TimeLimit = 1s사무실은 n*m 크기의 직사각형(1cctv는 5종류가 있고, 각 종류마다 감시할 수 있는 방향이 다르다1번 : 한 방향만2번 : 양쪽 방향3번 : 직각 방향4번 : 세 방향5번 : 모든 방향cctv는 대각선을 감시할 수 없고, 90도만 회전할 수 있다사무실은 빈칸(0), 벽(6), cctv(1~5)로 이루어져 있고, cctv는 벽을 통과해서 감시할 수 없다cctv가 감시할 수 없는 '사각지대'의 최솟값은? 풀이완전탐색cctv가 8대, 모든 cctv 종류를 1, n과 m이 8인 최악의 상황을 가정해보자각 cctv당 4방향을 탐색해봐야 하므로, 시간복잡도는 4*4*4*..*4 = 4**8-> O(4**8..

문제: https://www.acmicpc.net/problem/3109 조건TimeLimit = 1s제일 왼쪽열에서 제일 오른쪽 열까지 동시에 도달하는 경로의 수x인 부분은 지나갈 수 없고, 경로들은 서로 겹칠 수 없다이동할 수 있는 방향은 오른쪽, 오른쪽 대각선 위, 오른쪽 대각선 아래이다1 풀이완전탐색단순 완탐으로는 n이 크기에 TLE가 발생한다 -> 완탐은 O(V^2) = O(10만**2)문제분석 -> 완탐 -> 최적화 순으로 진행하자먼저, 시작열에서 출발 행은 임의로 정할 수 있으므로 모든 행에 대해 탐색을 진행해야한다또한 경로가 겹치면 안되므로 visited를 통해 방문 처리를 해야한다. 이때 동시에 도착하는 경로들을 구해야 하므로, 시작행이 바뀐다해서 visited를 초기화 하면 안된다**..