본문 바로가기
반응형

브루트포스25

프로그래머스 혼자서 하는 틱택토 - C++ 풀이 1. 올바르게 틱택토를 플레이할 때 나올 수 있는 모든 보드를 구한다. 2. 모든 보드 중에 주어진 보드가 있는지 확인한다. 1. 올바르게 틱택토를 플레이할 때 나올 수 있는 모든 보드를 구한다. 보드가 9칸 밖에 되지 않기 때문에 가능한 모든 보드 상태를 구해도 충분하다. 재귀를 이용하여 모든 케이스를 구해주자. 2. 모든 보드 중에 주어진 보드가 있는지 확인한다. 이제 모든 케이스와 주어진 보드 상태를 비교하여 주어진 보드와 같은 케이스가 존재하는지 확인해주면 된다. #include #include using namespace std; vector allCases; bool isEqual(char a, char b, char c) { return a == b && b == c; } bool isFin.. 2023. 9. 5.
프로그래머스 이모티콘 할인행사 - C++ 풀이 1. 4가지의 할인율을 가질 수 있으므로 n개의 이모티콘들의 할인율을 설정하는 방법의 수는 4^n이다. 2. 비트마스크를 사용하여 이모티콘들의 할인율을 설정하는 모든 방법을 탐색한다. 3. 서비스 가입자 수가 가장 많은 방법, 서비스 가입자 수가 같다면 판매 금액이 가장 높은 방법을 선택한다. 1. 4가지의 할인율을 가질 수 있으므로 n개의 이모티콘들의 할인율을 설정하는 방법의 수는 4^n이다. 각 이모티콘별로 총 가지, 10%, 20%, 30%, 40% 중 하나의 할인율을 갖는다. 따라서 n개의 이모티콘들의 할인율을 설정하는 방법의 수는 4^n이다. 이모티콘의 개수 n은 최대 7로 매우 작기 때문에 모든 경우를 다 탐색하는 브루트포스를 사용하더라도 제한시간 내에 해결이 가능하다. 2. 비트마스크를 사용.. 2023. 7. 22.
백준 27172번 수 나누기 게임 - C++ 풀이 1. 약수&배수 관계인 수들의 결투만 의미가 있다. 2. 어떤 수 x의 모든 약수는 1 ~ sqrt(x)까지 순회하여 찾을 수 있다. 3. 각 xi에 대해 xi의 모든 약수들과 결투한다. 1. 약수&배수 관계인 수들의 결투만 의미가 있다. 두 수가 서로 약수와 배수 관계인 경우에만 점수에 변화가 생긴다. 따라서 주어진 수들의 약수&배수 관계에만 집중하자. 2. 어떤 수 x의 모든 약수는 1 ~ sqrt(x)까지 순회하여 찾을 수 있다. 어떤 수 x의 모든 약수는 1부터 sqrt(x)까지로 모두 나누어떨어지는지 확인하는 방식으로 구할 수 있다. 만약 x가 i로 나누어 떨어진다면, i와 x/i는 x의 약수이다. 이때 i = x/i인 경우는 주의하여 처리하여야 한다. 2. 각 xi에 대해 xi의 모든 약수들과.. 2023. 7. 9.
백준 20529번 가장 가까운 세 사람의 심리적 거리 - C++ 풀이 1. 33명의 사람을 16개의 mbti로 분류하는 경우, 최소한 한 mbti에는 반드시 3명이상 속하게 된다. 2. 32명 초과인 경우 심리적 거리의 최솟값은 0이다. 3. 32명 이하인 경우 심리적 거리의 최솟값은 브루트포스로 구할 수 있다. 1. 33명의 사람을 16개의 mbti로 분류하는 경우, 최소한 한 mbti에는 반드시 3명이상 속하게 된다. 비둘기집의 원리란 "n+1 마리의 비둘기가 n개의 비둘기 집에 나누어들어간다면, 적어도 한 집에는 반드시 두 마리 이상의 비둘기가 들어가게 된다"는 원리이다. 이것을 현재 문제에도 적용할 수 있다. 사람 = 비둘기, mbti 종류 = 비둘기집으로 생각하면 된다. mbti가 16종류가 있으므로, 만약 사람이 16+1=17명 있다면, 적어도 한 mbti에는 .. 2023. 7. 6.
백준 17779번 게리맨더링 2 - C++ 풀이 1. 모든 (x, y, d1, d2) 쌍에 대해 선거구 나누기를 하여 최적화한다. 1. 모든 (x, y, d1, d2) 쌍에 대해 선거구 나누기를 하여 최적화한다. 가능한 모든 (x, y, d1, d2) 쌍은 N^4개, 선거구 나누기 시뮬레이션에 O(N^2)의 시간 복잡도가 소요되므로, 전체 시간 복잡도는 O(N^6). 이때 N=20이므로 브루트 포스로 해결할 수 있다. 선거구 나누기 시뮬레이션은 주어진 조건을 잘 구현하면 되고, 경계선으로 둘러싸인 5번 선거구는 DFS로 처리해주었다. #include #include #include using namespace std; const int INF = 987654321; int N; int A[20][20]; int board[20][20]; bool va.. 2022. 9. 18.
반응형

티스토리툴바