[백준][BOJ 5883] - 아이폰 9S
2023. 10. 5. 16:40
Algorithm/BruteForce
문제 https://www.acmicpc.net/problem/5883 5883번: 아이폰 9S 사람 9명이 줄을 서있고 각 사람이 원하는 용량의 크기는 2, 7, 3, 7, 7, 3, 7, 5, 7 이다. 용량 3을 원하는 사람을 줄에서 빼버리면, 줄은 2, 7, 7, 7, 7, 5, 7가 되고, 7을 원하는 사람이 4명이 연속된 구간이 www.acmicpc.net 문제 접근 특정 용량을 원하는 사람을 줄에서 제거했을 때 같은 용량을 원하는 연속된 사람의 길이의 최대값을 구하는 문제 모든 경우의 수를 탐색해야 한다. 예를 들어 0 0 1 2 0 0 3 0 3 3 이라는 입력이 있을 때 제거하는 경우의 수는 각각 0, 1, 2, 3이다. 이 모두를 탐색하면 된다. 즉 종류를 한번 카운팅해야 한다는 것이며..
[백준][BOJ 2422] - Ice Cream
2023. 10. 4. 17:04
Algorithm/BruteForce
문제 https://www.acmicpc.net/problem/2422 2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 www.acmicpc.net 문제 접근 1부터 $N$까지의 수들 중 3개를 뽑는 경우의 수를 구하는 문제 단 제약 조건이 달려 있는데 섞어먹으면 안되는 조합이 존재한다는 것이다. 만약 1은 2와 섞일 수 없다 라고 한다면 (1, 2, X) 로 되어 있는 모든 조합은 카운팅되지 않는다는 것이다. 즉 3개를 뽑은 뒤 각각의 수가 섞일 수 없는 수에 포함되어 있는지를 한 번 더 체크해야 ..
[백준][BOJ 1251] - 단어 나누기
2023. 10. 4. 12:59
Algorithm/BruteForce
문제 https://www.acmicpc.net/problem/1251 1251번: 단어 나누기 알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다. 먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다 www.acmicpc.net 문제 접근 입력으로 주어진 단어에 대해 문자열을 나누어 뒤집고, 이를 다시 조합하는 것이 가장 핵심적인 로직이다. 이때 만들 수 있는 모든 단어를 만들어야 하므로 어떻게 문자열을 나눌 것인지를 생각해야 한다. 모든 경우의 수를 따져보아야 하므로 문제에서 제시된 조건인 각각의 문자열은 적어도 길이 1 이상이어야 한다를 만족하도록 문자열을 나누어 주면 된다. 2중 for문으로 만들어낼 수 있다. ..
[백준][BOJ 1969] - DNA
2023. 10. 2. 14:29
Algorithm/BruteForce
문제 https://www.acmicpc.net/problem/1969 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 문제 접근 주어진 DNA입력들에 대해 Hamming Distance가 최소가 되는 DNA를 우리가 만들어야 한다. Hamming Distance의 경우 우리가 만든 DNA를 $s$라고 할 때 이 $s$의 각 부분과 주어진 DNA들의 각 부분을 비교해 다른 글자의 개수로 정의된다. 따라서 Hamming Distance를 최소화 시키기 위해서는 주어진..
[백준][BOJ 4134] - 다음 소수
2023. 10. 2. 13:06
Algorithm/BruteForce
문제 https://www.acmicpc.net/problem/4134 4134번: 다음 소수 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. www.acmicpc.net 문제 접근 $N$보다 크거나 같은 소수 중 가장 작은 소수를 구하는 문제 $N$이 최대 4억까지 주어질 수 있고, 어디까지 진행되는지도 알 수 없기 때문에 수 자체는 넉넉하게 long으로 잡았다. 생각해보면 그냥 int도 21억까지 지원하기 때문에 int로 해도 무방할 것 같기도 하다 이후에는 N을 1씩 증가시키며 소수인지를 판별했다. 소수를 판별하는 방식은 여러가지가 있지만 나는 루트를 적용하여 범위를 줄이는 방식을 사용하였다. 정답 코드 import java.io.Buf..
[백준][BOJ 2210] - 숫자판 점프
2023. 10. 2. 12:33
Algorithm/BruteForce
문제 https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 문제 접근 숫자판의 임의의 위치에서 인접한 4방향으로 5번 이동하면서 숫자판에 적힌 숫자를 붙이는 것이 핵심적인 기능이다. 이동 시에 이미 방문했던 칸을 다시 방문해도 상관없다는 조건이 붙어 있다. 숫자가 0인 경우에도 0으로 시작하는 수를 만들 수 있다. 위의 규칙을 만족시키면서 숫자판에서 이동할 때 나올 수 있는 모든 숫자의 개수를 구하는 것이 ..
[백준][BOJ] 27958 사격 연습
2023. 4. 6. 22:05
Algorithm/BruteForce
문제 https://www.acmicpc.net/problem/27958 27958번: 사격 연습 N×N 크기의 보드 판이 존재하며, 1개 이상의 표적이 존재한다. 한 학생은 사격을 연습하고 있으며, 1번부터 K번까지 K개의 총알을 가지고 있다. 학생은 총 K번의 사격을 진행하며, 1번부터 K번까지 www.acmicpc.net 문제 접근 N의 개수가 적은것으로 보아 브루트포스나 백트렉킹 유형의 가능성이 높아보인다. 예시를 볼 때, 그리디, 또는 DP적으로 생각해보아도 무언가 딱히 규칙성이 있어보이진 않았다. 그래서 브루트포스 유형으로 생각을 하고 접근하였다. N이 최대 8까지 올라갈 수 있고, 사격 횟수 K는 최대 5번까지이다. 이때 동일한 레인에서 쏴도 상관없다라는 설명이 있으므로 동일한 레인에 K번 ..
[BOJ 18428] 감시 피하기
2022. 12. 10. 00:31
Algorithm/BruteForce
문제 https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 접근 방법 3개의 위치를 선정하여 장애물을 놓고 그 장애물이 학생을 걸리지 않게 해 줄 수 있는지 판단하는 것이다. 즉, 문제는 2가지로 나눌 수 있다. 첫 번째로 3개의 위치를 선정해야 한다. 두 번째로 선정한 위치에 대해 감시를 피할 수 있는지 판정하는 로직을 넣어야 한다. N과 선생님의 전체 크기가 작고, 연산량 자체도 크지 않은 동시에 시간도 널럴하기 때문에 모든 위치에 대한..
[Programmers] 전력망을 둘로 나누기 - python
2022. 11. 23. 02:59
Algorithm/BruteForce
문제 접근 방법 문제의 유형이 일반적인 완전 탐색과는 달라보인다. 이 문제는 완전 탐색의 개념 + DFS/BFS 알고리즘이 합쳐진 문제로 개인적으로 꽤 좋은 문제라고 생각한다. 전선들 중 하나를 끊어 둘로 나뉘어진 송전탑의 개수를 구해야 한다. 이번 문제를 그래프로 모델링해보면 아래와 같을 것이다. 입력 예제로는 첫번째 샘플 예제를 사용한다. 이 그래프에서 우리는 어떤 간선을 잘라 두 개의 트리로 만들고 각 트리에 속한 정점의 개수들을 계산해야 한다. 간선은 단 한번만 자를 수 있다. 그럼 여기서 생각할 수 있는 경우의 수는 몇 가지일까? 이 문제의 경우의 수는 조합으로 환원할 수 있다 정점의 수가 N개라고 할 때 간선의 수는 N - 1개라고 문제에서 정의하고 있다. 여기서 1개를 선택하는 것이므로 경우..
[Programmers] 카펫 - python
2022. 11. 23. 01:19
Algorithm/BruteForce
문제 설명 접근 방법 그림을 유심히 보면 다음과 같은 특성을 얻을 수 있다. 둘레에 놓인 갈색의 가로는 노란색의 가로 + 2와 같다. 둘레에 놓인 갈색의 세로는 노란색의 세로와 같다. 다만 노란색이 항상 1 x w의 형식으로 놓이지는 않기 때문에 노란색이 배치될 수 있는 경우의 수를 찾아야한다. 노란색의 영역이 w x h 일때 w, h이 될 수 있는 조건은 노란색의 개수의 약수여야 한다는 것에 포인트를 맞추어야 한다. 그렇다면 w, h은 다음과 같이 될 수 있을 것이다. W H 1 24 2 12 3 8 4 6 6 4 8 3 12 2 24 1 이때 문제에서 카펫의 가로 길이 w는 세로 길이 h 보다 크거나 같다는 조건을 본다면 경우의 수가 반토막이 난다. 따라서 최종적으로 생각해볼 수 있는 w, h는 다음..