전체 글

📖 문제 1455번: 뒤집기 II 세준이는 동전 뒤집기를 하려고 한다. 세준이는 동전을 N×M개 가지고 있다. 동전은 세로로 N개, 가로로 M개 크기의 직사각형에 차곡차곡 놓여져 있다. 동전의 앞면을 0이라고 하고 뒷면을 1이라고 www.acmicpc.net 💡 풀이 방식 • 그리디 (i,j) 위치에서 뒤집는 경우, 해당 칸의 왼쪽 칸과 위쪽 칸이 뒤집힌다 그러므로 오른쪽 아래 점부터 위로 올라가면서 1을 발견할 때마다 뒤집는다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 import java.util.*..

📖 문제 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이 www.acmicpc.net 💡 풀이 방식 • BFS . 모래성이 없는 노드를 중심으로 생각한다! 모래성이 없는 노드의 주변 8방향 노드 中 모래성이 있는 노드의 튼튼함을 하나 깎는다. 그러다 보면 결국 가운데 모래성이 없어지게 되는데, 이 때는 그 위치를 노드에 추가해주면 된다. 💥 유의사항 이미 한 번 확인한 모래성이 없는 노드는 다시 확인할 필요가 없기 때문에 새롭게 모래성이 없어진 노드만 탐색한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 1..

📖 문제 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 💡 풀이 방식 • BFS 필요 자료구조 - 로봇 객체 (행, 열, 방향, 명령 횟수) - 3차원 boolean형 방문 표시 배열 : [행][열][방향] ⭐ - dx/dy 배열 동서남북 배열 1. 격자를 입력받는다. 2. 시작점 위치,방향과 도착점 위치,방향을 입력받는다. String[] s1 = br.readLine().split(" "); start = new Robot(Integer.parseInt(s1[0]) -1, Integer.parseInt(s1[1])..

📖 문제 5547번: 일루미네이션 첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는 www.acmicpc.net 💡 풀이 방식 • BFS 외벽과 닿는 모든 면을 정육각형으로 돌리기 위해 격자 판 숫자를 저장할 map 배열과, 벽 개수를 저장할 2차원 배열 result의 크기는 [행+2][열+2]로 설정한다. map = new int[H+2][W+2]; // 외벽과 닿는 모든 면을 정육각형으로 돌리기 위해 +2 result = new int[H+2][W+2]; // 벽 개수 저장 리스트 visited = new boolean[H+2][..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • 문자열 (브루트포스) 1. #이 붙은 부분을 다른 문자로 치환한다. m = m.replace("C#", "c") .replace("D#", "d") .replace("F#", "f") .replace("G#", "g") .replace("A#", "a") .replace("B#", "b"); 2. musicinfos 배열을 돌며 악보와 재생시간을 구한다. 1) #이 붙은 부분을 또 1과 같이 다른 문자로 대체한다. String[] info = music.split(","); int ..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • 소수/약수 (에라토스테네스의 체) begin부터 end까지의 범위 내에 있는 숫자들 중 해당 수의 가장 큰 약수를 블록에 적는다. 단, 블록에 적는 숫자는 10,000,000 보다 작거나 같아야 한다! 또, 숫자가 1인 경우만 블록에 0을 두는 예외처리가 필요하다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 import jav..

📖 문제 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 💡 풀이 방식 • BFS 검 존재 여부와 함께 방문 표시 나타내는 3차원 배열 visited[x][y][2] → visited[x][y][0] : 검 없고, 방문했음 → visited[x][y][1] : 검 있고, 방문했음 (0,0)부터 (N-1, M-1)까지 BFS 탐색을 수행한다.큐에는 (현재 행 위치, 열 위치, 그람(검) 유무, 이동 시간) 4가지 값을 들고 다닌다. Queue q = new ArrayDeque(); q.add(ne..

📖 문제 14716번: 현수막 혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라. www.acmicpc.net 💡 풀이 방식 • BFS 1. 격자의 모든 칸을 입력받는다. 2. 격자의 모든 점을 돌면서, 방문한 적 없는 글자(1)인 부분에서 BFS를 수행하고, 그 수행 횟수를 구한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 import java.util.*; import j..

📖 문제 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 💡 풀이 방식 • DP dp[ i ][ j ] = k ⇒ 1~i번째 집까지 칠하고 i번째 집은 j색으로 칠했을 때의 최소 비용은 k 1. 첫 집에 칠할 색 k를 정한다. 그러고 나면 나머지 색으로는 첫 집을 칠할 수 없으므로 나머지 칸들은 최댓값으로 설정한다. (0: 빨강 / 1: 초록 / 2: 파랑) → dp[1][0] : 첫 집을 빨간색으로 칠함. 나머지 dp[1][1] = dp[1][2] = INF → dp[1][1] :..