브루트포스

[C++] 백준 17779번 게리맨더링 2

17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 에 수록된 문제. 구현 / 브루트포스(완전탐색) / 시뮬레이션 문제. 처음에 조건 한줄을 잘못설정해줘서 계속 틀렸다. 반복문에서 break를 걸어주어야 하는데, continue를 써준게 틀린원인이였다. 정답률도 높은 편이고 생각한대로 구현을 잘 해주면 쉽게 맞출 수 있는 문제였다. 문제풀이 문제의 조건을 요약하면 다음과 같다. 선거구를 5개로 나눈다. 선거구를 나누는 것은 기준점 x, y와 길이 d1, d2를 정해서 나눠준다. d1은 ..

[C++] 백준 17135번 캐슬 디펜스

구현 / 시뮬레이션 문제. 삼성 A형 기출 문제에 수록되어 있는 문제다. 조합, 구현으로 문제를 풀었는데 그래프 탐색 이론으로도 풀 수 있다고 한다. (그래프 탐색 이론은 상상도 못했고 지금도 잘 감이 안온다. 아마 궁수마다 BFS돌면서 제일 가까운 적을 죽이는 방식인 것 같다.) 골드 구현 문제를 많이 풀어봤다면 시도해볼법한 문제였다. 처음에 테스트 케이스를 다 맞춰서 문제를 푼 줄 알았는데, 자꾸 31%를 못넘었었다. 나는 적들의 좌표를 기록해주고, 거리와 c값에 따라 정렬해 준 후에 푸는 방식으로 풀었는데, 죽은 적들의 좌표를 기록에서 지워주지 않아서 틀리고 있었다. 문제풀이 각 문제의 조건들을 어떻게 해결할 수 있을까? 1. 두 위치의 거리는 |r1 - r2| + |c1 - c2|로 해결할 수 있..

[C++] 백준 15683번 감시

15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 문제가 길어서 링크로 대체하겠다. 구현, 시뮬레이션, 브루트 포스 문제. 노가다해서 풀었는데, 사실 마땅한 좋은 방법이 딱히 떠오르지가 않았다. 코드 길이가 너무 길어서 비효율적이라고 생각하지만, 시간은 빠르게 나왔다. 문제풀이 CCTV가 1번부터 5번까지 있다. 각 번호마다 감시하는 방향이 존재하는데, CCTV는 90도 회전이 가능하다. 이 때, CCTV들의 방향을 설정해서 사각지대가 최소가 될 때 몇 개가 되는지 구하는 문제이다. 1번 CCTV가 가..

[C++] 백준 1436번 영화감독 숌

처음에 이 문제를 봤을 때 문제를 처음 봤을 때 666, 1666, 2666 ... 이런식으로 흘러가는 건 이해를 했다. 근데 너무 쉬워서 그냥 N - 1 출력하면 되는 게 아닌가 생각했는데 아무리 생각해도 너무 쉬워서 문제를 계속 읽었다. 함정은 6이 연속으로 3번 들어가면 그게 영화의 번째수가 된다는 것. 7번째는 따라서 6666이 아니라 6660이 된다는 것이다. 접근한 방식 처음에는 모든 경우의 수를 나누려고 했다. 맨 처음에는 모든 경우의 수를 다 생각하려고 했다. 그러다 보니 문제가 고려할 부분도 상당히 많아졌고, 맞았다고 생각해도 틀렸습니다 가 나왔다. 결국 이 방법으로 1, 2시간 고민하다가 이건 아닌 것 같아서 다 지우고 새롭게 생각했다. 1000씩 더하는 게 아니라 1씩 더해봐서 6이 ..

[C++] 백준 1018번 체스판 다시 칠하기

오랜만에 풀어보는 알고리즘 문제였다. 어려운 문제는 아니고 손풀기 목적으로 골라본 문제였다. 처음 이 문제를 봤을 때 내가 접근했던 방식은 백트래킹을 생각했었다. 그리고 큐를 사용해서 후위표기식 느낌으로 모든 줄마다 push해서 pop했을 때 같은 색깔이 두 번 나오면 바꿔야되는 색을 하나씩 늘리는 것을 생각했다. 그런데 이렇게 할 경우 고려해야하는 예외의 경우가 너무 많아져서 포기했다. 후에 접근한 방식 문제를 다시 한번 잘 읽어보니, 체스판을 색칠하는 경우가 두 가지 뿐이라고 나와있었다. 즉, 내가 고려해야 하는 경우의 수는 두 개 뿐인 것이다. 좌상단이 검은색으로 시작하거나, 흰색으로 시작하거나이다. 이렇게 하면 모든 경우의 수를 다 고려할 수 있다. 보드를 나타내는 변수, n과 m을 나타내는 변수..