시뮬레이션

📖 문제 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 💡 풀이 방식 • 구현, 시뮬레이션 필요 자료구조 - 컨베이어 벨트 칸의 내구도 저장용 1차원 int형 배열 (크기 : 2 * N) - 해당 칸에 로봇 존재 여부 저장할 1차원 boolean형 배열 (※ 크기 : N) → true : 로봇 O, false : 로봇 X 내구도가 0인 칸의 개수가 K개 미만인 동안 아래 3단계를 반복한다. 1. 컨베이어 벨트와 로봇 위치를 한 칸 이동한다. // 컨베이어 벨트 이동 int tmp = A[..

📖 문제 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 💡 풀이 방식 • 구현, 시뮬레이션, BFS 필요 자료구조 - 4방 탐색용 dx/dy 배열 - 땅에 붙어있는 클러스터 위치 저장용 큐 (bfs 수행) - 땅에 붙어있는 클러스터 표시할 방문 표시 배열 - 공중에 떠있는 미네랄 위치 저장용 리스트 1. 왼쪽, 오른쪽 번갈아가며 주어진 높이의 미네랄을 파괴한다. private static void solve(int row, int i) { if(i % 2 == 0) { // 왼 > 오 for(int j = 0 ; j < ..

📖 문제 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 💡 풀이 방식 • 구현, 시뮬레이션, BFS 필요 자료구조 - 4방향 탐색용 배열 - 외부 공기와 접촉한 수 저장용 2차원 int형 배열 air (-1: 외부 공기) - 치즈 수 1. 가장자리는 무조건 공기이므로 (0,0)부터 BFS를 수행해 가장자리(-1)를 표시한다. 2. 치즈(=값이 1)인 곳에서 상하좌우 中 외부 공기(=값이 -1) 갯수를 센다. 3. 외부 공기와 2개 이상 접하면 치즈를 녹인다. 4. 치즈 갯수가 0개가 될 때까지 ..

📖 문제 28215번: 대피소 $2$차원 평면의 KOI 마을에 $N$개의 집이 있다. 각 $i$번째 집의 위치는 $(X_i , Y_i)$이다. $i$번째 집과 $j$번째 집 사이의 거리는 $|X_i - X_j | + |Y_i - Y_j |$이다. 즉, 두 집 사이의 거리는 $X$의 차이와 $Y$의 www.acmicpc.net 💡 풀이 방식 #브루트포스 #시뮬레이션 N의 최대 크기가 50이어서 O(N^4)해도 괜찮으므로 브루트포스 가능. 대피소 갯수를 3개로 정하고 코드를 짜는 것이 핵심! 대피소가 1개인 경우는 3개 위치를 모두 동일하게 하고, 2개인 경우는 2개 위치 idx만 동일하게 하면 된다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ..

📖 문제 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 💡 풀이 방식 • 시뮬레이션 1. 집 정보를 입력받으면서, 공기청정기 위치 cleaner도 함께 입력받는다. 2. T초 동안 아래 과정을 반복한다. → 1) 미세먼지 위치와 미세먼지 양을 확인해 큐에 저장한다. (❌ 미세먼지 위치만 저장❌ 나중에 격자에서 해당 칸 값 map[i][j] 받아와서 기존 배열을 바로 수정하게 되면 틀린다.) → 2) 모든 미세먼지가 있는 칸을 돌며 먼지를 확산시킨다. 이 때, 확산될 먼지가 없다면 = 해당 칸의 값이 5보다 ..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 시뮬레이션 1부터 n행까지 돌며 해당 행의 (k, k +m)열의 위치의 값이 모두 0이라면, 다음 행에 넣도록 넘어간다. 모두 0이 아니라면, 해당 행의 바로 위쪽 행에 블록을 넣는다. 💥 유의사항 마지막 행(n)까지 왔을 때는, 마지막 행의 (k, k+m) 위치의 값이 모두 0이라면 마지막 열에 블록을 두고, 0이 아니라면 바로 윗 행에 블록을 두도록 한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • 시뮬레이션 1. 정사각형인 부분을 찾아 정사각형인 부분이 존재한다면, 집합(Set)에 해당 좌표들을 저장한다. (findSquares()) 2. 정사각형 위치 집합을 돌며 해당 위치의 블록들을 제거한다. (= '.'으로 변경) 3. 중력을 적용시킨다. private static void dropBlocks() { // 1. 2차원 임시 배열 생성해 모두 빈 칸(.)으로 초기화하기 char[][] tmpGrid = new char[m][n]; for(int i = 0 ; i < m ;..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 시뮬레이션 + BFS ① 한 칸 전진해 점수 갱신 → ② 주사위 굴리고 방향 조정 1. 현재 방향으로 한 칸 전진하여 좌표 값을 갱신하고, 해당 칸에서 bfs를 통해 현재 칸에서 얻을 수 있는 점수를 구해 합을 갱신한다. (한 칸 전진 시 격자판을 벗어난 경우, 반대 방향으로 되도록 조정해준다.) 2. 주사위가 놓인 상태를 조정한다. 이를 위해 현재 이동 방향에 맞춰 주사위를 굴리며 보이는 면 배열 dice를 갱신한다. 그리고 나서 주사위 바닥면의 값과 현재 칸의 값을 비교해 ..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • 시뮬레이션 최대 2*N번 동안 1,2번을 진행한다. ① 구슬들을 구슬 리스트에 저장하고 전부 한 번씩 움직이기 (moveAll()) - 벽이 있으면 방향을 전환하고, 벽이 없으면 한 칸 전진하게 한다. private static Marble moveMarble(Marble mm) { int nx = mm.x + dx[mm.d]; int ny = mm.y + dy[mm.d]; if(inRange(nx, ny)) // 벽이 없는 경우, 한 칸 전진 return new Marble(..