본문 바로가기

프로그래밍33

[Algorithm] BruteForce 0. 정의 BruteForce란, '무식하게 풀어본다'는 말 그대로, 모든 가능한 경우의 수를 하나하나 늘어놓아 가며 그 답을 구하는 알고리즘이다. 다른 말로는 완전 탐색(Exhaustive Search) 이라고도 한다. 사람이 일일이 손으로 나열해 가며 풀기에는 그 경우의 수가 너무 방대하나, 컴퓨터라면 충분히 계산할 수 있기 때문에 어찌 보면 컴퓨터의 성능을 가장 잘 활용할 수 있는 방법이다. 가장 아름답지 못해 보이는 풀이법이 가장 컴퓨터의 순수성과 닿아 있는 방법이라고 할 수 있다. 1. 접근법 for, while문 등의 방법을 통해 접근할 수도 있고, 주로 재귀호출(recursive call)을 사용해 접근한다. 재귀호출을 사용할 때는 반드시 Base case를 올바르게 설정하여 무한 재귀호출의.. 2024. 1. 6.
[Greedy] 백준 2839: 설탕 배달 2839번: 설탕 배달 (acmicpc.net) 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 분명히 브루트포스 문제집에서 건진 문제이고 문제에 대한 사족으로 "원래는 수학 카테고리에 있었는데 브루트포스로 옮겼다"고 까지 적혀 있는데 내가 쓴 재귀함수를 이용한 탐색에서는 틀렸다. 정확히는 예시+내가 만들어 본 case에 관해서는 답이 맞게 나왔는데 정작 채점을 돌렸을 때 시간초과가 났다. 문제를 포스팅하기 앞서 Greedy 알고리즘이란, 각 선택 단계마다 그 단계에서 당장 최적인 선택을 하는 것이다. Greedy 알고.. 2023. 11. 20.
[BruteForce] BOJ1436: 영화감독 숌 1436번: 영화감독 숌 (acmicpc.net) 1436번: 영화감독 숌 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워 www.acmicpc.net 입력 N은 10000보다 작은 자연수이고, 문제에서 제시하는 "종말의 수"는 최소한 1000개에 1개 이상씩은 존재한다. 666이 가장 작은 종말의 수이기 때문에 xxxx~~ + 666 형태인 수는 역시 종말의 수가 되기 때문이다. 따라서 최악으로 치닫더라도 10000*1000으로 1억보다 적기 때문에 그냥 순수하게 0부터 하나씩 키워 가면서 N 번째 종말의 수가 무엇인지 찾아 보기로 하였다. #include .. 2023. 11. 15.
[BruteForce] 백준 1018 : 체스판 다시 칠하기 1018번: 체스판 다시 칠하기 (acmicpc.net) 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 올바른 체크판이 될 수 있는 경우는 10101010 01010101 10101010 01010101 10101010 01010101 10101010 01010101 01010101 10101010 01010101 10101010 01010101 10101010 01010101 10101010 (흰색이 0, 흑색이 1) 이 두 가지밖에 없기 때문에, 처음에는 입력받은 보드를 순회하면서 8*8 체크보드.. 2023. 3. 2.

티스토리툴바