1. 💎 문제 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 익은 토마토는 1일이 지나면 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 익힌다. 토마토가 모두 익을 때까지 최소 며칠이 걸리는지 출력한다. 모두가 익지 못하는 상황이면 -1을 출력하고 처음부터 모든 토마토가 익어있으면 0을 출력한다. 2. 🤔 어떻게 풀까 저번에 2차원 상자에 있는 유사한 토마토 문제를 풀어봐서 바로 BFS로 풀면되겠구나 하고 풀었다. 추가된 것은 바로 좌표가 3차원이 된 것! 그래서 3..
1. 💎 문제 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 2. 🤔 어떻게 풀까 문제를 잘 읽어보면 달력에 표현되는 수는 x는 M으로 나눈 나머지, y는 N으로 나눈 나머지 값이다. 그러므로 입력으로 주어진 x,y가 몇 번째 해를 아는지 알기 위해서는 결국 아래 두 조건을 만족시키는 최소 공배수가 필요하다. M으로 나누었을 때 나머지가 x이다. N으로 나누었을 때 나머지가 y이다. 최소 공배수를 구하기 위해, x,y를 시작으로 각 M, N을 더해가면서 기존에 나왔던 수인지 비교한다. 비교하기 위해 `HashS..
1. 문제 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 배열을 R번 회전 후 결과를 출력한다. 안쪽에서 회전이 안일어나는 경우는 가로나 세로의 크기 2보다 작을 때이다. 2. 풀이 생각 처음 봤을 때는 저번에 풀었던 달팽이 게임(참고: https://uzinlab.tistory.com/52 ) 문제랑 비슷해서, 전체적인 틀은 네 방향을 나눠서 각각 구현하기로 생각하였고, 구현 문제답게 코드를 짜기전에 열심히 구상을..
1. 문제 20529번: 가장 가까운 세 사람의 심리적 거리 각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다. www.acmicpc.net 세 명의 심리적 거리를 구하고 가장 최솟값을 찾는다. 세명의 심리직 거리 = (A와 B의 심리적 거리) + (B와 C의 심리적 거리) + (C와 A의 심리적 거리) MBTI는 겹칠 수도 있으며, 같은 MBTI간의 심리적 거리는 0이다. 2. 풀이 생각 문제는 가장 최소가 될 수 있는 세명을 어떻게 찾느냐이냐. 세명을 찾기 위해 완전 탐색을 하게 되면 십만X십만X십만으로 10의 15승이 되고, 시간초과가 난다. 그러므로 완전 탐색은 방법이 아니다. 방법은 mbti의 종류가 16개인 것을 이용하는 것이다. 사람의 수가 아무리 많아도 MBTI는 16종류..
1. 💎 문제 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 한 계단, 두 계단 씩만 이동 가능 연속한 3개의 계단 불가 마지막 계단 반드시 밟음 얻을 수 있는 총 점수의 최댓값 구하기 2. 🤔 풀이 생각 이 문제의 핵심은 2계단을 가면 무조건 이동해야 한다는 것이다. 3 계단을 가지 전에 끊어줘야 하므로, 현재 계단에서 선택할 수 있는 경우의 수는 2가지뿐이다. 1. 직전의 계단(n-1)을 밟고 현재 계단을(n)을 밟는다. 2.두 번째 전 계단(n-2)을 밟고 현재 계단(n)을 밟는다. 여기서 1번은 세 계단을 이어서..
1. 💎 문제 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 케빈 베이컨은 모든 사람과 케빈 베이컨 게임을 했을 때 나오는 단계의 합이다. 2. 🤔 어떻게 풀까? 사람마다 한명 씩 모든 사람과의 케빈 값을 구한 후 모두 더해, 가장 낮은 사람을 출력하면 되겠다. 케빈 값을 구하는 방법은 DFS를 사용해서 깊이를 더해주면서 구하면 되겠다. 하지만 틀렸다. DFS를 사용하면 모든 사람과의 관계의 단계를 알 수 있지만..
1. 💎 문제 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net 2. 🤔 어떻게 풀까? 이 문제의 핵심은 주어진 번호들로 얼마나 근사치를 만들 수 있느냐이다. 고민을 많이 했다가 생각난 방법이 그리디였다. 자릿수마다 가장 크기 차이가 안나는 수를 선택하는 작업을 반복한다. 만약 주어진 수가 `54321`이라면 가장 첫 번째 수인 5와 가장 가까운 수를 망가지지 않은 버튼들에서 찾는다. 모두가 망가지지 않았다면 4와 6일 것이다. 하지만 여기서 4와 6중 무엇을 선택해야 할까? 나는 여기서 다음..
1. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 2. 어떻게 풀까 처음에 문제를 잘못 읽어서 횟수가 10번인 줄 알고 어떻게 찾아냐 하나 난감했는데, 1번만 연산하면 되는 것이었다. 잘 알려진 공식 `2b = a + c`를 이용하기로 했다. 2b -a -c를 2로 나줘주면 정답이다. 이때 절대값으로 바꿔줘야 한다.하지만 이렇게만 구현하면 오답처리된다. 왜냐하면 수 세개의 부호가 다르면 결과가 다르기 때문이다. 0일 때는 상관 없지만 세 수중 하나라도 부호가 다르면 나누기 2를 하지 않아야 한다. 왜인지는 잘 모르겠다.. 계산해보니 나누기 2를 안하니깐 딱 맞아 떨어진다. 3. 코드 class Solu..
1. 💎 문제 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 2. 🤔어떻게 풀까 저번에 풀어봤던 문제랑 비슷해서 그때 처럼 `TreeMap`을 써서 풀기로 했다. 조건은 가장 작은 수를 단 번에 꺼낼 수 있어야 한다는 것과 중복값을 포함할 수 있어야 한다는 것이다. 가장 작은 수를 앞에서 꺼내기 위해 정렬을 한 후 넣으면 시간 초과가 난다. TreeSet 또는 TreeMap 삽입과 동시에 정렬을 해서 넣어준다. 이진 탐색으로 구현되어 있다. -정렬 방법 변경- 생성할 때 Compartor..
1. 💎 문제 2. 🤔 어떻게 풀까 `찾을 때까지 재귀`를 돌리면 될 것 같다. 어떤 조건으로 재귀를 돌릴까? 찾아야 되는 숫자를 기준으로 x, y값 범위가 초과되는지, 포함되는지 여부에 따라 `4사분면`으로 나눠서 진행한다. 만약 현재 탐색하는 x의 범위가 찾아야 하는 x값보다 크다면 2, 3 사분면으로 인식하여 더해줄 것 더해주고 y값도 마찬가지로 비교해서 적절한 사분면을 찾자, 범위는 현재 범위의 나누기 2만큼 다시 탐색을 진행! 그리고 원하는 값을 찾으면 재귀를 멈춘다. 문제를 잘못 봐서 원하는 숫자를 기준으로 로직을 생각했다가, 주어지는 것이 행과 열 정보인 것을 보고 기준을 행과 열로 다시 진행했다! 로직은 같다. 3. 🖥️ 코드 여기서의 제4사분면은 지그재그 순서대로 1,2,3,4 분면을 나..