조합

📖 문제 https://www.acmicpc.net/problem/17142   💡  풀이 방식• 조합 + BFS[필요 자료구조]- 바이러스 객체 ⇒ (행,열, 거리 값) 저장- 인접한 4방향 탐색할 dx/dy 배열- 바이러스 위치 저장용 객체 리스트- 초기 빈 칸 개수 저장하는 int형 변수 zeroCnt  연구소의 상태를 입력받는다.빈 칸(0)인 경우, zeroCnt에 +1 한다.바이러스(2)인 경우, 해당 위치와 0을 리스트에 저장한다.빈 칸의 갯수가 0이라면, 0을 출력하고 종료한다. / 그게 아니라면, 바이러스 위치 중 M개를 뽑아 바이러스를 심고 퍼뜨리는 데 걸리는 최소 시간을 계산한다.M개 바이러스 뽑기 > 조합 (백트래킹)바이러스 퍼뜨리기 > BFS- M개 바이러스를 뽑았으면, 해당 위..

📖 문제   18428번: 감시 피하기NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복www.acmicpc.net   💡  풀이 방식• 조합(DFS) + BFS 1. 격자를 입력받으면서 학생 S의 위치, 선생님 T의 위치, 빈 칸 X의 위치를 각 리스트에 저장해둔다.이러면 나중에 완전탐색으로 학생, 선생님, 장애물 위치를 따로 안 찾아도 된다.for(int i = 0 ; i   2. 빈 칸 X의 위치들 중 3개를 뽑고, 해당 위치에 장애물을 심었을 때 모든 학생들이 감시를 피할 수 있는지 BFS로 탐색한다.private static void dfs(int..

📖 문제  17141번: 연구소 2인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러www.acmicpc.net   💡  풀이 방식• 조합(DFS) + BFS필요 자료구조- 인접한 4방향 칸 탐색용 dx/dy 배열- BFS용 방문 표시용 2차원 boolean형 배열- 바이러스 위치 저장용 리스트 virusList- 뽑은 바이러스 M개 저장할 임시 리스트 tmpList  1. 연구소 정보를 저장하면서, 바이러스 위치도 저장한다.2. 조합(DFS)으로 바이러스 위치들 중 M개를 뽑아 뽑은 칸에서 BFS 탐색을 통해 바이러스를 퍼뜨리는 시간을 계산한다. [바이러스 위치들 중 ..

📖 문제 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 💡 풀이 방식 • 부분 집합 (백트래킹, 재귀) + BFS 필요 자료구조 [전역변수] - 인구 수 저장용 1차원 int형 배열 - 그래프 정보를 저장하기 위한 그래프 리스트 배열 - 부분 집합용 사용 여부 표시용 1차원 boolean형 배열 - 최솟값 [BFS용] - 방문할 원소를 저장하는 Integer형 큐 - 방문 표시용 1차원 boolean형 배열 (연결되었는지 확인용) [두 그룹에 속한 원소들 저장하고, 차이 저장용] - 구역A 원소들 저장할 Integer형 리스트 -..

📖 문제 15489번: 파스칼 삼각형 첫째 줄에 양의 정수 R, C, W가 공백을 한 칸씩 두고 차례로 주어진다. (단, 2 ≤ R+W ≤ 30, 2 ≤ C+W ≤ 30, 1 ≤ W ≤ 29, C ≤ R) www.acmicpc.net 💡 풀이 방식 • 조합 (DP) 파스칼 삼각형을 모두 왼쪽으로 밀었다고 생각하고 2차원 배열을 채운다. 맨 왼쪽 줄(= 0번째 열) 과 행=열인 칸은 값을 1로 채운다. 나머지 (i, j) 위치의 칸은 왼쪽 위 칸 (i-1, j-1)과 바로 윗 칸 (i-1,j)의 합으로 채운다. dp[i][j] = dp[i-1][j-1] + dp[i-1][j] 점 (R,C)부터 길이가 W인 삼각형의 합을 구한다. 이 때 삼각형 모양으로 범위를 제한하기 위해 변수 tmp를 활용하며, 현재 행..

📖 문제 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net 💡 풀이 방식 • DP . 2차원 배열을조합 식 nCr = n-1Cr-1 + n-1Cr 을 활용해 채운다. - 첫 번째 열에 있는 칸과, 행=열인 칸은 1로 초기화 dp[n][k] = dp[n-1][k-1] + dp[n-1][k] 🔺 코드 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 import java.util.*; import java.io.*; publi..

🔺 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 🧩 해결 아이디어 • 백트래킹 (조합) . 필요 자료구조 ┕ 격자 저장할 2차원 int형 배열 ┕ 중복 방지용 boolean형 배열 ┕ 조합 숫자들 저장용 int형 리스트 (열 저장) . 시간 복잡도 : O(N! * N) - 2차원 배열에 값을 입력받는다. - 1부터 N행까지 돌며 어떤 열을 색칠할지 N개의 값을 뽑아 조합을 생성한다. - 해당 조합에 있는 숫자들 중 최솟값을 구하고, 이 최솟값을 현재 최댓값과 비교해 갱신한다. 💥 유의사항 각 행과 열에 1개의 색칠된 칸만 오게 한다고 하였으므..

🔺 문제 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 🔺 코드 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 import java.util.*; import java.io.*; public class Main { static int L, C; stat..

🔺 문제 15686번: 치킨 배달크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸www.acmicpc.net  🔺 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980import java.util.*;import java.io.*; public class Main {    static int N, M;    static i..