🔗 문제 링크 1069번: 집으로 은진이는 지금 (X, Y)에 있고, (0, 0)에 있는 집으로 가능한 빨리 가려고 한다. 이동할 수 있는 방법은 다음 두 가지이다. 첫 번째 방법은 걷는것이다. 걸을 때는 1초에 1만큼 움직인다. 두 번째 방법 www.acmicpc.net 💡 문제 풀이 및 해석 점프와 걷기가 있다. 만약, 점프가 걷기보다 느리다면, 굳이 점프할 필요없이 걷기로만 이동하면 된다. 충분히 가까워 진 순간은 "점프 2번으로 갈 수 있는 거리" > "현재 위치에서 목적지까지의 거리" 이다. 2번 지점에서는 2가지 선택지가 있다. 3-1. 조금 돌아서 가는 점프 2번의 거리 (최단 경로가 아닌, ^ 모양으로 위로 조금이동하고 아래로 이동하는 방법) 3-2. 목적지를 점프 경로안에 넣고, 남은 거..
알고리즘 문제 풀이
🔗 문제 링크 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 💡 문제 풀이 및 해석 최소한의 인원을 이동시키면서 줄을 세워야 하는 문제이다. 줄을 세운다 => 숫자를 정렬한다 => 정렬할 때, 최대한 적게 움직여야 한다. 움직이는 인원 = 전체 - 움직이지 않아도 되는 인원 움직이지 않아도 되는 인원 = 이미 줄이 제대로 돼있는 인원 따라서 이미 정렬이 되어있는 인원을 전체에서 빼주면 된다!! 내 위치에서 내 앞에 있는 인원들을 비교하여 나까지 증가하는 부분 수열을 구하면 된다. ⭐️ 정답 코드 및 설명 impor..
🔗 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 문제 풀이 및 해석 직사각형의 크기만큼 모두 더하면 최악의 경우 $$1000\times1000\times250000$$ 이라는 말도안되는 경우의 수가 발생하므로 다른 방법을 생각해야 한다. 여기서 DP 아니면 누적합이 보통은 떠오를 텐데, 솔직히 문제 후기에서 말한듯이 둘 중 하나를 선택하고 생각하는 것은 개인의 능력이 아닐까 싶다. 이 문제는 제목에 써놓은 듯이 누적합 문제이다. 일차원 누적합이 아닌 2차원 누적합이니 다른 방법이 필요한데 아래 만약, (0,0) (2,2) 에 5를 더한다고..
🔗 문제 링크 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 💡 문제 풀이 및 해석 평범한 BFS 문제로 본다면, 모든 지점에서 BFS 알고리즘을 구현하여 실행하면 된다. 적록색약과 아닌 상황을 구분해야 하므로, 아래와 같은 과정을 거쳐야 한다. 3-1. 적록색맹이 아닌 사람에 대해서 BFS로 검사한다. 3-2. 적록색맹인 사람은 R -> G 로 바꿔서 검사한다. ⭐️ 정답 코드 및 설명 import javax.naming.PartialResultException; import java.awt.imag..
🔗 문제 링크 2194번: 유닛 이동시키기 첫째 줄에 다섯 개의 정수 N, M(1 ≤ N, M ≤ 500), A, B(1 ≤ A, B ≤ 10), K(0 ≤ K ≤ 100,000)가 주어진다. 다음 K개의 줄에는 장애물이 설치된 위치(행 번호, 열 번호)가 주어진다. 그 다음 줄에는 시작점의 www.acmicpc.net 💡 문제 풀이 및 해석 "시작점 -> 도착점"의 최소거리를 구해야 한다는 점에서 BFS로 풀어야 한다 생각했다. 단, queue에 들어간 모든 원소가 빠져나가는 것을 1회로 지정해야 한다. 이 때, 움직이는 Unit은 동서남북으로 한칸씩 움직일 수 있는데, 장애물이 설치된 구역이거나 맵의 바깥쪽으로는 이동할 수 없다. 동서남북으로 이동시에 방향에 맞게 유닛이 이동하는 변이 금지구역에 들어..
🔗 문제 링크 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 💡 문제 풀이 및 해석 N의 범위가 100 이하이므로, 1N번 방에서 1N번 방까지 가는 최소값 거리를 모두 구해도 1초안에 해결되는 문제다. 모든 방에서 모든 방까지 가는 최소의 거리를 다익스트라를 통해서 구한다. 이 최솟값들을 모든 방에 더해준다. 가장 값이 작은 방이 모이기 최적화된 방이다. 값이 같은 경우, 번호가 낮은 수가 출력되어야 한다. ⭐️ 정답 코드 및 설명 #include #include #include #include #defin..
🔗 문제 링크 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 💡 문제 풀이 및 해석 회전을 시켜야 하는데, 이는 2^N 이다. N북, 남->서, 동->남, 저장된 북->동 순서로 돌렸다. rotate 하는 함수는 L에 영향을 받는데, 이는 매개 변수 size로 넣어주었다. rotate는 왼쪽 위, 오른쪽 아래 2개의 x,y rotate해야 되는 정사각형의 변을 표현하였다. 그 다음은 녹이는 것과 bfs인데, 굳이 설명해놓지 않겠다. ⭐️ 정답 코드 및 설명 #include #include ..
🔗 문제 링크 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 💡 문제 풀이 및 해석 문제의 조건대로 풀면된다. 단, 사전 작업으로 해야할 일이 있다. 이 나라는 이번 회차(인구 이동 당일)에 인구 이동이 일어났는가 국경선이 열린 이웃한 나라들의 집합은 어떻게 처리할 것인가 인구가 이동하지 않은 것은 어떻게 알 것인가 더 자세한 풀이는 코드의 주석에 있으니 코드의 흐름대로 읽으면 이해할 수 있을 것이다. ⭐️ 정답 코드 및 설명 #include #include #include #define end..
