본문 바로가기

브루트 포스

Baekjoon 17136 색종이 붙이기 2019. 6. 2. Link https://www.acmicpc.net/problem/17136 소스결과 1988 KB / 36 ms 언어 C++ 17 출처 Baekjoon 분류 브루트 포스 설명 10 x 10 의 판에 1 이 적힌 부분을 덮기 위해 필요한 색종이의 수를 구하여라. 삽질에 삽질에 삽질을 했던 문제. 타임아웃 문제를 해결해야 했던 문제도, 그리디로 처리해 오답이 나온 경우도 있었다. 타임아웃의 경우는 한 위치에서 5x5 색종이가 놓는게 가능하다 할 때 이 위치는 4,3,2,1 이 가능하기때문에 모든 경우에 다 대입하는 방법이었는데 시간도 오래 걸릴 뿐 더러, 굳이 할 필요가 없는 문제였다. 그리디로 처리한 경우는 예제중 한 경우도 통과 못했었다. 정답은 타임아웃 경우를 조금 수정한 방법이었는데. 색종이를 놓을..
Baekjoon 12100 2048 (Easy) 2019. 3. 8. Link https://www.acmicpc.net/problem/12100 소스결과 1988 KB / 0ms 출처 Baekjoon 언어 C++ 17 분류 브루트 포스 설명 과거 유행했던 2048 게임을 모방한 Easy버전의 2048게임을 구현하자. 2048 게임을 해봤다면 문제 내용은 쉽게 이해 할 수 있는 문제. 단 새로운 블록이 추가 되지 않고. 결과값으로는 만들 수 있는 최대값을 출력 해야 한다. 최대 5번 이동을 한다는 제약, 그리고 움직일 수 있는 방향은 동, 서, 남, 북 4가지 방향이 조건이다. 4가지 방향으로 5번. 4 ^ 5 = 1024 충분히 해 볼만한 경우의 수 주의 할 점은 매 회마다 배열을 복사해서 넘겨 주어야 한다. 값을 이동 시킬 때는 현재 넣어야 할 위치를 지정하고, 다음 ..
BaekJoon 16922 로마 숫자 만들기 2019. 2. 13. Link https://www.acmicpc.net/problem/16922 소스결과 1984 KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 브루트포스 설명 I V X L 4개로 구성된 로마 숫자 N개를 이용하여 서로 만들 수 있는 다른 수의 총 가지 수를 출력하는 문제. 한개의 경우에 대해서 총 4개의 가지가 존재하는 전형적인 브루트 포스 문제 앞에서 미리 탐색을 한 경우에는 경우의 수에 추가 하지 않도록 확인 하는 변수가 필요하다. 또한 가지치기를 하지 않는 다면 바로 타임아웃이 걸린다. 모든 경우의 수를 다 확인 하면서 탐색을 적게 하는 방법을 적용해야 한다. 알고리즘 1. 숫자 n을 입력 받는다 ( 최대 깊이 ) 2. 0번 인덱스 부터 앞서 선택한 값 이상인 경우를 전부 탐색한다...
BaekJoon 2309 일곱 난쟁이 2019. 2. 3. Link https://www.acmicpc.net/problem/2309 소스결과 1988 KB / 0 ms 출처 Baekjoon, KOI 2004 초등부 1번 언어 C++ 17 분류 브루트 포스 설명 아홉 명의 난쟁이 중 일곱명을 선택해 난쟁이의 키가 100이되는 경우에 난쟁이의 키를 오름차순으로 출력하자. 오름차순으로 출력 하기 위해 9명의 난쟁이를 먼저 오름차순으로 정렬하자. 9명중에 7명을 조합하는 재귀 함수를 만든다. 합이 100이면 출력하자. 최종 경우에 합을 가지고만 판단하기에 앞서 누가 선태 되었는지 확인 할 수 없기에 누가 선택 됬는지 기억해줄 배열이 하나 필요하다. 알고리즘 1. 입력되는 9명의 난쟁이를 오름차순으로 정렬한다. 2. 9명 중 7명을 선택하는 조합 재귀함수를 만든다. 2..
Baekjoon 1405 미친 로봇 2019. 1. 21. Link https://www.acmicpc.net/problem/1405 소스 결과 1988 KB / 40 ms 출처 Baekjoon 언어 C++ 17 분류 DFS, 브루트 포스, 탐색 설명 통제할 수 없는 미친 로봇이 n번의 행동 중 로봇의 이동 경로가 단순한 경우의 확률을 구해 내는 문제 앞선 문제의 경우와 다른 점은 확률을 구해야 한다는 점이 가장 눈에 띈다. 이동 경로를 구해야 되는 문제이기 때문에 BFS/DFS를 사용 해야 한다. 하지만 이번 문제는 최단 경로를 구하는 문제가 아니기에 BFS를 사용하는것은 적절하지 않아보인다. 또한 로봇이 이동 할 수 있는 모든 경로에 대해서 탐색 해야한다. DFS를 진행 하면서 브루트 포스가 자동으로 진행 되기 때문에 크게 유의하지는 않아도 된다. 맵의 크기..
BaekJoon 1107 리모컨 2019. 1. 15. Link https://www.acmicpc.net/problem/1107 소스결과 2084KB 12 ms 출처 Baekjoon 언어 C++ 17 분류 브루트포스 설명 어떤 멍청이가 버튼을 너무 세게 누르는 바람에 버튼이 고장나서 내가 원하는 채널로 갈때 내가 버튼을 몇번 눌러야 하는지 계산 하는 문제 왜 고장을 낸건지 너무 화가난다. 처음으로 백준 게시판에 안된다고 반례 찾아달라고 질문 올린 문제, 테스트케이스만 30개 이상 돌려본거 같다. 접근을 3가지 방법으로 해야한다 1. 현재 채널에서 목표 채널까지 + , - 을 눌러서 최소로 가는 경우 2. 목표 채널보다 작으면서 최대인 경우 3. 목표 채널보다 크면서 최소인 경우 3가지 방법중에 최소인 경우를 구해야 한다. 또한 0000 의 경우에는 0을 한..
BaekJoon 14888 연산자 끼워넣기 2019. 1. 15. Link https://www.acmicpc.net/problem/14888 소스결과 1988 KB / 0 ms 출처 Baekjoon 언어 C++ 17 설명 수 사이에 연산자를 넣어 최대 최소가 되는 경우를 찾아내는 문제 수는 신경쓰지 않고 연산자를 할당하는 부분에 신경을 기울이면 된다. 또한 연산자의 개수가 정해져 있기 때문에 현재까지 몇개를 할당 해 줬는지 기억을 해줄 필요가 있다 연산자가 n-1개가 아니라 n개라면 맨 앞에 -를 넣는 경우를 생각 해야 하지만 현재 문제는 n-1 개 이기 때문에 고려하지 않아도 된다. 계산식의 우선순위가 없다는 점이 문제의 난이도를 낮춘다. 유의 할 점은 이번 연산자가 / 일때 분모가 0이 되는 경우는 제외해서 연산을 시켜야 한다. 또한 값을 최대 최솟값이 doubl..

티스토리툴바