본문 바로가기

알고리즘/백준 - 실버19

백준 10974 순열 백준 10974 순열 1. 문제 링크 https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 2. 문제 해결에 대한 아이디어 문제의 테스트 케이스는 [1, 2, 3]에 대한 순열의 결과이다. visit 을 사용하여, 순열 결과 배열(int[] candidate)에 들어가는 숫자의 순서를 제어한다. 백트래킹으로 모든 순열을 구할 수 있으며, 테스트 케이스 기준으로 아래와 같이 동작한다. (depth를 인데스로 사용하고 있다.) 재귀의 depth별 결과는 아래와 같다. 3. 코드 import java.io.BufferedReader; impor.. 2021. 12. 28.
백준 6603 로또 백준 6603 로또 1. 문제 링크 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 2. 풀이 이 문제는 조합의 대표 유형이다. 조합은 순서를 고려하지 않기 때문에 아래의 경우는 1개로 카운트 한다. - [1, 2, 3] / [1, 3, 2] / [2, 1, 3] [1, 2, 3] 에서 2개를 뽑는 경우를 생각해본다. 가능한 경우는 [1, 2] / [1, 3] / [2, 3] 총 3개이다. 처음 1을 뽑고 나서 1이 포함된 모든 경우.. 2021. 12. 27.
백준 7576 토마토 백준 7576 토마토 1. 문제 링크 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 2. 문제 해결에 대한 아이디어 1. input으로 토마토 상자에 대한 정보를 받을 때, 익은 토마토의 위치를 큐에 담는다. 2. 큐가 빌 때까지 BFS를 통해 안 익은 토마토를 익게 한다. 3. 이 때 weight 배열에 토마토가 익은 날짜를 기록한다. 4. BFS가 끝나면 토마토 상자를 순회하며 안 익은 토마토가 있는지 확인하고, 최대가중치.. 2021. 9. 7.
백준 1012 유기농 배추 백준 1012 유기농 배추 1. 문제 링크 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 2. 문제 해결에 대한 아이디어 input으로 들어온 2차원 배열을 순회하며 1(배추가 심어져 있는 땅)에 대해 BFS를 수행한다 BFS를 수행한 카운트를 출력한다. 3. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.ut.. 2021. 9. 6.
백준 4963 섬의 개수 백준 4963 섬의 개수 1. 문제 링크 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 2. 문제 해결에 대한 아이디어 1. Input으로 받은 2차원 배열을 순회하면서 1로 되어 있는 위치에서 BFS를 수행한다. 2. BFS를 수행한 카운트를 출력한다. 3. 대각선도 접근할 수 있는 것을 간과하면 안 된다. 3. 코드 import java.io.BufferedReader; import java.io.IOException; import .. 2021. 9. 6.
백준 2468 안전 영역 백준 2468 안전 영역 1. 문제 링크 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 2. 문제 해결에 대한 아이디어 1. 내린 비의 양에 따라 각 케이스 별로 안전 영역의 개수를 세야 한다. 2. 코딩할 때는, input 값 중 최대 높은 숫자부터 하나씩 줄여갔지만 현재 시점에선 그럴 필요 없다고 판단한다. . 내린 비의 높이를 0부터 차례대로 증가시키며 안전 영역의 개수를 세고 개수가 0일 때 끝내면 되었을 것 같다. 3. 내린 비의 높이 별로.. 2021. 9. 3.

티스토리툴바