갑갑이의 개발세상

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 유니온파인드 응용 문제이다. boolean[] know 배열을 이용하여 진실을 아는 그룹을 체크해주면 된다. 유니온파인드 기초만 탄탄하다면 응용하기 어렵지 않은 문제 import java.io.*; import java.util.*; public class Main { private static int[] parent; private static boolean[] know; public static void..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 시뮬레이션 + BFS 문제이다. BFS에 익숙하다면 시간 단위로 거리가 가장 가까운 물고기를 찾는 것은 쉽게 해결할 수 있을 것이다. 다만 문제에서 한 가지 골치아팠던 점은 거리가 똑같은 물고기가 여러 마리인 경우에 위쪽에 있는>오른쪽에 있는 물고기 순으로 먹어야한다는 것이다. 그래서 해당 시간에서 먹을 수 있는 물고기가 있다면 pq에 담아주었다. // 움직일 수 있으면 일단 큐에 담는다...

https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 효율성의 함정에 빠져서 어떻게 브루트포스로 안풀고 해결하지 고민하다가 오래걸린 문제,,, 그냥 가능한 경로를 일일이 해보면 되는 문제였다 😓 1. 욱제가 상/하/좌/우/대각선4방향/그대로 총 9 방향으로 움직이거나 멈춰있을 수 있습니다. 현재 있는 칸과 움직일 칸 모두에 벽이 있으면 안됩니다. // 현재의 칸(p.i,p.j)에서 9방향으로 돌려가며 ni와 nj를 찾는다. int ni =..

이렇게 연결되있으면 못찾음 // 프림 boolean[] visit = new boolean[n]; double[] minEdge = new double[n]; Arrays.fill(minEdge, Double.MAX_VALUE); int v = 0; // 시작점: 0 visit[0] = true; int cnt = 0; double ans = 0; while (cnt < n - 1) { double dist = Double.MAX_VALUE; int minNode = v; for (int i = 0; i < n; i++) { if (visit[i] || adj[v][i] == 0) continue; // 나와 그 점과의 거리가 지금보다 작아야돼 if (adj[v][i] < dist) { dist = ad..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 시뮬레이션 문제이다. 주어진 순서대로 찹찹 구현하면 된다. 시뮬레이션 치고 생각할게 많아서 좀 복잡했다. CCTV의 최대 개수가 8개이기때문에, CCTV의 모든 방향의 경우의 수를 탐색한다고 하더라도 4^8 = 65만 맵의 크기도 최대 64이기때문에 브루트 포스로 찾아도 시간은 충분하다고 본다. *구현 순서* 1. CCTV의 위치를 찾아서 저장한다. 2. CCTV의 가능한 방향을 계산한..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 간단한 분할정복 문제이다. N이 무조건 2의 거듭제곱 꼴로 주어진다. 문제 이름 쿼드트리 그대로 네모를 사등분하여 생각해주면 된다. 네모의 모든 칸이 1또는 0으로 채워져있으면 압축 가능하기때문에, 이 조건을 넣어서 String값을 return해주면 된다. 비트 시프팅을 이용하여 아주아주 간단한 소스코드로 풀 수 있다. import java.io.*; public class Main ..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 1. 문제 풀이 떠오르는 풀이는 간단합니다. (조를 만들지 못하는 학생을 탈락했다고 표현) 인덱스 순서대로 진행하고, 현재 배열값이 가르키는 학생 번호로 이동해서 조를 짤 수 없으면 탈락된 학생들의 숫자를 더해주고, 하나의 사이클이 만들어졌다면 탈락하는 학생들이 없다는 이야기입니다. 사이클 여부는 맨 처음 학생의 번호와 비교했습니다. boolean[] visit배열을 이용하여 방문한 학생을 중복해서 방..

https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제도 단순하고, 난이도에 비해서 쉽게 푼 것 같다. 풀이 N자리 숫자가 주어졌을 때 가장 큰 수를 만들려면 앞자리 숫자를 가장 크게 만들어야 할 것이다. 그러면 앞에 숫자부터 비교해서 1. 다음자리 숫자가 나보다 큰 경우 && 아직 제거해야할 자릿수가 남은 경우 나를 지우고 다음숫자를 이어붙여준다. (1) 예를 들어 476127과 같은 경우 4 < 7이므로 4를 제거해야 함 (2) 76127 에서는 1 < 2 이므로 1을 제거 (3) 7627 에서는 2= c) break;..

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 개인적으로 분할정복에 약해서 좀 어려웠던 문제이다. 아이디어를 얻어서 문제를 풀었다기보다는, 그림을 그려가며 규칙을 발견해서 이에 맞춘 느낌? 이 문제를 N별로 찬찬히 들여다보면 다음과 같은 규칙을 발견할 수 있음 빨>주>노>초 순으로 1>2>3>4 1. N=1일 때 또한 왼쪽 위 칸을 기준으로 인덱스는 2. N=2일 때 왼쪽 위 영역에서 0,0좌표의 숫자를 기준으로 한다. 3. N=3일..

트라이(Trie)란? 트라이는 문자열을 효율적으로 검색하기 위해 고안된 Search Tree의 일종입니다. 어떠한 알고리즘을 이용하여 정수나 실수 등과 같은 기본 자료형의 변수를 비교할 때에는 각 자료마다 동일한 시간이 걸릴 것이지만, 문자열의 경우 각각의 문자열마다 길이가 다르기 때문에 동일한 알고리즘으로 비교하더라도 같은 시간이 걸린다고 말할 수 없습니다. 최악의 경우 문자열의 길이만큼의 시간이 더 걸리게 될 것입니다. BST를 이용한 검색 (1) 정수 자료형의 경우 한 번의 검색마다 트리의 깊이가 1씩 깊어집니다. 트리의 깊이가 1씩 깊어질 때마다 비교해야 할 자료형은 절반씩 줄어들기 때문에 총 검색의 시간복잡도는 O(logN) 일 것입니다. (2) 문자열의 경우 한 번 검색마다 트리의 깊이가 1씩..