개발개발

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/43163?language=java 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 2. 풀이 가장 짧은 변환 과정을 찾으므로 BFS를 사용해 풀이한다. 두 개의 단어가 주어졌을 때, 하나의 단어를 다른 단어로 변환할 수 있는지(다른 알파벳의 갯수가 1개인지)를 판별하는 함수 isChangeOk()를 구현한다. 처음 시작하는 단어인 begin와 단어 후보들(words..

1. 문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 2. 풀이 총 5개의 블록이 있는데, 이 중 ㅜ 블록(분홍색 블록)을 제외하고는 DFS 4번을 통해 대칭, 회전을 한 모든 블록의 모습을 구할 수 있다. 따라서, ㅜ를 제외한 4개의 블록은 DFS를 통해 4개 칸의 합을 구하고, ㅜ는 별도의 함수를 통해 4개 칸의 합을 구한다. 모든 칸에서 4개 블록타입을 모두 확인해야 하므로, 처음 DFS를 호출 할 때 백트래킹을 사용한다.(81~83..

1. 문제 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 2. 풀이 가장 빠른 횟수를 구하기 위해 BFS를 사용한다. 구슬이 굴러가면 파란 구슬과 빨간 구슬이 같이 굴러가게 되므로, 두 구슬의 위치를 모두 담은 클래스를 선언해 사용한다. 맨 처음 구슬의 위치를 저장해 BFS를 시작한다. 구슬들의 위치 방문여부를 확인하기 위해 4차원 배열을 사용한다.(visited[n][m][n][m]) 4 방..

1. 문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 2. 풀이 백트래킹을 이용해 풀이한다. DFS를 이용해 한 사람씩 팀에 추가시키고 이를 boolean 배열에 저장한다(boolean[] visited) 선택한 사람의 수가 n/2인 경우, 즉 두 팀이 결성된 경우 두 팀의 점수차를 구한다. 두 팀의 점수차가 0인 경우 이미 최솟값이므로 프로그램을 종료한다. 3. 코드 import java.util.*; import java.io.*; class Main{ s..

1. 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 2. 풀이 벽을 세울 위치를 선택할 때 DFS, 바이러스가 퍼지는 과정은 BFS를 이용해 풀이한다. 입력을 받을 때, 바이러스가 있는 좌표(값이 2인 부분)은 따로 저장해둔다. DFS를 이용해 벽을 세운다. 재귀함수를 이용해 DFS를 구현한다. map 중 벽을 세울 수 있는 부분(map[i][j] == 0)에 벽을 세운다.(map[i][j] = 1) 3개의 벽을 모두 세울때까지 재귀함수를 호출해 이..

1. 문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 2. 풀이 백트래킹을 이용해 풀이한다. 기호별 사용할 수 있는 남은 갯수를 담은 배열(markCnt)에서 0이 아닌 경우, 즉 기호를 사용할 수 있는 경우 기호를 사용한 계산을 한다. 모든 경우를 구하기 위해 재귀함수 실행 후, 기호별 사용할 수 있는 갯수를 다시 늘려준다.(markCnt[i]++) 계산식을 끝까지 구한 경우, 이전..

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42895?language=java 코딩테스트 연습 - N으로 표현 programmers.co.kr 2. 풀이 재귀함수를 이용한 DP를 통해 풀이한다. 재귀함수의 매개변수로 지금까지 쓰인 숫자의 수, 현재까지의 계산 결과를 넣는다. for문을 통해 숫자의 갯수를 가능한 범위까지 늘려가며 +,-,/,* 연산을 한다. 최솟값이 8보다 크면 -을 return 한다. 3. 코드 class Solution { int answer = 9; public void dp(int N, int number, int count, int currentNumber){ if(count > 8) { return; } if(curre..

1. 문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 2. 풀이 BFS를 통해 상어의 위치를 이동해가며, 먹을 수 있는 물고기 중 가장 작은 거리를 선택하고 더이상 먹을 수 없는 물고기가 없을 때까지 이 과정을 반복해 답을 구한다. 전체적인 풀이 과정은 아래와 같다. 상어의 위치를 저장하고, 상어의 위치에서부터 탐색을 시작한다. 상어의 위치에서 BFS를 해 상어의 위치를 이동시킨다. 상어가 갈 수 있는 경우는 (1) 상어의 크기보다..

1. 문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 2. 풀이 백트래킹을 이용해 풀이한다. 백트래킹을 통해 치킨집을 하나씩 선택하며 총 m개의 치킨집을 선택한다.(backTracking()) 백트래킹을 하기 위해, 방문여부를 나타내는 boolean[] visited을 사용한다. m개의 치킨집을 고른 경우, 도시의 치킨 거리를 구한다(getChickenDist()). 최소 도시의 치킨 거리를 구한다.(Math.min(..

1. 문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 2. 풀이 n일에 받을 수 있는 최대 수익을 기억하기 위해 DP 배열을 사용한다. 날짜 범위 내에 일 종료가 가능한 경우(i + time[i]