본문 바로가기

전체 글96

[백준] 14502번 연구소 자바 문제 (DFS, 브루트포스 알고리즘) 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 풀이 세상에나 완전탐색 문제였다. 난 뭐 논리적으로 푸는 줄 알았는데 구글링해보니 그냥 모든 경우에 한해 벽 세우고 탐색하면서 안전구역의 최대값을 구하는 거였다... 나는 벽 세우는 것과 바이러스 퍼져나가는 것 둘 다 DFS로 구현했다. 그리고 minCount와 count 두 개의 변수를 이용해 답을 구했는데, 아래 코드에서 count는 해당 경우의 벽또는 바이러스의 개수 카운트이고, 이 수가 작을수록 안전구역의 개수가 커지는 것이므.. 2022. 2. 2.
[백준] 14888번 연산자 끼워넣기 자바 문제 (브루트포스 알고리즘) 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 풀이 사용되는 연산자를 해당 연산자의 인덱스번호를 perm_data에 담는다. 예를 들어 '+'가 1개, 'x'가 2개 이면 perm_data = {0, 2, 2} 이런 식으로 담기게 된다. 이 배열을 조합하여 모든 경우에 해당 되는 연산자 순서를 구하고, 구하는 경우마다 계산결과를 구해 답을 갱신한다. 소스 코드 import java.util.Scanner; public c.. 2022. 2. 2.
[백준] 10971번 외판원 순회 자바 문제 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 풀이 전체 도시를 순회하는 경우, 어느 도시에서 출발하든지 최소비용이 동일하다는 사실을 이해하면 순열을 이용하여 모든 탐색에 한하여 최소비용을 구하면 된다. 예를 들어, 3번 도시에서 출발하여 다음과 같은 순서로 순회했을 때가 최소 비용이라고 해보자. 3 → 2 → 0 → 1 → 3 이 순서는 어떠한 시작점으로 바꿔도 위와 같은 최소비용이 나온다. ex) 2 → 0 → 1 → 3 → 2 ex) 0 → 1 → .. 2022. 2. 2.
[백준] 2206번 벽 부수고 이동하기 자바 문제 (BFS, 골드4) 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 풀이 나에겐 이해하기 너무 어려운 문제였다... 일단 이 문제에서 궁금했던 세 가지는 1. 격자 최단경로에서 BFS를 쓰는 이유? : 트리의 경우, DFS로 두 정점 간의 거리를 구할 수 있다. BUT, 트리(거리가 하나 존재)라는 확증이 필요하다. 그래프의 경우, 내가 구한 경로가 최단경로인지 확신할 수 없다. 그래프를 DFS탐색할 경우 한 정점에 대해 타고타고 내려간 경로가 최소인지 확인이 필요하다. 따.. 2022. 1. 24.
[프로그래머스] 단체사진 찍기 자바 문제 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr 문제 풀이 나는 순열 함수를 따로 만들어서 모든 경우에 한해 조건 검사하고 맞는 경우에 answer값을 증가하여 답을 구했다. char배열에 각 이름을 담아 인덱스 번호를 이용하여 순열 결과로 나온 숫자와 매칭하여 조건 검사를 했다. 근데 검사할 때마다 모든 조건에 대해 split하고 검사하는 거라 뭔가 썩 좋은 방법같지는 않다고 생각된다... 소스 코드 class Solution { static int answer; static int n; stati.. 2022. 1. 21.
[백준] 10974번 모든 순열 자바 문제 (실버3) 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 ✔️ 사용 변수 문제에서 주어지는 순열 출력 숫자 : int N 출력 순서를 늘려나갈 숫자 변수: int depth 하나의 경우를 담아 출력할 배열 : int[] result 해당 숫자를 사용했는지 여부를 체크하기 위한 배열: boolean[] visited ✔️permutaion알고리즘 - 아래 그림처럼 각각의 시작 숫자로 사용하지 않은 숫자로 result배열을 채워나가면서 계속해서 재귀 호출한다. - 한 번의 수행 후에(마지막 배열의 호출이 끝난 후) 다시 visited배열을 초기화해가면서 사전 순으로 수를 담는다. 소스 .. 2022. 1. 21.

티스토리툴바