브루트_포스

[C++] 백준 1107번 리모컨

브루트 포스 완전탐색 문제. 이 문제는 두 번 풀게됐는데, 처음에 푼 완전탐색 코드에서 시간이 다른 사람들에 비해 너무 많이 나와서 백준 게시판을 참고해서 다시 풀게됐다. 정답 비율이 낮지만 반례를 보면서 디버깅을 하다보면 풀 수 있었던 문제다. 글 읽기 - [반례모음] 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 반례는 위 사이트를 참고했다. 문제풀이 TV를 보는데 현재 채널이 100이다. 그리고 채널을 돌리려고 하는데, 일부 숫자가 고장이 났다. +버튼은 +1채널, -버튼은 -1채널인데 0채널에서는 변화하지 않는다. 조건은 간단하다. 위 조건만 고려해주면된다. 처음에 푼 방식은 조건을 나누어서 계산해서 풀었다. 모두 +로 계산했을 때, 모두 -로 계산했을 때, 숫자로 최대한 가까..

[C++] 백준 14500번 테트로미노

브루트 포스 / 구현 문제. 모든 경우를 다 확인하는 코드를 작성하면 맞출 수 있다. 문제풀이 문제는 위와같은 경우의 수들로 나뉘어져 있다. 이 모든 경우의 수를 고려해주면 된다. 빨간색으로 칠해진 원은 시작점이 저기일때라고 가정한 것이라고 생각하면 된다. 처음에는 해당 부분을 탐색하는 것을 일일이 따로 예외로 두어서 구현해 보았는데 틀렸습니다가 나왔을 때 고려해 줄 부분을 찾기가 너무 어려웠다. 따라서 이 코드를 다 지우고 새로운 방법으로 찾았다. 코드를 살펴보자. 우선 결과값을 매번 갱신하기 위해, max() 메서드를 사용하려고 algorithm STL을 사용했다. 그리고 위처럼 하드코딩을 하지 않게 하기위해 Direction 클래스를 만들어서 현재 좌표에서 각 네 칸을 어떻게 더해줘야 할지 pair..

[C++] 백준 15686번 치킨 배달

구현 및 브루트 포스(완전 탐색) 문제. 처음에 잘못된 백트래킹과 dfs로 접근해서 시간초과를 많이 냈다. 백준 게시판에서 도움을 얻고, 겨우 풀었다. 처음 이 문제를 봤을 때 백트래킹으로 폐업시킬 치킨집을 정하고 그래프 탐색으로 (처음에는 BFS로 하려 했으나 코드로는 DFS로 했다.) 최단거리에 있는 치킨집의 거리를 다 구해서 더하고 어떤 치킨집들을 폐업시킬 때 최소 거리가 나오는지 구하려 했다. 이 방법은 시간초과가 났고, 게시판을 참고한 결과 다음과 같은 도움을 얻었다. 폐업시킬 치킨집을 고르는 것이 아닌, 그냥 치킨집들 중 어떤 치킨집들을 open할 지 결정하면 된다. 각 집들의 거리와 치킨집들의 거리를 저장해두고 쓰면, 굳이 도시들을 다시 살펴보지 않아도 된다. 이 두개가 이 문제의 keypo..

[C++] 백준 2468번 안전 영역

2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net (문제가 길어서 캡쳐화면 대신 링크로 대체) 그래프 탐색 문제. 그래프 탐색에 브루트 포스(완전 탐색)를 곁들인(?) 문제이다. 문제를 이해하는 것도 어려웠고, 생각해야할 조건들도 까다로웠다. 문제풀이 일단 문제를 잘 해석해보면 연결 요소의 개수(ConnectedComponents)를 구하는 문제라는 것은 알 수 있다. 그리고 고려해야할 사항들이 있다. 물의 높이보다 낮거나 같으면 물에 잠긴다. 모든 도시가 물에 잠기지 않을 수도 있다. (연결 요소의 개수는 최소 0이..