갑갑이의 개발세상

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 =..

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일..

https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 트라이를 활용하여 풀 수 있다. 트라이에 삽입할 때 비교해주면 쉽게 풀 수 있음 트라이에 삽입할 때 1. 삽입 중간에 end node를 만날 경우 예를 들어 911 91111 순으로 삽입한다고 하면 91111을 삽입할 때 91111에서 이전에 삽입한 911의 end node를 만날 것이다. 이 경우 일관성 없음: false를 return해준다. for (int i = 0; ..

https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 풀이는 간단하다. 과목들간의 관계를 방향 그래프로 생각, 정보는 인접 리스트에 담아준다. 과목 그래프의 방향은 그림의 반대방향으로 담아줘야지 나의 선수과목에 뭐가 있는지 쉽게 검색이 가능하다. 선수과목이 없는 경우: 1학기에 바로 수강이 가능 선수과목이 있는 경우 인접 리스트를 통해서 해당 과목의 선수과목들이 뭐가 있는지 판단하고, 선수과목 중 가장 큰 것의 학기에 +1 *시간복잡도 선수과목 정보를 입력받을 때 조건이 1≤A