We will find a way, we always have.

-interstellar

브루트포스 2

[백준] 13140번: Hello World! - 파이썬

🔈 문제 N이 주어질 때 hello + world = N을 만족하는 서로 다른 한 자리 자연수(0 포함) d, e, h, l, o, r, w를 구해서 아래 그림과 같은 형태로 출력하는 프로그램을 작성하여라. 단, h와 w는 0이 될 수 없다. 📝입력 첫 번째 줄에 양의 정수 N이 주어진다. N은 32비트 정수 범위로 표현할 수 있는 수만 들어온다. 📑출력 만약 답이 없으면 'No Answer'을 출력한다. 그렇지 않은 경우 가능한 답들 중에서 아무거나 출력한다. 📚 문제 해석 처음에는 l이 같은 위치에 있다는 것을 이용하여, n[-2]//2 로 l을 먼저 구한다음, n[-3] - l 을 통해 (2*l 에 캐리값이 있는지 확인후) r 을 구하고, o와 d는 for 문을 돌려 구한뒤, e를 구하고 마지막으로..

순열과 조합 그리고 브루트 포스

브루트 포스 (Brute-force) 는 '무차별 대입' 이라는 의미이다. 말 그대로 모든 경우의 수를 대입해보는 것이다. 완전탐색 전략을 사용하여 확실하게 답을 구하는 알고리즘이지만 단점은 시간복잡도에 있다. 모든 경우를 돌아보기 때문에 문제에서 시간초과가 발생 할 수 있다. 다음 문제를 보자. N개의 수를 입력 받아서 두 수를 뽑아 합이 가장 클 때는? 브루트 포스를 사용한다면 2중 for문을 돌면서 두 수를 골라 더해서 최댓값을 갱신하면 '두 수를 뽑는 모든 경우'를 살펴보게 되고, 답을 확실하게 구할 수 있다. 이때 시간 복잡도는 O(N^2)이 된다. 버뜨 list 사용해서 최댓값 찾고 그 두개를 더하면 시간복잡도는 O(NlogN)이다. 브루트 포스로 문제를 풀 때는 반복문을 사용할 때도 있고, ..