https://www.acmicpc.net/problem/1911분석이 문제는 물웅덩이들을 최소한의 널빤지로 모두 덮어야 하는 그리디(Greedy) 문제입니다. 널빤지의 길이가 고정되어 있으므로, 앞에서부터 차례대로 덮어나가는 것이 최선입니다.시간복잡도는 물웅덩이의 개수 n이 최대 10,000개이므로, 물웅덩이를 시작 위치 기준으로 정렬하는 데 O(n log n), 그리고 정렬된 웅덩이를 한 번 순회하며 널빤지를 배치하는 데 O(n)이 소요됩니다. 전체 시간복잡도는 O(n log n)으로, 2초의 제한 시간 내에 여유롭습니다.공간복잡도는 웅덩이 정보를 저장하는 데 int 형 O(n)이 필요하며, 8 byte * 10,000 * 2 = 약 160 KB 저장하므로 충분합니다. 알고리즘 로직을 정리하면 다..

https://www.acmicpc.net/problem/15662 분석이 문제는 주어진 조건에 따라 여러 개의 톱니바퀴를 회전시키는 시뮬레이션 문제입니다.시간복잡도는 회전 횟수 k번 동안 최대 t개의 톱니바퀴를 검사하고 회전시켜야 하므로 O(k * t)$입니다. 1,000 * 1,000 = 1,000,000으로 2초라는 시간 제한 내에 충분히 여유롭게 통과 가능합니다.공간복잡도는 톱니바퀴 상태를 저장하는 int 형 2차원 배열 O(t * 8)$입니다. 8 byte * 1,000 * 8은 약 64KB 정도로 매우 여유롭습니다. 알고리즘 로직을 생각해 보면,연쇄 회전 결정:특정 톱니바퀴가 회전할 때, 양옆의 톱니바퀴가 함께 회전할지 여부를 먼저 결정해야 합니다.회전이 실제로 일어나기 전의 상태를 기준으로 ..

https://www.acmicpc.net/problem/17406분석이 문제는 완전탐색이고, 탐색 순서에 따라 결과가 바뀌니 순열 탐색 문제입니다.시간복잡도는 순열생성 후 k 번 회전 수행, n * m 배열을 탐색해야하니 O(k! * (k * (n * m)) 입니다. 3 공간복잡도는 int형 2차원 배열 O(n * m) = 8 byte * 50 * 50 = 약 20 KB 로 여유롭습니다. 알고리즘 로직을 생각해보면, 순열 (Permutation):회전 연산이 k개 주어질 때, 이를 나열하는 순서는 최대 k!가지입니다.배열 복사:각 순열 케이스마다 원본 배열이 변하면 안 되므로, 반드시 배열을 복사하여 시뮬레이션을 진행해야 합니다.배열 회전:주어진 r, c, s 에 대해 가장 바깥쪽 사각형부터 안쪽 사각..

https://www.acmicpc.net/problem/3190분석이 문제는 시뮬레이션을 구현하면 되는 문제입니다. 하지만 뱀의 상태를 Deque 를 사용하여 관리하는게 키 포인트 였습니다.시간 복잡도는 2 공간 복잡도는 2차원 배열 탐색 int형 O(n^2) = 8byte * 101^2 = 약 80,000 뱀의 상태 16byte * 101^2 = 약 160,000 을 더하면 24KB 로 여유롭습니다. 알고리즘을 생각해보면, 뱀의 이동:매 초마다 머리를 다음 칸으로 이동시킵니다.벽이나 자기 자신의 몸에 부딪히면 게임이 종료됩니다.사과가 있다면: 꼬리는 그대로 두고 머리만 추가합니다.사과가 없다면: 머리를 추가하고, 가장 오래된 좌표(꼬리)를 제거합니다.방향 전환:특정 초가 지났을 때 L(왼쪽 90도) ..

https://www.acmicpc.net/problem/12100분석이 문제는 4방향으로 최대 5번의 이동을 하는 시뮬레이션 문제입니다.시간 복잡도는 1 공간 복잡도는 재귀 할때마다 새 보드를 생성하므로, int 형 O(n^2 * 5) = 8byte * 400 * 5 = 16,000 으로 여유롭습니다. 알고리즘을 생각해보면, 방향 탐색 (재귀/백트래킹):상, 하, 좌, 우 4가지 방향으로 5번 이동하는 모든 경로를 재귀 함수로 탐색합니다.각 단계마다 격자 상태를 복사해서 넘겨주어야 원본 데이터가 유지 됩니다.블록 밀기 (Move):한 방향으로 밀 때, "이미 합쳐진 블록은 이번 턴에 다시 합쳐질 수 없다"는 규칙이 가장 중요합니다.예: 2 2 2 2가 한 방향으로 밀리면 8이 아니라 4 4가 되어야 합..

https://www.acmicpc.net/problem/14889분석이 문제는 n 명 중 n / 2 명을 뽑는 문제입니다. 뽑는 것에 순서는 필요가 없으니 조합 문제 입니다.N=20 이라는 작은 입력 크기 덕분에 브루트 포스와 백트래킹으로 가능합니다.시간 복잡도는 4 184,756 * 400 = 7300만 으로 시간 제한에 여유롭습니다.공간 복잡도는 int 형 O(n2) = 8byte * 400 = 3200 byte 으로 여유롭습니다. 풀이 코드package mainimport ( "bufio" "fmt" "math" "os")var ( n int powers [][]int visited []bool res = math.MaxInt32)func main() { in := bufio.NewReader(o..

https://www.acmicpc.net/problem/17144분석이 문제는 미세먼지가 확산되고, 공기청정기가 바람을 일으켜 청소하는 과정을 시뮬레이션 하는 문제입니다. 알고리즘 과정을 생각해보면미세먼지 확산 (spread 함수) 은 모든 칸이 동시에 확산되므로, 원본 배열을 수정하는 것 보단 새로운 배열을 만들어 원본 배열에 반영합니다.청소 (clean 함수) 는 바람이 불어오는 역순으로 탐색해야 합니다.최종 결과를 합산합니다.시간 복잡도는 모든 칸을 순회하고, t 만큼 반복하므로 O(t * r * c) 입니다.6 공간 복잡도는 2차원 배열 2개를 사용하므로 O(r * c) 입니다.풀이 코드package mainimport ( "bufio" "fmt" "os")var ( r, c, t int gr..

https://www.acmicpc.net/problem/1700분석이 문제는 멀티탭 구멍의 개수 n 과 전기 용품의 사용 순서 k 가 주어집니다. 멀티탭에 꽂혀 있는 플러그를 최소한으로 뽑으면서k 개의 용품을 순서대로 사용해야 합니다. 미래의 사용 순서를 미리 알고 있기 때문에 가장 나중에 다시 사용되거나, 앞으로 사용되지 않을 용품을 먼저 뽑는 것이최적의 해를 보장합니다. 알고리즘 실행 과정을 생각해보면,이미 꽂혀 있는 경우, 플러그를 뽑을 필요가 없으므로 continue빈 자리가 있는 경우, 그냥 꽂으면 됩니다.빈 자리가 없는 경우,현재 멀티탭에 꽂힌 용품들 중, 가장 늦게 나타나는 용품을 찾습니다.만약 이후에 다시 사용하지 않는 용품이 있다면 최우선 제거 대상 입니다. (풀이 코드의 인덱스를 최대..

https://www.acmicpc.net/problem/3273분석이 문제는 수열이 주어지고 수열 내에서 서로 다른 자연수 2개를 더했을 때, x 가 되는 쌍을 구해야 합니다.수열의 크기가 1 시간 초과입니다. 그래서 활용한 알고리즘은 투 포인터 입니다.이 알고리즘을 사용하기 위해선 수열이 우선 정렬되어 있어야 합니다. 두 수의 쌍을 찾으면 되기 때문에 수열의 첫 번째와 끝부터 시작하여 서로 더해가면서 포인터를 조절하며 찾으면 됩니다. 그리고 1 시간복잡도는 배열 탐색 O(N), 수열 정렬 O(NlogN) 이므로 O(NlogN) 입니다.공간복잡도는 최대 int 형 10만개이므로 8byte * 10만 = 80만 byte 로 0.8 MB 입니다.풀이 코드package mainimport ( "bufio"..

최소 신장 트리(MST, Minimum Spanning Tree)는 그래프 내의 모든 정점을 연결하는 최소 비용의 간선 집합으로 이루어진 트리를 의미합니다. 즉, 그래프의 모든 노드를 최소 비용으로 연결하는 것입니다.1. MST의 특징모든 정점이 연결되어 있어야 합니다.사이클을 포함해서는 안 됩니다.최소한의 비용으로 구성됩니다.2. MST 알고리즘 종류최소 신장 트리를 구하는 대표적인 알고리즘은 다음과 같습니다.2-1. 크루스칼(Kruskal) 알고리즘시간 복잡도: O(ElogE)간선의 비용을 기준으로 오름차순으로 정렬한 후, 사이클을 형성하지 않도록 최소 비용 간선을 순차적으로 선택합니다.2-2. 프림(Prim) 알고리즘시간 복잡도: O(ElogV)시작 정점에서부터 시작하여 연결된 정점들 중 최소 비용..