Bruteforce

백준 2309번 문제 바로가기 bruteforce #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> snowWhite; int total = 0; int height = 0; bool check = false; for (int i=0; i<9; i++){ cin >> height; total += height; snowWhite.push_back(height); } sort(snowWhite.begin(), snowWhite.end()); for (int i=0; i<9; i++){ for (int j=i+1; j<9; j++){ if (snowWhite[i] + snowWhite[j] == total - 100){ check = true; for (int k=0; k<9; k++){ if (k == i || k == j){ continue; } cout << snowWhite[k] << endl; } break; } } if (check) break; } return 0; } Review bruteforce을 이용하면 간단하게 풀어낼 수 있는 문제 다만, 이중 for문을 사용하기에 break 처리에 유의해야 한다. 내부 for문만 break하고 외부 for문은 break하지 않으면, 모든 경우의 수를 출력하기 때문에 틀렸습니다가 발생할 수 있다.

백준 27295번 문제 바로가기 나의 풀이 문제 자체는 그리 어렵지 않다. x의 합=X, (b-y)의 합=Y라고 두면, 결국엔 $ a * X + Y = 0 $ 방정식을 푸는 것에 불과하기 때문이다. for 반복문으로 x와 y값의 합을 구해준 뒤에 조건에 따라 x_sum=0인 경우, 정수꼴, 분수꼴로 나눠주면 된다. 주의할 점은 주어진 정수의 값이 꽤 크기 때문이다. $ -10^{9} <= x,y <= 10^{9} $ 이고 $ 1 <= n <= 10^{5} $ 이므로 곱하다보면 최대 $ 10^{14} $ 가 되어 int 자료형으로는 overflow가 발생할 수 있다. int / long은 4 byte로, -2,147,483,648 ~ 2,147,483,647 범위를 가지기 때문이다. 따라서 p와 q, divider의 경우 long long 정수 자료형을 사용해서 overflow가 발생하지 않도록 방지해야 한다. ...

프로그래머스 피로도 문제 바로가기 나의 풀이 First Thoughts 어떤 기준에 따라 sort하면 최적 방법을 찾을 수 있지 않을까? (e.g key = lambda x : x[1]) -> 실패 그냥 bruteforce로 모든 경우의 수에 대해서 다 따져보자! 이를 위해서 itertools에서 permutations을 불러와서 모든 경우의 수를 따져주었다. math.perm()과는 달리 모든 경우의 수를 보여줘서 각 요소의 내용을 다뤄야할 때에는 매우 편리하다. from itertools import permutations as p def solution(k, dungeons): ans = 0 for dg in p(dungeons): hp = k cnt = 0 for d in dg: if d[0] > hp: break hp -= d[1] cnt += 1 ans = max(cnt, ans) return ans DFS 을 이용한 풀이 전혀 상상도 하지 못했는데 DFS을 이용한 풀이도 가능했다. 키포인트는 visited[j]를 1로 지정했다가 다시 0으로 바꿔주는 작업! ...

카펫 문제 바로가기 나의 풀이 문제를 해결하기 위해 끄적이다가 결국엔 약수를 구하는 아이디어로 접어들었다. 전체 넓이와 노란색 영역 넓이의 관계를 생각해보다가 다음을 만족한다는 사실을 발견했다. $ yellow_area = (width-2)*(height-2) $ 잘 이해되지 않는다면 다음 사진처럼 노란색을 움직인다는 아이디어로 접근해보자. def solution(brown, yellow): total = brown + yellow for i in range(3, total//2): if total % i == 0: width,height = (total//i),i if (width-2)*(height-2) == yellow: return (width, height) return -1 다른 풀이 구경하기 나는 넓이:넓이 관계에 집중했다면 다른 풀이에서는 넓이:둘레 상관관계로 접근한 것도 있었다. 전체 둘레에서 한 칸을 갈색 타일에 대응시키면 각 모서리(즉 4개)가 더블 카운팅되는데, $ 2*(height+width) = (brown - 4) $ 만족시키는지 확인하는 방법도 존재했다. ...

모의고사 문제 바로가기 나의 풀이 bruteforce 문제는 문제 이해만 잘 하면 솔직히 구현의 영역이다. PS에서 list을 다룰 때에 enumerate가 굉장히 유용하고 자주 쓰이기에 잘 활용하는 것이 중요하다. 아래 풀이에서는 그냥 1, 2, 3번 학생의 찍는 번호를 a,b,c array로 만들고 하나씩 확인하는 방법을 택했다. score=[0,0,0]으로 선언하고 각 자리에 1,2,3번 학생의 점수를 더해주면 나중에 오름차순하는 소요가 줄어서 풀이가 간편해진다. def solution(answers): a = [1,2,3,4,5]*2000 b = [2,1,2,3,2,4,2,5]*1250 c = [3,3,1,1,2,2,4,4,5,5]*1000 score = [0,0,0] for i, ans in enumerate(answers): if a[i] == ans: score[0] += 1 if b[i] == ans: score[1] += 1 if c[i] == ans: score[2] += 1 answer = [] for i, s in enumerate(score): if s == max(score): answer.append(i+1) return answer 다른 사람의 풀이 구경하기 순환주기 고려해주기 pattern1[idx%len(pattern1)] 처럼 각각의 순환 주기로 index을 나누어주면 큰 숫자에 대해서도 정답을 구할 수 있다. a = [1,2,3,4,5]*2000처럼 안해도 되어서 메모리 절약 가능! ...