코테/백준

📖 문제 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net 💡 풀이 방식 • BFS + 정렬 1. ArrayList 배열을 만들어 양방향 그래프를 만든다. 2. ArrayList 배열의 각 ArrayList를 오름차순 정렬한다. 3. BFS를 하면서 방문하지 않은 노드를 방문 처리하고 순서를 기록한다. 4. 1~M까지 순서대로 정점들의 방문한 순서 출력 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1..

📖 문제 16719번: ZOAC 2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로 www.acmicpc.net 💡 풀이 방식 • 재귀 재귀 메소드 zoac에서 (처음 시작 부분, 끝나는 부분)을 인자로 받는다. 그리고 시작하는 부분과 끝나는 부분 사이에 있는 글자들 중에서 사전식 정렬했을 때 가장 앞에 오는 글자를 방문처리한다. 그리고 방문한 적 있는 idx들을 출력한다. 아까 발견한 idx에서 +1한 위치와 끝나는 문자열 위치를 넘기며 메소드를 호출한다. (재귀) 이어서 시작하는 문자열 위치와 idx에서 -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 💡 풀이 방식 • 구현 행과 열 중 더 작은 값 / 2한 길이까지 대각선의 값을 이용해 회전 시작점을 잡는다. (i, i). 한 겹씩 회전 (i,i)를 시작점으로 잡고, 마지막 값은 빠뜨릴 수 있으므로 미리 변수로 따로 저장해둔다. int lastVal = map[i][i]; 현재 회전 방향이 4보다 작다면 (= 회전 방향을 한 바퀴 돌지 않았다면) 이동시키도록..

📖 문제 15787번: 기차가 어둠을 헤치고 은하수를 입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. www.acmicpc.net 💡 풀이 방식 • 구현 & 비트마스킹 (비트마스킹 안 쓰고 풀었다.) 사용 자료구조 - 2차원 int형 배열 [기차 수 N][기차 좌석 수 20] - 열차 상태를 String형으로 받아 저장할 Set (중복 제거) 1. 입력받은 숫자에 따라 명령을 수행한다. - 숫자가 1이면, 해당 칸을 1로 만들어 사람을 태운다. - 숫자가 2면, 해당 칸을 0으로 만들어 사람을 하차시킨다. - 숫자가 3이면, 모두 한 칸씩 뒤로 이동시키고 맨 뒷사람은 하..

📖 문제  16637번: 괄호 추가하기첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가www.acmicpc.net 💡  풀이 방식• DFS + 백트래킹1. 이전 연산 결과 순차적으로 계산2. 이전 연산 결과 오른쪽의 2개의 값을 괄호로 처리해 계산하고, 이전 연산 결과와 합침 DFS 통해 맨 뒤에서부터 괄호를 묶을 수 있는 경우 묶으면서 연속적으로 계산연산자 인덱스 기준 접근 - 숫자 리스트와 연산자 리스트를 따로 두어야 한다.  🔺 코드12345678910111213141516171819202122232425262728293031323334353..

🔺 문제 20207번: 달력 수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다. 여름이 거의 끝나가자 장 www.acmicpc.net 🧩 해결 아이디어 • 구현 구간을 입력받고, 해당 시작점부터 끝점까지 구간을 색칠한다. → 카운트 배열 사용 카운트 배열을 돌면서 해당 칸의 값이 0이 아니라면 너비 + 1하고 높이는 최대 높이와 비교해 더 큰 값으로 갱신한다. / 해당 칸의 값이 0이라면, 여태까지 구한 너비와 최대 높이를 구해 넓이 값에 누적해 저장하고, 너비와 최대 높이는 0으로 초기화한다. ⭐ 마지막 구간 처리를 위해 마지막에 넓이들의 합에 너비 * 최대 높이 구한 값을 더해줘야 한다!! 💥 ..

🔺 문제 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 🧩 해결 아이디어 • 구현 & 시뮬레이션 1. 현재 칸의 주변 4칸 中 청소 안 된 빈 칸이 있는 경우, 반시계로 90도 회전하면서 주변을 청소할 수 있는지 확인한다. - 청소 안 된 곳이 있으면, cnt + 1하고 현재 좌표에서 dfs를 수행한다. for(int i = 0 ; i < 4 ; i++) { dir = (dir + 3) % 4;// 반시계로 90도 회전 int nx = x + dx[dir]; ..

🔺 문제 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 🧩 해결 아이디어 • 구현 (dx/dy technique) (0,0)에서 시작해 바깥쪽에서 안쪽으로 돌며 격자를 돌며 칸을 채운다. 이미 방문한 칸이거나 격자 범위를 벗어난 칸인 경우, 아래 → 오른쪽 → 위쪽 → 왼쪽 순으로 방향 전환하게 했다 💥 유의사항 ArrayIndexOutOfBoundsException 주의,, 코드 앞뒤나 위아래 작성 순서에 따라 틀릴 수 있어서 순서를 잘 생각해야 함,, 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 1..

🔺 문제 4396번: 지뢰 찾기 지뢰찾기는 n × n 격자 위에서 이루어진다. m개의 지뢰가 각각 서로 다른 격자 위에 숨겨져 있다. 플레이어는 격자판의 어느 지점을 건드리기를 계속한다. 지뢰가 있는 지점을 건드리면 플레이어 www.acmicpc.net 🧩 해결 아이디어 • 구현 필요 변수 char형 2차원 격자 배열 열렸는지 확인용 boolean형 2차원 방문 배열 지뢰 갯수 저장할 int형 2차원 배열 지뢰 건드렸는지 확인용 boolean 변수 지뢰 위치를 2차원 char형 배열로 입력받는다. 열린 칸과 안 열린 칸을 입력 받는다. 해당 칸이 열렸을 경우, 해당 칸은 방문 처리 지뢰가 아닌 칸이 열린 경우, 8방향을 돌며 주변 지뢰 갯수를 센다. 지뢰인 칸이 열린 경우, 입력받을 때 지뢰였던 칸은 '..